图论实验代码

1、图论实验报告（代码）学号：1241902129姓名：肖尧1.写一个程序，输入一个图，一对顶点和通路长度，输出两个顶点间 指定长度的通路。 程序代码： #include<stdlib.h> #include<stdio.h> #include<iostream> using namespace std; #define MAX 20 typedef struct ArcNode int adjvex; struct ArcNode *nextarc; ArcNode; typedef struct VNode char data; ArcNode *first

2、arc; VNode,AdjListMAX; typedef struct AdjList vertices; int n,e; MGraph; int pathMAX; int visitedMAX; /返回字符 v 在图中的位置 int LocateVex(MGraph G, char v) int i; for(i=0;i<G.n;i+) if(G.verticesi.data=v) return i;break; return -1; /得到顶点 Vi char GetValue(MGraph G,int i) 1return (i>=0 && i<G

3、.n) ? G.verticesi.data : NULL; /判断字符 m 是否在图中 int IsIn(MGraph G,char m) int p; for(p=0;p<G.n;p+) if(G.verticesp.data=m) return p; return -1; /创建图 void CreatGraph(MGraph &G) int i,k; char m,n; ArcNode *s; cout<<"请输入顶点数和边数 : " cin>>G.n>>G.e; cout<<endl; while(G.

4、n>20) cout<<"输入的数字不符合要求,请重新输入 : " cin>>G.n>>G.e; while(G.e>(G.n-1)*G.n/2) cout<<"输入的数字不符合要求,请重新输入 : " cin>>G.e; cout<<"请输入各顶点的名称 : " /建立顶点表 for(i=0;i<G.n;i+) cin>>G.verticesi.data; G.verticesi.firstarc=NULL;/初始化图 cout&l

5、t;<endl; /输入边 for(k=0;k<G.e;k+) 2int a,b,p,q; cout<<"请输入有边的 2 个顶点 : " cin>>m>>n; cout<<endl; p=IsIn(G,m); q=IsIn(G,n); while(p=-1|q=-1) cout<<"输入的数字不符合要求,请重新输入: " cin>>m>>n; p=IsIn(G,m); q=IsIn(G,n); a=LocateVex(G, m); b=LocateVex(G

6、, n); /生成边表结点 s=(ArcNode*)malloc(sizeof(ArcNode); s->adjvex=a; s->nextarc= G.verticesb.firstarc; /将顶点 m 插入到顶点 n 之后 G.verticesb.firstarc=s; s=(ArcNode*)malloc(sizeof(ArcNode); s->adjvex=b; s->nextarc= G.verticesa.firstarc; /将顶点 n 插入到顶点 m 之后 G.verticesa.firstarc=s; /k 是要判断的长度，x,y 为给定的两个点的地

7、址 int Search(MGraph G,int x,int y,int k,int visited,int path,int d) int n,i; ArcNode *p; visitedx=1; d+; pathd=x; if(x=y && d=k) return 1; p=G.verticesx.firstarc; while(p !=NULL) n=p->adjvex; 3if(visitedn=0) if(i=Search(G,n,y,k,visited,path,d)=1) return i; p=p->nextarc ; visitedx=0; d-

8、; return 0; int main() char m,n; int x,y,k,j; for( int i=0;i<MAX;i+) visitedi=0; cout<<"本程序的功能：输入一个图，一对顶点和通路长度，输出两个顶点间指定长度 的通路数。"<<endl<<endl; MGraph G; CreatGraph(G); cout<<"寻找路径的两个顶点 : " cin>>m>>n; cout<<endl; while(IsIn(G,m)=-1 | Is

9、In(G,n)=-1) cout<<"顶点不符合要求,请重新输入 : " cin>>m>>n; cout<<"请输入想寻找的简单路径的长度 ：" cin>>k; cout<<endl; x=LocateVex(G,m); y=LocateVex(G,n); j=Search(G,x,y,k,visited,path,-1); if(j=1) cout<<"两个顶点间长度为"<<k<<"的通路 : " for(

10、int i=0;i<k;i+) cout<<GetValue(G,pathi)<<" => " 4cout<<n<<endl; else cout<<"长度为"<<k<<"的路径不存在！"<<endl; system("pause"); 运行结果（以 P287 页(图 7 - 2.8) 数据为例） ：2.编程用图的关联矩阵实现结点的合并，并输出合并后图的关联矩 阵。 程序代码： #include <io

11、stream> #include <iomanip> using namespace std; typedef struct Node int v; Node; typedef struct Edge int e0; Node begin; Node end; Edge; 5Node node20; Edge edge50; int Incidence_Matrix 5050; int Incidence_Matrix_2 5050; void inite(int m,int n); void memset(int m,int n); void mergence(int m,

12、int n,int merge_node1,int merge_node2); /初始化顶点和边 void inite(int m,int n) int i,j,a,b; for (i=0;i<m;i+) nodei.v=i; for (j=0;j<n;j+) cout<<endl; cout<<"请按照边的序号输入边的 2 个顶点 : " cin>>a>>b; edgej.e0=j; edgej.begin.v=a-1; edgej.end.v=b-1; /设置关联矩阵 void memset(int m,int

13、 n) int i,j; for (i=0;i<m;i+) for (j=0;j<n;j+) if (nodei.v=edgej.begin.v)|(nodei.v=edgej.end.v) Incidence_Matrix ij=1; cout<<endl; cout<<"完全关联矩阵 : "<<endl; 6for (i=0;i<m;i+) cout<<setw(3); for (j=0;j<n;j+) cout<<Incidence_Matrix ij<<setw(3);

14、cout<<endl; cout<<endl; /相关结点合并及合并后图的关联矩阵输出 void mergence(int m,int n,int merge_node1,int merge_node2) int i,j; int p=0,q=0; /两顶点合并及消失点标记 for (j=0;j<n;j+) Incidence_Matrix merge_node1-1j=Incidence_Matrix merge_node1-1j + Incidence_Matrix merge_node2-1j; if (Incidence_Matrix merge_node

15、1-1j=2) Incidence_Matrix merge_node1-1j=0; Incidence_Matrix merge_node2-1j=-1; /在合并后图的关联矩阵中消去标记顶点行 for (i=0;i<m;i+) for (j=0;j<n;j+) if (Incidence_Matrix ij!=-1) Incidence_Matrix_2 pq=Incidence_Matrix ij; q+; if (q=n) q=0; p+; 7/输出合并后图的关联矩阵 cout<<endl; cout<<"合并后图的完全关联矩阵 : &qu

16、ot;<<endl; for (i=0;i<m-1;i+) cout<<setw(3); for (j=0;j<n;j+) cout<<Incidence_Matrix_2 ij<<setw(3); cout<<endl; cout<<endl; void main(void) int m,n,merge_node1,merge_node2; cout<<"本程序的功能：输入一个图，用图的关联矩阵实现结点的合并，并输出合并后 图的关联矩阵。(顶点均按顺序用数字 1,2,3.表示)"

17、;<<endl<<endl; cout<<"请输入顶点数和边数 : " cin>>m>>n; inite(m,n); memset(m,n); cout<<"请输入需要合并的两个顶点(顶点均按顺序用数字 1,2,3.表示) : " cin>>merge_node1>>merge_node2; mergence(m,n,merge_node1,merge_node2); system("pause"); 运行结果（以 P296 页(图 7-3

18、.7) 数据为例） ：83.写一个程序，输入一个图，确定是否是欧拉图，如果是欧拉图，输 出欧拉回路。 程序代码： #include<stdio.h> #include<string.h> #include<stdlib.h> /顶点的堆栈 struct stack int top , node210; f; /图的邻接矩阵 int AdjMatrix2020; int n; /图的深度优先遍历 void Depth_First_Search(int x) 9int i; f.top +; f.nodef.top = x; for (i = 1; i <

19、= n; i +) if (AdjMatrixix > 0) /删除此边 AdjMatrixix = 0; AdjMatrixxi = 0; Depth_First_Search(i); break; /欧拉路算法 void Euler(int x) int i , b; f.top = 0; f.nodef.top = x; printf("n 该图的欧拉图（回路）是 ："); while (f.top >= 0) b = 0; for (i = 1; i <= n; i +) if (AdjMatrixf.nodef.topi > 0) b =

20、1; break; /如果没有点可以扩展，输出并出栈 if (b = 0) printf("%d" , f.nodef.top); f.top -; if(f.top != -1) printf(" => "); 10 /如果有，就 DFS else f.top -; Depth_First_Search(f.nodef.top+1); printf("nn"); int main() int m , s , t , num ; int i , j , begin; printf("本程序的功能：输入一个图，确定是否是

21、欧拉图。如果是欧拉图，输出欧拉回路。 (顶点均按顺序用数字 1,2,3.表示)nn"); printf("请输入顶点数和边数 : "); scanf("%d %d" , &n , &m); memset(AdjMatrix , 0 , sizeof(AdjMatrix); for (i = 0; i < m; i +) printf("n 请输入有边的 2 个顶点 ："); scanf("%d %d" , &s , &t); while(s < 0 | s &g

22、t; n | t < 0 | t > n) printf("n 输入的数字不符合要求,请重新输入 : "); scanf("%d %d" , &s , &t); AdjMatrixst = 1; AdjMatrixts = 1; /判断是否存在欧拉回路 s = 0; begin = 1; for (i = 1; i <= n; i +) num = 0; for (j = 1; j <= n; j +) num += AdjMatrixij; if (num % 2 = 1) 11 begin = i; s +;

23、if (s = 0) | (s = 2) Euler(begin); else printf("n 输入的图不是欧拉图！nn"); system("pause"); return 0; 运行结果（以 P303 页(图 b) 数据为例） ：4.写一个程序，输入一个图，输出每个顶点的度数。 程序代码： #include<stdio.h> #include<stdlib.h> #define M 20 #define MAX 20 12 typedef struct int begin; int end; edge; typedef s

24、truct int adj; AdjMatrixMAXMAX; typedef struct AdjMatrix arc; int vexnum, arcnum; MGraph; /函数申明 void CreatGraph(MGraph *); void DEG(MGraph *); /创建图 void CreatGraph(MGraph *G) int i, j,n, m; printf("请输入边数和顶点数 : "); scanf("%d %d",&G->arcnum,&G->vexnum); /初始化图 for (i =

25、 1; i <= G->vexnum; i+) for ( j = 1; j <= G->vexnum; j+) G->arcij.adj = G->arcji.adj = 0; /输入边 for ( i = 1; i <= G->arcnum; i+) printf("n 请输入有边的 2 个顶点 : "); scanf("%d %d",&n,&m); while(n < 0 | n > G->vexnum | m < 0 | m > G->vexnum

26、) printf("输入的数字不符合要求,请重新输入: "); 13 scanf("%d%d",&n,&m); G->arcnm.adj = G->arcmn.adj = 1; getchar(); printf("n 邻接矩阵为:n"); for ( i = 1; i <= G->vexnum; i+) for ( j = 1; j <= G->vexnum; j+) printf("%d ",G->arcij.adj); printf("n&q

27、uot;); /输出每个顶点的度数 void DEG(MGraph *G) int i, j, count; printf("n 每个顶点的度数如下：nn"); for ( i = 1; i <= G->vexnum; i+) count=0; for (j = 1; j <= G->vexnum; j+) if (G->arcij.adj = 1) count+; printf("deg(%c) = %dn",i+64,count); /主函数 int main(void) MGraph *G; G = (MGraph*)

28、malloc(sizeof(MGraph); if (G = NULL) printf("申请内存失败！"); exit(1); 14 printf("本程序的功能：输入一个图，输出每个顶点的度数。(顶点均按顺序用数字 1,2,3. 表示)nn"); CreatGraph(G); DEG(G); system("pause"); return 0; 运行结果（以 P272 页(图 b) 数据为例） ：5.写一个程序，输入一个有向图，输出每个顶点的出度和入度。 程序代码： #include<stdio.h> #include

29、<stdlib.h> #define M 20 #define MAX 20 typedef struct int begin; int end; edge; typedef struct 15 int adj; AdjMatrixMAXMAX; typedef struct AdjMatrix arc; int vexnum, arcnum; MGraph; /函数申明 void CreatGraph(MGraph *); void OUT_DEG(MGraph *); void IN_DEG(MGraph *); /创建图 void CreatGraph(MGraph *G)

30、int i, j,n, m; printf("请输入边数和顶点数 : "); scanf("%d %d",&G->arcnum,&G->vexnum); /初始化图 for (i = 1; i <= G->vexnum; i+) for ( j = 1; j <= G->vexnum; j+) G->arcij.adj = G->arcji.adj = 0; /输入边 for ( i = 1; i <= G->arcnum; i+) printf("n 请输入有边的 2

31、 个顶点（先输入起始结点，再输入终止结点） "); ：scanf("%d %d",&n,&m); while(n < 0 | n > G->vexnum | m < 0 | m > G->vexnum) printf("n 输入的数字不符合要求,请重新输入: n"); scanf("%d%d",&n,&m); G->arcnm.adj = 1; getchar(); printf("n 邻接矩阵为:n"); for ( i = 1;

32、 i <= G->vexnum; i+) 16 for ( j = 1; j <= G->vexnum; j+) printf("%d ",G->arcij.adj); printf("n"); /输出每个顶点的出度 void OUT_DEG(MGraph *G) int i, j, count; printf("n 每个顶点的出度如下：n"); for ( i = 1; i <= G->vexnum; i+) count=0; for (j = 1; j <= G->vexnum

33、; j+) if (G->arcij.adj = 1) count+; printf("out-degree(%c) = %dn",i+64,count); /输出每个顶点的入度 void IN_DEG(MGraph *G) int i, j, count; printf("n 每个顶点的入度如下：n"); for ( j = 1; j <= G->vexnum; j+) count=0; for (i = 1; i <= G->vexnum; i+) if (G->arcij.adj = 1) count+; pri

34、ntf("in-degree(%c) = %dn",j+64,count); 17 /主函数 int main(void) MGraph *G; G = (MGraph*)malloc(sizeof(MGraph); if (G = NULL) printf("申请内存失败！"); exit(1); printf("本程序的功能：输入一个有向图，输出每个顶点的出度和入度。(顶点均按顺序 用数字 1,2,3.表示)nn"); CreatGraph(G); OUT_DEG(G); IN_DEG(G); system("pause

35、"); return 0; 运行结果（以 P273 页(图 b) 数据为例） ：18 6.写一个程序，输入一个图，一对顶点和通路长度，输出两个顶点间 指定长度的通路数。 程序代码： #include<stdlib.h> #include<stdio.h> #include<iostream> using namespace std; #define MAX 20 typedef struct ArcNode int adjvex; struct ArcNode *nextarc; ArcNode; typedef struct VNode char

36、 data; ArcNode *firstarc; VNode,AdjListMAX; typedef struct AdjList vertices; int n,e; MGraph; int pathMAX; int visitedMAX; /返回字符 v 在图中的位置 int LocateVex(MGraph G, char v) int i; for(i=0;i<G.n;i+) if(G.verticesi.data=v) return i;break; return -1; /得到顶点 Vi char GetValue(MGraph G,int i) 19 return (i&

37、gt;=0 && i<G.n) ? G.verticesi.data : NULL; /判断字符 m 是否在图中 int IsIn(MGraph G,char m) int p; for(p=0;p<G.n;p+) if(G.verticesp.data=m) return p; return -1; /创建图 void CreatGraph(MGraph &G) int i,k; char m,n; ArcNode *s; cout<<"请输入顶点数和边数 : " cin>>G.n>>G.e; cou

38、t<<endl; while(G.n>20) cout<<"输入的数字不符合要求,请重新输入 : " cin>>G.n>>G.e; while(G.e>(G.n-1)*G.n/2) cout<<"输入的数字不符合要求,请重新输入 : " cin>>G.e; cout<<"请输入各顶点的名称 : " /建立顶点表 for(i=0;i<G.n;i+) cin>>G.verticesi.data; G.verticesi.fir

39、starc=NULL;/初始化图 cout<<endl; /输入边 for(k=0;k<G.e;k+) 20 int a,b,p,q; cout<<"请输入有边的 2 个顶点 : " cin>>m>>n; cout<<endl; p=IsIn(G,m); q=IsIn(G,n); while(p=-1|q=-1) cout<<"输入的数字不符合要求,请重新输入: " cin>>m>>n; p=IsIn(G,m); q=IsIn(G,n); a=Locat

40、eVex(G, m); b=LocateVex(G, n); /生成边表结点 s=(ArcNode*)malloc(sizeof(ArcNode); s->adjvex=a; s->nextarc= G.verticesb.firstarc; /将顶点 m 插入到顶点 n 之后 G.verticesb.firstarc=s; s=(ArcNode*)malloc(sizeof(ArcNode); s->adjvex=b; s->nextarc= G.verticesa.firstarc; /将顶点 n 插入到顶点 m 之后 G.verticesa.firstarc=s;

41、 /k 是要判断的长度，x,y 为给定的两个点的地址 int Search(MGraph G,int x,int y,int k,int visited,int path,int d) int n,i; ArcNode *p; visitedx=1; d+; pathd=x; if(x=y && d=k) return 1; p=G.verticesx.firstarc; while(p !=NULL) n=p->adjvex; if(visitedn=0) 21 if(i=Search(G,n,y,k,visited,path,d)=1) return i; p=p-&

42、gt;nextarc ; visitedx=0; d-; return 0; int main() char m,n; int x,y,k,j; for( int i=0;i<MAX;i+) visitedi=0; cout<<"本程序的功能：输入一个图，一对顶点和通路长度，输出两个顶点间指定长度 的通路数。"<<endl<<endl; MGraph G; CreatGraph(G); cout<<"寻找路径的两个顶点 : " cin>>m>>n; cout<<en

43、dl; while(IsIn(G,m)=-1 | IsIn(G,n)=-1) cout<<"顶点不符合要求,请重新输入 : " cin>>m>>n; cout<<"请输入想寻找的简单路径的长度 ：" cin>>k; cout<<endl; x=LocateVex(G,m); y=LocateVex(G,n); j=Search(G,x,y,k,visited,path,-1); if(j=1) cout<<"两个顶点间长度为"<<k<

44、<"的通路 : " for(int i=0;i<k;i+) cout<<GetValue(G,pathi)<<" => " 22 cout<<n<<endl; else cout<<"长度为"<<k<<"的路径不存在！"<<endl; system("pause"); 运行结果（以 P287 页(图 7 - 2.8) 数据为例） ：7.写一个程序，输入一个图，确定是否是欧拉图，如果是

45、欧拉图，输 出欧拉回路。 程序代码： #include<stdio.h> #include<string.h> #include<stdlib.h> /顶点的堆栈 struct stack int top , node210; f; /图的邻接矩阵 int AdjMatrix2020; int n; 23 /图的深度优先遍历 void Depth_First_Search(int x) int i; f.top +; f.nodef.top = x; for (i = 1; i <= n; i +) if (AdjMatrixix > 0) /删

46、除此边 AdjMatrixix = 0; AdjMatrixxi = 0; Depth_First_Search(i); break; /欧拉路算法 void Euler(int x) int i , b; f.top = 0; f.nodef.top = x; printf("n 该图的欧拉图（回路）是 ："); while (f.top >= 0) b = 0; for (i = 1; i <= n; i +) if (AdjMatrixf.nodef.topi > 0) b = 1; break; /如果没有点可以扩展，输出并出栈 if (b = 0

47、) printf("%d" , f.nodef.top); f.top -; if(f.top != -1) 24 printf(" => "); /如果有，就 DFS else f.top -; Depth_First_Search(f.nodef.top+1); printf("nn"); int main() int m , s , t , num ; int i , j , begin; printf("本程序的功能：输入一个图，确定是否是欧拉图。如果是欧拉图，输出欧拉回路。 (顶点均按顺序用数字 1,2,3.

48、表示)nn"); printf("请输入顶点数和边数 : "); scanf("%d %d" , &n , &m); memset(AdjMatrix , 0 , sizeof(AdjMatrix); for (i = 0; i < m; i +) printf("n 请输入有边的 2 个顶点 ："); scanf("%d %d" , &s , &t); while(s < 0 | s > n | t < 0 | t > n) printf(&

49、quot;n 输入的数字不符合要求,请重新输入 : "); scanf("%d %d" , &s , &t); AdjMatrixst = 1; AdjMatrixts = 1; /判断是否存在欧拉回路 s = 0; begin = 1; for (i = 1; i <= n; i +) num = 0; for (j = 1; j <= n; j +) num += AdjMatrixij; 25 if (num % 2 = 1) begin = i; s +; if (s = 0) | (s = 2) Euler(begin); e

50、lse printf("n 输入的图不是欧拉图！nn"); system("pause"); return 0; 运行结果（以 P303 页(图 b) 数据为例） ：8.输入一个图，用韦尔奇.鲍威尔着色理论对其进行着色。 程序代码： #include <iostream> 26 #include <iomanip> using namespace std; typedef struct Node int v; int deg; int color; bool flag; Node; typedef struct Edge int

51、e0; Node begin; Node end; Edge; Node node20; Edge edge50; int Incidence_Matrix 5050; int downnote20; int count_1=0; int draw_color=1; void inite(int m,int n); void memset(int m,int n); void sort(int m,int n); void Coloration(int m,int n); /初始化边和顶点 void inite(int m,int n) int i,j,a,b; for (i=0;i<m

52、;i+) nodei.v=i; nodei.deg=0; nodei.color=0; nodei.flag=false; for (j=0;j<n;j+) cout<<endl; cout<<"请输入有边的 2 个顶点 : " cin>>a>>b; 27 edgej.e0=j; edgej.begin.v=a-1; edgej.end.v=b-1; /设置关联矩阵及各顶点的度 void memset(int m,int n) int i,j; for (i=0;i<m;i+) for (j=0;j<n;j+

53、) if (nodei.v=edgej.begin.v)|(nodei.v=edgej.end.v) Incidence_Matrix ij=1; nodei.deg=nodei.deg+1; cout<<endl; cout<<"完全关联矩阵 : "<<endl; for (i=0;i<m;i+) cout<<setw(3); for (j=0;j<n;j+) cout<<Incidence_Matrix ij<<setw(3); cout<<endl; cout<<

54、;endl; cout<<"每个顶点的度数："<<endl; for (i=0;i<m;i+) cout<<"deg("<<i+1<<") = "<<nodei.deg<<endl; /度数排序 void sort(int m,int n) int i,j,temp; 28 for(i=0;i<m;i+) downnotei=0; nodei.flag=true; j=0; while (j<m) temp=0; for (i=0;i

55、<m;i+) if (nodetemp.deg<=nodei.deg)&&(nodei.flag!=false) temp=i; nodetemp.flag=false; downnotej=temp; j+; for (i=0;i<m;i+) if (nodei.flag!=false) nodei.flag=false; downnotem-1=i; cout<<endl; cout<<"按照度数递减对顶点进行排序 : "<<endl; for (j=0;j<m;j+) cout<<"顶点"<<downno