• 第1关：图的邻接矩阵存储及求邻接点操作

    • 任务要求
    • 参考答案
    • 评论2

    任务描述

    本关任务：要求从文件输入顶点和边数据，包括顶点信息、边、权值等，编写程序实现以下功能。 1）构造无向网G的邻接矩阵和顶点集，即图的存储结构为邻接矩阵。 2）输出无向网G的各顶点和邻接矩阵。 3）输出无向网G中顶点H的所有邻接顶点。

    相关知识

    图是表达“多对多”的关系的一种数据结构，由非空的有限顶点集合和有限边集合组成。将图的类型定义为枚举类型，在枚举值表中罗列：

    enum GraphKind{DG,DN,UDG,UDN}; // 有向图,有向网,无向图,无向网

    顶点集合

    每个顶点数据类型为VertexType，一个图的顶点集合用数组表示，数组下标表示顶点位置。数组内容包含顶点的信息，图的顶点集合的数据类型定义如下：

     

    1. #define MAX_VERTEX_NUM 20 // 最大顶点个数
    2. typedef char VertexType[16]; // 顶点类型
    3. VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量
     

    将顶点数据类型定义为长度为16的字符数组类型，可以将表示的城市名称存储在计算机中。
     

    边集合
     

    邻接矩阵是表示顶点之间相邻关系的矩阵。设G＝(V，E)是具有n顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：
     

     

    图及邻接矩阵
     

     

    网及邻接矩阵
     

    用邻接矩阵来表示一个具有n个顶点的图时，用邻接矩阵中的n×n个元素存储顶点间相邻关系，对于无权图，当邻接矩阵中的元素仅表示相应的边是否存在时，VRType可定义为值为0和1的枚举类型，0表示两个顶点之间没有边，即没有关系。对于带权图，则为权值，如果两个顶点之间没有边，则用一个很大很大的数代替∞。将顶点关系类型VRType定义为整型：
     

    typedef int VRType; // 顶点关系边的数据类型
     

    顶点关系边的数据类型类型，对于无权图，用1或0表示相邻否；对于带权图，则为权值。
     

    图的边集合的数据类型定义如下：
     

     

    1. #define INFINITY INT_MAX // 用整型最大值代替∞
    2. typedef struct
    3. {
    4. VRType adj; 
    5. } ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; 
     

    说明： AcrCell和AdjMatrix都是类型的名称，若有定义： AdjMatrix arcs; 则arcs是一个以元素类型为AcrCell的20*20二维数组。上述声明与下面等同： ArcCell arcs [MAX_VERTEX_NUM][MAX_VERTEX_NUM];
     

    图的邻接矩阵存储表示，类型定义如下：
     

     

    1. struct MGraph
    2. {
    3. VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量
    4. AdjMatrix arcs; // 邻接矩阵
    5. int vexnum, arcnum; // 图的当前顶点数和弧数
    6. GraphKind kind; // 图的种类标志
    7. };
     

    图的邻接矩阵表示法是图的一种顺序存储结构，优点是可以快速判断两个顶点之间是否存在边，可以快速添加边或者删除边，可以快速计算顶点度数、求邻接点的操作等；而其缺点是如果顶点之间的边比较少，会比较浪费空间。
     

    邻接矩阵具有如下性质： （1）图中各项点的序号确定后，图的邻接矩阵是唯一确定的； （2）无向图和无向网的邻接矩阵是一个对称矩阵； （3）无向图邻接矩阵中第i行(或第i列)的非0元素的个数即为第i个顶点的度； （4）有向图邻接矩阵中第i行非0元素的个数为第i个顶点的出度，第i列非0元素的个数为第i个顶点的入度，第i个顶点的度为第i行与第j非0元素个数之和； （5）无向图的边数等于邻接矩阵中非0元素个数之和的一半，有向图的弧数等于邻接矩阵中非0元素个数之和。
     

    编程要求
     

    根据提示，在右侧编辑器补充代码，要求从文件中输入顶点和边数据，包括顶点信息、边、权值等，编写函数实现图的基本运算：
     

     

    1. void CreateGraphF(MGraph &G);// 采用数组(邻接矩阵)表示法，由文件构造无向网G
    3. void Display(MGraph G); // 输出邻接矩阵存储表示的图G
    5. int LocateVex(MGraph G,VertexType u);//若G中存在顶点u，则返回该顶点在图中位置；否则返回-1 
    7. VertexType& GetVex(MGraph G,int v); // v是G中某个顶点的序号，返回v的值
    9. int FirstAdjVex(MGraph G,VertexType v);//v是图G中某个顶点，返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1 
    11. int NextAdjVex(MGraph G,VertexType v,VertexType w);//v是G中某个顶点，w是v的邻接顶点，返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1 
    13. void DestroyGraph(MGraph &G); // 销毁图G 
     

    测试说明
     

    平台会对你编写的代码进行测试：
     

    测试输入： 3 lt.txt  武汉
     

     
 
    输入说明： 第一行输入3，表示输入图的类型为无向网。 第二行输入文件名，该文件里保存了图的数据信息，内容如下： 6 9 武汉 上海 长沙 南京 成都 广州 武汉 长沙 9 武汉 成都 2 长沙 上海 2 长沙 南京 2 上海 南京 5 上海 广州 4 上海 成都 3 南京 广州 8 成都 广州 6
     

     

     
 
    第1行为图的顶点的个数n； 第2行为图的边的条数m； 第3行至第n+2行是n个顶点的数据； 第n+3行至第n+m+2行是m条边的数据； 最后输入一个顶点的数据
     

     

    预期输出： 无向网 6个顶点9条边。顶点依次是: 武汉 上海 长沙 南京 成都 广州  图的邻接矩阵: ∞ ∞ 9 ∞ 2 ∞  ∞ ∞ 2 5 ∞ ∞  9 2 ∞ 2 ∞ ∞  ∞ 5 2 ∞ ∞ ∞  2 ∞ ∞ ∞ ∞ ∞  ∞ ∞ ∞ ∞ ∞ ∞  长沙 成都
     

    1. #include 
    2. #include 
    3. #include
    4. #include 
    5.  
    6. typedef int VRType;    // 顶点关系类型 
    7. typedef char VertexType[20]; // 顶点类型 
    8. // 图的数组(邻接矩阵)存储表示 
    9. #define INFINITY INT_MAX // 用整型最大值代替∞ 
    10. #define MAX_VERTEX_NUM 20 // 最大顶点个数 
    11. typedef enum{DG,DN,UDG,UDN}GraphKind; // {有向图,有向网,无向图,无向网} 
    12.  
    13. typedef struct
    14. {
    15. 	VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；对带权图，则为权值 
    16. }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 二维数组 
    17.  
    18. typedef struct      // 图的数组(邻接矩阵)存储 
    19. {
    20. 	VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 
    21. 	AdjMatrix arcs; // 邻接矩阵 
    22. 	int vexnum,arcnum; // 图的当前顶点数和弧数 
    23. 	GraphKind kind; // 图的种类标志 
    24. }MGraph;  
    25.  
    26. void visit(VertexType i);
    27.  
    28. void CreateGraphF(MGraph &G);// 采用数组(邻接矩阵)表示法，由文件构造无向网G
    29. void Display(MGraph G);    // 输出邻接矩阵存储表示的图G
    30. int LocateVex(MGraph G,VertexType u);//若G中存在顶点u，则返回该顶点在图中位置；否则返回-1 
    31. VertexType* GetVex(MGraph G,int v);    // v是G中某个顶点的序号，返回v的值
    32. int FirstAdjVex(MGraph G,VertexType v);//v是图G中某个顶点，返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1 
    33. int NextAdjVex(MGraph G,VertexType v,VertexType w);//v是G中某个顶点，w是v的邻接顶点，返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1 
    34. void DestroyGraph(MGraph &G); // 销毁图G 
    35.  
    36.  
    37.  
    38.  
    39. int main()
    40. {
    41. 	MGraph g;
    42. 	VertexType v1,v2;
    43. 	CreateGraphF(g);      // 利用数据文件创建邻接矩阵表示的图	
    44. 	Display(g);           // 输出图  
    45. 	int i,j,k,n;
    46. 	//printf("请输入顶点的值: ");
    47. 	scanf("%s",v1);
    48. 	//printf("输出图G中顶点%s的所有邻接顶点: ",v1);
    49. 	k=FirstAdjVex(g,v1);
    50. 	while(k!=-1)
    51. 	{ 
    52. 		strcpy(v2, g.vexs[k] );
    53. 		visit(v2);
    54. 		k=NextAdjVex(g,v1,v2);
    55. 	}
    56. 	printf("\n");    
    57. 	return 0;
    58. }
    59.  
    60. void visit(VertexType i)
    61. {
    62. 	printf("%s ",i);
    63. }
    64.  
    65.  
    66. void CreateGraphF(MGraph &G)
    67. {
    68. 	// 采用数组(邻接矩阵)表示法，由文件构造无向网G
    69. 	/********** Begin **********/
    70. 	int i,j,k,w;
    71. 	char filename[13];
    72. 	VertexType va,vb;
    73. 	FILE * graphlist;
    74. 	scanf("%d",&G.kind);
    75. 	scanf("%s",filename);
    76. 	graphlist=fopen(filename,"r");
    77.  
    78. 	fscanf(graphlist,"%d",&G.vexnum);
    79. 	fscanf(graphlist,"%d",&G.arcnum);
    80. 	for(i=0;i
    81. 		fscanf(graphlist,"%s",G.vexs[i]);
    82. 	for(i=0;i
    83. 		for(j=0;j
    84. 			if(G.kind%2)
    85. 				G.arcs[i][j].adj=INFINITY;
    86. 			else
    87. 				G.arcs[i][j].adj=0;
    88. 		}
    89. 	for(k=0;k
    90. 		if(G.kind%2)
    91. 			fscanf(graphlist,"%s%s%d",va,vb,&w);
    92. 		else
    93. 			fscanf(graphlist,"%s%s",va,vb);
    94. 		i=LocateVex(G,va);
    95. 		j=LocateVex(G,vb);
    96. 		if(G.kind==0)
    97. 			G.arcs[i][j].adj=1;
    98. 		else if(G.kind==1)
    99. 			G.arcs[i][j].adj=w;
    100. 		else if(G.kind==2)
    101. 			G.arcs[i][j].adj=G.arcs[j][i].adj=1;
    102. 		else
    103. 			G.arcs[i][j].adj=G.arcs[j][i].adj=w;
    104. 	}
    105. 	fclose(graphlist);
    106. 	/********** End **********/
    107. }
    108.  
    109.  
    110. void Display(MGraph G)
    111. {
    112. 	// 输出邻接矩阵存储表示的图G
    113. 	/********** Begin **********/
    114. 	int i,j;
    115. 	switch(G.kind){
    116. 		case DG:printf("有向图\n");break;
    117. 		case DN:printf("有向网\n");break;
    118. 		case UDG:printf("无向图\n");break;
    119. 		case UDN:printf("无向网\n");
    120. 	}
    121.     printf("%d个顶点%d条边。顶点依次是: ",G.vexnum,G.arcnum);
    122. 	for(i=0;i
    123. 		printf("%s ",G.vexs[i]);
    124. 	printf("\n图的邻接矩阵:\n");
    125. 	for(i=0;i
    126. 		for(j=0;j
    127. 			if(G.kind%2){
    128. 				if(G.arcs[i][j].adj==INFINITY)
    129. 					printf("%s\t","∞");
    130. 				else
    131. 					printf("%d\t",G.arcs[i][j].adj);
    132. 			}else
    133. 				printf("%d\t",G.arcs[i][j].adj);
    134. 		printf("\n");
    135. 	}
    136. 	/********** End **********/
    137. }
    138.  
    139.  
    140. int LocateVex(MGraph G,VertexType u)
    141. {
    142. 	//初始条件：图G存在，u和G中顶点有相同特征
    143. 	// 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1 
    144. 	/********** Begin **********/
    145.     int i;
    146. 	for(i=0;i
    147. 		if(strcmp(u,G.vexs[i])==0) return i;
    148. 	return -1;  
    149. 	/********** Begin **********/
    150. }
    151.  
    152. VertexType* GetVex(MGraph G,int v)
    153. { 
    154. 	// 初始条件：图G存在，v是G中某个顶点的序号。操作结果：返回v的值
    155. 	/********** Begin **********/
    156. 	if(v>=G.vexnum || v<0)
    157. 		exit(0);
    158. 	return &(G.vexs[v]); 
    159. 	/********** End **********/
    160. }
    161.  
    162.  
    163.  
    164. int FirstAdjVex(MGraph G,VertexType v)
    165. {
    166.  	// 初始条件：图G存在，v是G中某个顶点 
    167. 	// 操作结果：返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1 
    168. 	/********** Begin **********/
    169. 	int i,j,k;
    170. 	if(G.kind%2)
    171. 		j=INFINITY;
    172. 	else
    173. 		j=0;
    174. 	k=LocateVex(G,v);
    175. 	for(i=0;i
    176. 		if(G.arcs[k][i].adj!=j)
    177. 			return i;
    178. 	return -1;
    179. 	/********** End **********/
    180. }
    181.  
    182. int NextAdjVex(MGraph G,VertexType v,VertexType w)
    183. {
    184. 	// 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点 
    185. 	// 操作结果：返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1 
    186. 	/********** Begin **********/
    187. 	int i,j,k1,k2;
    188. 	if(G.kind%2)
    189. 		j=INFINITY;
    190. 	else
    191. 		j=0;
    192. 	k1=LocateVex(G,v);
    193.  
    194. 	k2=LocateVex(G,w);
    195.  
    196. 	for(i=k2+1;i
    197. 		if(G.arcs[k1][i].adj!=j)
    198. 			return i;
    199. 	return -1;
    200. 	/********** End **********/
    201. }
    202.  
    203.  
    204. void DestroyGraph(MGraph &G)
    205. { // 初始条件：图G存在。操作结果：销毁图G 
    206. 	/********** Begin **********/
    207. 	int i,j,k=0;
    208. 	if(G.kind%2) 
    209. 		k=INFINITY; 
    210. 	G.vexnum=0; 
    211. 	G.arcnum=0; 
    212. 	/********** End **********/
    213. }
    214.  
     

     
 
    输出说明： 第一行输出图的类型。 第二行起输出图的顶点和边的数据信息。 最后一行输出输入顶点的所有邻接点。
     

    
                
    
                    
    
                
    • 

                
  • 

                    相关阅读:
    
                    
node的web编程                            
    
（C语言）成绩统计                            
    
CPSC认证是什么意思？CPSC主要测什么？                            
    
【Mycat】Mycat主从复制                            
    
在express中使用session认证                            
    
【POST请求-腾讯翻译君-爬虫案例】                            
    
QCSPCChart for Java R3x0 Crack                            
    
Unity技术手册 - 干扰/噪音/杂波（Noise）子模块                            
    
刷完HashMap源码，我们一起进大厂                            
    
2024Java springboot mybatis-flex 根据数据表时间开启定时任务                            
    
                        
                
    • 
                
  • 
                    原文地址：https://blog.csdn.net/toptopniba/article/details/134534404
                
    •