图的应用题
作为另一种非线性结构—图，它比树更复杂，它的数据元素之间存在多对多的关系，即图中任意一个节点都有多个前驱结点和多个后继结点。图中任意两个结点之间都有可能存在关系，从而可以表达数据元素之间更复杂的关系。
1．使用邻接矩阵或邻接表表示下面的无向图，并计算图中的总边数。
//创建无向图
#include <stdio.h>
#include <stdlib.h>
typedef char DataType;
typedef int weight; /*权值*/
#define MAXVEX 50 /*最大顶点个数*/
typedef struct {
weight arcs[MAXVEX][MAXVEX];/*邻接矩阵*/
DataType data[MAXVEX];/*顶点信息*/
int vexs; /*顶点数*/
}MGraph, *AdjMetrix;
//（1）创建邻接矩阵
void CreateGraph(AdjMetrix g, int m[][MAXVEX], DataType d[], int n) {
int i, j;
g->vexs = n;
for (i = 0; i < n; i++) {
g->data[i] = d[i];
for (j = 0; j < n; j++) g->arcs[i][j] = m[i][j];
}
}
//显示邻接矩阵
void DispGraph(AdjMetrix g) {
int i, j;
printf("顶点：\n\t");
for (i = 0; i < g->vexs; i++)
printf("V%c\t", g->data[i]);
printf("\n\n邻接矩阵：");
for (i = 0; i < g->vexs; i++) {
printf("\nV%c:\t", g->data[i]);
for (j = 0; j < g->vexs; j++)
printf("%d\t", g->arcs[i][j]);
}
printf("\n\n");
}
int main(int argc, char * argv[]) {
MGraph gg;
AdjMetrix g = ≫
int pos, i,p,bian;
char d[] = {'1','2','3','4','5','6'};
int m[][MAXVEX] = {{0,31,0,0,21,11},{31,0,7,18,0,8},{0,7,0,12,0,0},{0,18,12,0,29,23},{21,0,0,29,0,9},{11,8,0,23,9,0}};
CreateGraph(g, m, d, 6);
DispGraph(g);
for(int q=0;q<=5;q++)
{
for(int ml=0;ml<=5;ml++)
{
if(m[q][ml]>0)
p++;
}
}
bian=p/2;
printf("总边数：%d\n",bian);
system("pause");
return 0;
}
2.使用邻接表和逆邻接表表示有向图，带权值表示。
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define MAXVEX 50
#define MAXWEIGHT 100
typedef int DataType ;
typedef struct arc{/*边表结点类型*/
int adjvex;/*顶点序号*/
int wt;
struct arc* next;/*指向下一个邻接点*/
}ArcNode,*PArcNode;
typedef struct{/*顶点表结点类型*/
DataType data;/*顶点信息*/
ArcNode* head;/*边表头指针*/
}VexNode;
typedef struct{/*邻接表类型*/
VexNode lists[MAXVEX];/*顶点表*/
int edges,vexs;/*边数，顶点数*/
}VGraph,*AdjList;
void CreateGraph(AdjList *g,int m[][MAXVEX],int n){/*n为顶点总数*/
int i,j;PArcNode p;
*g=(AdjList)malloc(sizeof(VGraph));/*初始化邻接表*/
(*g)->edges=0; (*g)->vexs=n;
for(j=0;j<n;j++){
(*g)->lists[i].head=NULL; /*边表头指针初始化*/
for(i=n-1;i>=0;i--)
if(m[i][j]!=MAXWEIGHT) { /*矩阵元素不为0，则在边表中生成一个结点*/
p=(PArcNode)malloc(sizeof(ArcNode));
p->adjvex=i;
p->next=(*g)->lists[j].head;/*从链表头部插入新结点*/p->wt=m[i][j];
(*g)->lists[j].head=p;(*g)->edges++;
}
}
}
void DispGraph(AdjList g){
int i;
PArcNode p;
for(i=0;i<g->vexs;i++){
printf("\n point %d:\t",i+1);
p=g->lists[i].head;
while(p!=NULL){
printf("\t[%d]\t权值:\t %d",p->adjvex+1,p->wt);
p=p->next;
}
}
}
int main(int argc, char * argv[]) {
AdjList g;
int p, i;
int m[][MAXVEX] = { {MAXWEIGHT,8,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT},{MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,13},
{MAXWEIGHT,7,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT},{MAXWEIGHT,18,12,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT},{8,MAXWEIGHT,MAXWEIGHT,6,MAXWEIGHT,MAXWEIGHT} ,{21,MAXWEIGHT,MAXWEIGHT,19,12,MAXWEIGHT}};
CreateGraph(&g, m, 6);
printf("\n2:\n");
DispGraph(g);
system("pause");
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define MAXVEX 50
#define MAXWEIGHT 100
typedef int DataType ;
typedef struct arc{/*边表结点类型*/
int adjvex;/*顶点序号*/
int wt;
struct arc* next;/*指向下一个邻接点*/
}ArcNode,*PArcNode;
typedef struct{/*顶点表结点类型*/
DataType data;/*顶点信息*/
ArcNode* head;/*边表头指针*/
}VexNode;
typedef struct{/*邻接表类型*/
VexNode lists[MAXVEX];/*顶点表*/
int edges,vexs;/*边数，顶点数*/
}VGraph,*AdjList;
void CreateGraph(AdjList *g,int m[][MAXVEX],int n){/*n为顶点总数*/
int i,j;PArcNode p;
*g=(AdjList)malloc(sizeof(VGraph));/*初始化邻接表*/
(*g)->edges=0; (*g)->vexs=n;
for(i=0;i<n;i++){
(*g)->lists[i].head=NULL; /*边表头指针初始化*/
for(j=n-1;j>=0;j--)
if(m[i][j]!=MAXWEIGHT) { /*矩阵元素不为0，则在边表中生成一个结点*/
p=(PArcNode)malloc(sizeof(ArcNode));
p->adjvex=j;
p->next=(*g)->lists[i].head;/*从链表头部插入新结点*/p->wt=m[i][j];
(*g)->lists[i].head=p;(*g)->edges++;
}
}
}
void DispGraph(AdjList g){
int i;
PArcNode p;
for(i=0;i<g->vexs;i++){
printf("\n point %d:\t",i+1);
p=g->lists[i].head;
while(p!=NULL){
printf("\t[%d]\t权值:\t %d",p->adjvex+1,p->wt);
p=p->next;
}
}
}
int main(int argc, char * argv[]) {
AdjList g;
int p, i;
int m[][MAXVEX] = { {MAXWEIGHT,8,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT},{MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,13},
{MAXWEIGHT,7,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT},{MAXWEIGHT,18,12,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT},{8,MAXWEIGHT,MAXWEIGHT,6,MAXWEIGHT,MAXWEIGHT} ,{21,MAXWEIGHT,MAXWEIGHT,19,12,MAXWEIGHT}};
CreateGraph(&g, m, 6);
printf("\n1:\n");
DispGraph(g);
system("pause");
return 0;
}
3.求第1题中V3与V5之间的最短路径。
#include <stdio.h>
#include <stdlib.h>
#define MAXWEIGHT 100
#include<iostream>
using namespace std;
typedef char DataType;
typedef int weight; /*权值*/
#define MAXVEX 50 /*最大顶点个数*/
typedef int weight; /*权值*/
typedef struct{
weight arcs[MAXVEX][MAXVEX];/*邻接矩阵*/
DataType data[MAXVEX];/*顶点信息*/
int vexs; /*顶点数*/
}MGraph,*AdjMetrix;
/*下面添加4.2.1小节相关邻接表结构定义、函数和4.2.4小节普里姆算法函数*/
void CreateGraph(AdjMetrix g, int m[][MAXVEX], DataType d[], int n) {
int i, j;
g->vexs = n;
for (i = 0; i < n; i++) {
g->data[i] = d[i];
for (j = 0; j < n; j++) g->arcs[i][j] = m[i][j];
}
}
void Prim(AdjMetrix g,int v){
weight lowcost[MAXVEX];
int uset[MAXVEX],sum(0);
int i,j,MinEdge,MinWeight,k;
for(i=0;i<g->vexs;i++) { /*初始化lowcost和uset数组*/
lowcost[i]=g->arcs[v][i];
uset[i]=1;
}
uset[v]=0; /*把起始点放到最小生成树中*/
printf("起始点v%c\n",g->data[v]);
for(i=1;i<g->vexs;i++) {
MinWeight=MAXWEIGHT;
for(j=0;j<g->vexs;j++){
if(uset[j]&&lowcost[j]<MinWeight){/*寻找权值最小的边*/
MinWeight=lowcost[j];
MinEdge=j; /*权值最小的边的弧尾顶点*/
}
}
for(j=0;j<g->vexs;j++){/*寻找权值最小的边的弧头顶点*/
if(g->arcs[j][MinEdge]==MinWeight)
k=j;
}
sum+=MinWeight;
printf("边（v%c,v%c）\t权值[%d]\n",g->data[k],g->data[MinEdge],MinWeight);
if(g->data[MinEdge]=='5') {printf("最短路径值：%d",sum);
break;}
uset[MinEdge]=0;/*权值最小的边加入最小生成树*/
v=MinEdge;
for(j=0;j<g->vexs;j++){/*更新最小权值*/
if(uset[j]&&g->arcs[v][j]<lowcost[j])
lowcost[j]=g->arcs[v][j];
}
}
}
int main() {
MGraph gg;
AdjMetrix g = ≫
int pos, i;
char d[] = { '1','2','3','4','5','6'};
int m[][MAXVEX] = { {MAXWEIGHT,31,MAXWEIGHT,MAXWEIGHT,21,11},{31,MAXWEIGHT,7,18,MAXWEIGHT,8},
{MAXWEIGHT,7,MAXWEIGHT,12,MAXWEIGHT,MAXWEIGHT},{MAXWEIGHT,18,12,MAXWEIGHT,29,23},{21,MAXWEIGHT,MAXWEIGHT,29,MAXWEIGHT,9} ,{11,8,MAXWEIGHT,23,9,MAXWEIGHT}};
CreateGraph(g, m, d, 6);
Prim(g,2);
system("pause");
return 0;
}
支持可以关注我哦，持续分享编写的代码。
