devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

头歌数据结构——图——课上课后练_头歌数据结构图课上课后练习

作者：从前慢现在也慢 | 2024-06-25 11:37:05

赞

踩

头歌数据结构图课上课后练习

第1关：图的邻接矩阵存储及图初始化

本关任务：根据下面的描述和要求，完成图的邻接矩阵数据结构定义，及图初始化函数。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define N  6
  4. #define MAX 100
  5. typedef struct {
  6. 	int vex;
  7. 	int shortweight;
  8. }ShortWeight;
  9. typedef struct QueueNode{
  10. 	int val;
  11. 	struct QueueNode* next;
  12. }QueueNode;
  13.  
  14. typedef struct Queue{
  15. 	QueueNode *head;
  16. 	QueueNode *tail;
  17. }Queue;
  18. //邻接矩阵数据结构 
  19. typedef  struct{
  20.    int vcount;//顶点数
  21.    int type ;//0 无向图，1 有向图
  22.    char  vexs[N]  ;     // 顶点信息
  23.    int  arcs[N][N]; //关系矩阵
  24. } GraphMatrix;
  25.  
  26. //邻接表数据结构
  27. struct EdgeNode { //边表中的结点
  28.       int  endvex;    //相邻顶点在顶点表中下标
  29.       int  weight;  //边的权
  30.       struct EdgeNode  * nextedge;   //链字段
  31. };   
  32. typedef struct EdgeNode * EdgeList;
  33.  
  34. typedef struct
  35. {
  36.    char  vertex;  //记录顶点信息
  37.    int degree;//用于记录顶点的入度，在拓扑排序时需使用
  38.    EdgeList  edgelist;  //指向边表的指针
  39. } VexNode; 
  40. typedef struct{
  41.    VexNode  *vexs[N];  //N个顶点
  42.    int type ;//0 无向图，1 有向图
  43.    int vcount;//顶点数
  44. } GraphList; 
  45.  
  46. /*第一关 完成图初始化
  47. */
  48. void printGraph(GraphMatrix *G)
  49. {//本函数输出图的邻接矩阵
  50.  int i,j;
  51.  for(i=0;i<G->vcount;i++)
  52.  {
  53. //  printf("%c ",G->vexs[i]);
  54.   for( j=0;j<G->vcount;j++)
  55.      printf("%d ",G->arcs[i][j]);
  56.   printf("\n");
  57.  }
  58. }
  59.  
  60. /*第一关 完成图初始化-邻接矩阵
  61. */
  62. GraphMatrix *initGraphMatrix( )
  63. {
  64.   /*第一行输入图的类型、图的顶点数和边数，第二行输入各条边的两顶点的编号，按顶点编号从小到大的顺序输入。
  65. 输出邻接矩阵，不需要考虑输入的数字非法情况，不输入顶点的信息*/
  66.    GraphMatrix *G;
  67.    G=(GraphMatrix *)malloc(sizeof(GraphMatrix));
  68.    int t,v,s;
  69.    scanf("%d %d %d",&t,&v,&s);
  70.    G->vcount=v;
  71.    G->type=t;
  72.    int i,j;
  73.    for(i=0;i<N;i++){
  74.       for(j=0;j<N;j++){
  75.          G->arcs[i][j]=0;
  76.       }
  77.    }
  78.    int head,tail;
  79.    if(t==0)
  80.       for(i=0;i<N;i++){
  81.          scanf("%d %d",&head,&tail);
  82.          G->arcs[head][tail]=1;
  83.          G->arcs[tail][head]=1;
  84.       }
  85.    if(t==1){
  86.       for(i=0;i<N;i++){
  87.          scanf("%d %d",&head,&tail);
  88.          G->arcs[head][tail]=1;
  89.       }
  90.    }
  91.    return G;
  92. }
  93. /*第二关 完成图初始化-邻接表,并完成输出图的邻接表函数
  94. */
  95. GraphList* initGraphList()
  96. {
  97. 	/*第一行输入图的类型、图的顶点数和边数，第二行输入各条边的两顶点的编号，按顶点编号从小到大的顺序输入。
  98.   输出邻接表。不需考虑输入的数字非法情况，输入顶点的信息*/
  99. 	GraphList* G = (GraphList*)malloc(sizeof(GraphList));
  100. 	int t, v, s;
  101. 	scanf("%d%d%d", &t, &v, &s);
  102. 	G->vcount = v;
  103. 	G->type = t;
  104. 	int i, j, k, l;
  105. 	char vex[N];
  106. 	char ch = getchar();
  107. 	for (i = 0; i < v; i++) {
  108. 		scanf("%c", &vex[i]);
  109. 	}
  110. 	for (i = 0; i < v; i++) {
  111. 		G->vexs[i] = (VexNode*)malloc(sizeof(VexNode));
  112. 		G->vexs[i]->vertex = vex[i];
  113. 		G->vexs[i]->edgelist = (EdgeList)malloc(sizeof(struct EdgeNode));
  114. 		G->vexs[i]->edgelist->nextedge = NULL;
  115. 	}
  116. 	for (i = 0; i < s; i++) {
  117. 		int head, tail,w;
  118. 		scanf("%d %d %d", &head, &tail,&w);
  119. 		if (t == 0) {
  120. 			for (k = 0; k < v; k++) {
  121. 				if (G->vexs[k]->vertex - '0' == head) {
  122. 					EdgeList node1 = (EdgeList)malloc(sizeof(struct EdgeNode));
  123. 					for (j = 0; j < v; j++) {
  124. 						if (vex[j] - '0' == tail) {
  125. 							node1->weight = w;
  126. 							node1->endvex = j;
  127. 							node1->nextedge = G->vexs[k]->edgelist->nextedge;
  128. 							G->vexs[k]->edgelist->nextedge = node1;
  129. 							break;
  130. 						}
  131. 					}
  132. 					for (j = 0; j < v; j++) {
  133. 						if (G->vexs[j]->vertex - '0' == tail) {
  134. 							EdgeList node2 = (EdgeList)malloc(sizeof(struct EdgeNode));
  135. 							for (l = 0; l < v; l++) {
  136. 								if (vex[l] - '0' == head) {
  137. 									node2->weight = w;
  138. 									node2->endvex = l;
  139. 									node2->nextedge = G->vexs[j]->edgelist->nextedge;
  140. 									G->vexs[j]->edgelist->nextedge = node2;
  141. 									break;
  142. 								}
  143. 							}
  144. 						}
  145. 					}
  146. 				}
  147.  
  148.  
  149. 			}
  150. 		}
  151. 	}
  152. 	return G;
  153. }
  154. void printGraphLit( GraphList *G)
  155. {
  156.  /*输出邻接表，输出格式：顶点->邻接顶点编号->...*/
  157.     int i;
  158. 	for(i=0;i<G->vcount;i++){
  159. 		printf("%c->",G->vexs[i]->vertex);
  160. 		EdgeList tp=G->vexs[i]->edgelist->nextedge;
  161. 		while(tp->nextedge!=NULL){
  162. 			printf("%d->",tp->endvex);
  163. 			tp=tp->nextedge;
  164. 		}
  165. 		printf("%d\n",tp->endvex);
  166. 	}
  167. }
  168. /*第三关 完成图的广度遍历（周游），可根据需要添加自定义函数
  169. */
  170. int visited[N]={0};
  171. void BFS_list(GraphList *G)
  172. {
  173. 	int i,j;
  174. 	printf("%c ",G->vexs[0]->vertex);
  175. 	visited[0]=1;
  176. 	EdgeList tp=G->vexs[i]->edgelist->nextedge;
  177. 	while(tp->nextedge!=NULL){
  178. 		printf("%d ",tp->endvex);
  179. 		visited[tp->endvex]=1;
  180. 		tp=tp->nextedge;
  181. 	}
  182. 	printf("%d ",tp->endvex);
  183. 	visited[tp->endvex]=1;
  184. 	for(i=N-1;i>=0;i--){
  185. 		if(visited[i]==1){
  186. 			EdgeList tp=G->vexs[i]->edgelist->nextedge;
  187. 			while(tp->nextedge!=NULL && visited[tp->endvex]==0){
  188. 			printf("%d ",tp->endvex);
  189. 			visited[tp->endvex]=1;
  190. 			tp=tp->nextedge;
  191. 			}
  192. 		}
  193. 	}
  194. 	
  195. }
  196. /*第四关 完成图的深度遍历（周游），可根据需要添加自定义函数
  197. */
  198. int visited2[N];
  199. void DFS_list(GraphList *G)
  200. {
  201. 	int i,j,k;
  202. 	for(i=0;i<N;i++){
  203. 		visited2[i]=0;
  204. 	}
  205. 	printf("%c ",G->vexs[0]->vertex);
  206. 	visited2[0]=1;
  207. 	EdgeList tp=G->vexs[0]->edgelist->nextedge;
  208. 	printf("%d ",tp->endvex);
  209. 	visited2[tp->endvex]=1;
  210. 	int num=4;
  211. 	while(1){
  212. 		for(i=0;i<G->vcount;i++){
  213. 			if(G->vexs[i]->vertex-'0'==tp->endvex){
  214. 				EdgeList tp2=G->vexs[i]->edgelist->nextedge;
  215. 				if(visited2[tp2->endvex]==0){
  216. 					tp=tp2;
  217. 					printf("%d ",tp2->endvex);
  218. 					visited2[tp2->endvex]=1;
  219. 					break;
  220. 				}
  221. 				else if(visited2[tp2->endvex]==1){
  222. 					for(tp2=tp2->nextedge;tp2!=NULL;tp2=tp2->nextedge){
  223. 						if(visited2[tp2->endvex]==0){
  224. 							tp=tp2;
  225. 							printf("%d ",tp2->endvex);
  226. 							visited2[tp2->endvex]=1;
  227. 							break;
  228. 						}
  229. 					}
  230. 					
  231. 				}
  232. 				
  233. 			}
  234. 		}
  235. 		int count=0;
  236. 		for(i=0;i<N;i++){
  237. 			if(visited2[i]==1) count++;
  238. 		}
  239. 		if(count==G->vcount) break;
  240. 	}
  241. 	
  242. }
  243. /*第五关 生成图的拓扑排序，可根据需要添加自定义函数
  244. */
  245. void QueueInit(Queue* pq) {
  246. 	pq->head = pq->tail = NULL;
  247. }
  248. void QueuePush(Queue* pq, int x) {
  249. 	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  250. 	newnode->val = x;
  251. 	newnode->next = NULL;
  252. 	if (pq->tail == NULL) {
  253. 		pq->head = pq->tail = newnode;
  254. 	}
  255. 	else {
  256. 		pq->tail->next = newnode;
  257. 		pq->tail = newnode;
  258. 	}
  259. }
  260. void QueuePop(Queue* pq) {
  261. 	if (pq->head->next == NULL) {
  262. 		pq->head = pq->tail = NULL;
  263. 	}
  264. 	else {
  265. 		QueueNode* next = pq->head->next;
  266. 		pq->head = next;
  267. 	}
  268. }
  269. int QueueFront(Queue* pq) {
  270. 	return pq->head->val;
  271. }
  272. int QueueEmpty(Queue* pq) {
  273. 	return pq->head == NULL;
  274. }
  275. void Top_list(GraphList* G)
  276. {
  277. 	Queue* Q=(Queue *)malloc(sizeof(Queue));
  278. 	QueueInit(Q);
  279. 	int i;
  280. 	int deg[N];
  281. 	for (i = 0; i < N; i++) {
  282. 		deg[i] = 0;
  283. 	}
  284. 	for (i = 0; i < N; i++) {
  285. 		deg[i] = G->vexs[i]->degree;
  286. 	}
  287.  
  288. 	for (i = 0; i < N; i++) {
  289. 		if (deg[i] == 0) {
  290. 			QueuePush(Q, i);
  291. 		}
  292. 	}
  293. 	while (!QueueEmpty(Q)) {
  294. 		int j = QueueFront(Q);
  295. 		printf("%d ", j);
  296. 		QueuePop(Q);
  297. 		EdgeList p;
  298. 		p = G->vexs[j]->edgelist->nextedge;
  299. 		while (p != NULL) {
  300. 			deg[p->endvex]--;
  301. 			if (deg[p->endvex] == 0) {
  302. 				QueuePush(Q, p->endvex);
  303. 			}
  304. 			p = p->nextedge;
  305. 		}
  306. 	}
  307. }
  308. /*第六关 prim算法生成最小生成树
  309. */
  310. int GetShortWeight(GraphList* G,ShortWeight *shortw) {
  311. 	int i;
  312. 	int min = MAX;
  313. 	int loc;
  314. 	for (i = 1; i < G->vcount; i++) {
  315. 		if (min > shortw[i].shortweight && shortw[i].shortweight != 0) {
  316. 			min = shortw[i].shortweight;
  317. 			loc = i;
  318. 		}
  319. 	}
  320. 	return loc;
  321. }
  322.  
  323. void Prim_list(GraphList* G)
  324. {
  325. 	int i, j, k;
  326. 	ShortWeight shortw[10];
  327. 	for (i = 0; i < 10; i++) {
  328. 		shortw[i].shortweight = MAX;
  329. 	}
  330. 	k = 0;
  331. 	EdgeList tp = G->vexs[k]->edgelist->nextedge;
  332. 	while (tp) {
  333. 		shortw[tp->endvex].shortweight= tp->weight;
  334. 		shortw[tp->endvex].vex = k;
  335. 		tp = tp->nextedge;
  336. 	}
  337. 	shortw[k].shortweight = 0;
  338. 	for (i = 0; i < G->vcount - 1; i++) {
  339. 		k = GetShortWeight(G, shortw);
  340. 		printf("%d %d\n", shortw[k].vex, k);
  341. 		shortw[k].shortweight = 0;
  342. 		EdgeList tp2 = G->vexs[k]->edgelist->nextedge;
  343. 			while (tp2) {
  344. 				if (tp2->weight < shortw[tp2->endvex].shortweight) {
  345. 					shortw[tp2->endvex].shortweight = tp2->weight;
  346. 					shortw[tp2->endvex].vex = k;
  347. 				}
  348. 				tp2 = tp2->nextedge;
  349. 			}
  350. 	}
  351. }
  352. /*第七关 Kruskal算法生成最小生成树
  353. */
  354.  
  355. void Kruskal_list(GraphList *G)
  356. {
  357.  
  358.  
  359. }
  360.  
  361. /*第八关 Dijistra算法求最短路径
  362. */
  363.  
  364. void Dijkstra_list(GraphList *G)
  365. {
  366.  
  367.  
  368. }

第2关：图的邻接表存储及图初始化

本关任务：编写一个能输入图的基本信息（含图的类型，图的顶点，边等），并用邻接表存储图的程序。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define N  6
  4. #define MAX 100
  5. typedef struct {
  6. 	int vex;
  7. 	int shortweight;
  8. }ShortWeight;
  9. typedef struct QueueNode{
  10. 	int val;
  11. 	struct QueueNode* next;
  12. }QueueNode;
  13.  
  14. typedef struct Queue{
  15. 	QueueNode *head;
  16. 	QueueNode *tail;
  17. }Queue;
  18. //邻接矩阵数据结构 
  19. typedef  struct{
  20.    int vcount;//顶点数
  21.    int type ;//0 无向图，1 有向图
  22.    char  vexs[N]  ;     // 顶点信息
  23.    int  arcs[N][N]; //关系矩阵
  24. } GraphMatrix;
  25.  
  26. //邻接表数据结构
  27. struct EdgeNode { //边表中的结点
  28.       int  endvex;    //相邻顶点在顶点表中下标
  29.       int  weight;  //边的权
  30.       struct EdgeNode  * nextedge;   //链字段
  31. };   
  32. typedef struct EdgeNode * EdgeList;
  33.  
  34. typedef struct
  35. {
  36.    char  vertex;  //记录顶点信息
  37.    int degree;//用于记录顶点的入度，在拓扑排序时需使用
  38.    EdgeList  edgelist;  //指向边表的指针
  39. } VexNode; 
  40. typedef struct{
  41.    VexNode  *vexs[N];  //N个顶点
  42.    int type ;//0 无向图，1 有向图
  43.    int vcount;//顶点数
  44. } GraphList; 
  45. /*第二关 完成图初始化-邻接表,并完成输出图的邻接表函数
  46. */
  47. GraphList *initGraphList()
  48. {
  49.   /*第一行输入图的类型、图的顶点数和边数，第二行输入各条边的两顶点的编号，按顶点编号从小到大的顺序输入。
  50. 输出邻接表。不需考虑输入的数字非法情况，输入顶点的信息*/
  51.  GraphList *G=(GraphList*)malloc(sizeof(GraphList));
  52.  int t,v,s;
  53.  scanf("%d%d%d",&t,&v,&s);
  54.  G->vcount=v;
  55.  G->type=t;
  56.  int i,j,k,l;
  57.  char vex[N];
  58.  char ch=getchar();
  59.  for(i=0;i<v;i++){
  60.  	scanf("%c",&vex[i]);
  61.  }
  62.  for(i=0;i<v;i++){
  63.  	G->vexs[i]=(VexNode *)malloc(sizeof(VexNode));
  64.  	G->vexs[i]->vertex=vex[i];
  65.  	G->vexs[i]->edgelist=(EdgeList)malloc(sizeof(struct EdgeNode));
  66.  	G->vexs[i]->edgelist->nextedge=NULL;
  67.  	G->vexs[i]->degree=0;
  68.  }
  69.  for(i=0;i<s;i++){
  70. 	int head,tail;
  71. 	scanf("%d %d",&head,&tail);
  72. 	if(t==0){
  73. 		for(k=0;k<v;k++){
  74. 			if(G->vexs[k]->vertex-'0'==head){
  75. 				EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
  76. 				for(j=0;j<v;j++){
  77. 					if(vex[j]-'0'==tail){
  78. 						node1->endvex=j;
  79. 						node1->nextedge=G->vexs[k]->edgelist->nextedge;
  80. 						G->vexs[k]->edgelist->nextedge=node1;
  81. 						break;
  82. 					}
  83. 				}
  84. 				for(j=0;j<v;j++){
  85. 					if(G->vexs[j]->vertex-'0'==tail){
  86. 						EdgeList node2=(EdgeList)malloc(sizeof(struct EdgeNode));
  87. 						for(l=0;l<v;l++){
  88. 							if(vex[l]-'0'==head){
  89. 								node2->endvex=l;
  90. 								node2->nextedge=G->vexs[j]->edgelist->nextedge;
  91. 								G->vexs[j]->edgelist->nextedge=node2;
  92. 								break;
  93. 							}
  94. 						}
  95. 					}
  96. 				}
  97. 			}
  98. 			
  99. 		
  100. 		}
  101. 	} 
  102. 	else if(t==1){
  103. 		for(k=0;k<v;k++){
  104. 			if(G->vexs[k]->vertex-'0'==head){
  105. 				EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
  106. 				for(j=0;j<v;j++){
  107. 					if(vex[j]-'0'==tail){
  108. 						for(l=0;l<G->vcount;l++){
  109. 							if(G->vexs[l]->vertex-'0'==tail){
  110. 								G->vexs[l]->degree++;
  111. 							}
  112. 						}
  113. 						node1->endvex=j;
  114. 						node1->nextedge=G->vexs[k]->edgelist->nextedge;
  115. 						G->vexs[k]->edgelist->nextedge=node1; 
  116. 						break;
  117. 					}
  118. 				}
  119. 			}
  120. 		}
  121. 	
  122.  	}
  123.  }
  124.  return G;
  125. }
  126. void printGraphLit( GraphList *G)
  127. {
  128.  /*输出邻接表，输出格式：顶点->邻接顶点编号->...*/
  129.     int i;
  130. 	for(i=0;i<G->vcount;i++){
  131. 		printf("%c->",G->vexs[i]->vertex);
  132. 		EdgeList tp=G->vexs[i]->edgelist->nextedge;
  133. 		while(tp->nextedge!=NULL){
  134. 			printf("%d->",tp->endvex);
  135. 			tp=tp->nextedge;
  136. 		}
  137. 		printf("%d\n",tp->endvex);
  138. 	}
  139. }

第3关：图的广度遍历

本关任务：完成程序能实现图的广度遍历。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define N  6
  4. #define MAX 100
  5. typedef struct {
  6. 	int vex;
  7. 	int shortweight;
  8. }ShortWeight;
  9. typedef struct QueueNode{
  10. 	int val;
  11. 	struct QueueNode* next;
  12. }QueueNode;
  13.  
  14. typedef struct Queue{
  15. 	QueueNode *head;
  16. 	QueueNode *tail;
  17. }Queue;
  18. //邻接矩阵数据结构 
  19. typedef  struct{
  20.    int vcount;//顶点数
  21.    int type ;//0 无向图，1 有向图
  22.    char  vexs[N]  ;     // 顶点信息
  23.    int  arcs[N][N]; //关系矩阵
  24. } GraphMatrix;
  25.  
  26. //邻接表数据结构
  27. struct EdgeNode { //边表中的结点
  28.       int  endvex;    //相邻顶点在顶点表中下标
  29.       int  weight;  //边的权
  30.       struct EdgeNode  * nextedge;   //链字段
  31. };   
  32. typedef struct EdgeNode * EdgeList;
  33.  
  34. typedef struct
  35. {
  36.    char  vertex;  //记录顶点信息
  37.    int degree;//用于记录顶点的入度，在拓扑排序时需使用
  38.    EdgeList  edgelist;  //指向边表的指针
  39. } VexNode; 
  40. typedef struct{
  41.    VexNode  *vexs[N];  //N个顶点
  42.    int type ;//0 无向图，1 有向图
  43.    int vcount;//顶点数
  44. } GraphList; 
  45. /*第一关 完成图初始化-邻接矩阵
  46. */
  47. GraphMatrix *initGraphMatrix( )
  48. {
  49.   /*第一行输入图的类型、图的顶点数和边数，第二行输入各条边的两顶点的编号，按顶点编号从小到大的顺序输入。
  50. 输出邻接矩阵，不需要考虑输入的数字非法情况，不输入顶点的信息*/
  51.    GraphMatrix *G;
  52.    G=(GraphMatrix *)malloc(sizeof(GraphMatrix));
  53.    int t,v,s;
  54.    scanf("%d %d %d",&t,&v,&s);
  55.    G->vcount=v;
  56.    G->type=t;
  57.    int i,j;
  58.    for(i=0;i<N;i++){
  59.       for(j=0;j<N;j++){
  60.          G->arcs[i][j]=0;
  61.       }
  62.    }
  63.    int head,tail;
  64.    if(t==0)
  65.       for(i=0;i<N;i++){
  66.          scanf("%d %d",&head,&tail);
  67.          G->arcs[head][tail]=1;
  68.          G->arcs[tail][head]=1;
  69.       }
  70.    if(t==1){
  71.       for(i=0;i<N;i++){
  72.          scanf("%d %d",&head,&tail);
  73.          G->arcs[head][tail]=1;
  74.       }
  75.    }
  76.    return G;
  77. }
  78. /*第二关 完成图初始化-邻接表,并完成输出图的邻接表函数
  79. */
  80. GraphList *initGraphList()
  81. {
  82.   /*第一行输入图的类型、图的顶点数和边数，第二行输入各条边的两顶点的编号，按顶点编号从小到大的顺序输入。
  83. 输出邻接表。不需考虑输入的数字非法情况，输入顶点的信息*/
  84.  GraphList *G=(GraphList*)malloc(sizeof(GraphList));
  85.  int t,v,s;
  86.  scanf("%d%d%d",&t,&v,&s);
  87.  G->vcount=v;
  88.  G->type=t;
  89.  int i,j,k,l;
  90.  char vex[N];
  91.  char ch=getchar();
  92.  for(i=0;i<v;i++){
  93.  	scanf("%c",&vex[i]);
  94.  }
  95.  for(i=0;i<v;i++){
  96.  	G->vexs[i]=(VexNode *)malloc(sizeof(VexNode));
  97.  	G->vexs[i]->vertex=vex[i];
  98.  	G->vexs[i]->edgelist=(EdgeList)malloc(sizeof(struct EdgeNode));
  99.  	G->vexs[i]->edgelist->nextedge=NULL;
  100.  	G->vexs[i]->degree=0;
  101.  }
  102.  for(i=0;i<s;i++){
  103. 	int head,tail;
  104. 	scanf("%d %d",&head,&tail);
  105. 	if(t==0){
  106. 		for(k=0;k<v;k++){
  107. 			if(G->vexs[k]->vertex-'0'==head){
  108. 				EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
  109. 				for(j=0;j<v;j++){
  110. 					if(vex[j]-'0'==tail){
  111. 						node1->endvex=j;
  112. 						node1->nextedge=G->vexs[k]->edgelist->nextedge;
  113. 						G->vexs[k]->edgelist->nextedge=node1;
  114. 						break;
  115. 					}
  116. 				}
  117. 				for(j=0;j<v;j++){
  118. 					if(G->vexs[j]->vertex-'0'==tail){
  119. 						EdgeList node2=(EdgeList)malloc(sizeof(struct EdgeNode));
  120. 						for(l=0;l<v;l++){
  121. 							if(vex[l]-'0'==head){
  122. 								node2->endvex=l;
  123. 								node2->nextedge=G->vexs[j]->edgelist->nextedge;
  124. 								G->vexs[j]->edgelist->nextedge=node2;
  125. 								break;
  126. 							}
  127. 						}
  128. 					}
  129. 				}
  130. 			}
  131. 			
  132. 		
  133. 		}
  134. 	} 
  135. 	else if(t==1){
  136. 		for(k=0;k<v;k++){
  137. 			if(G->vexs[k]->vertex-'0'==head){
  138. 				EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
  139. 				for(j=0;j<v;j++){
  140. 					if(vex[j]-'0'==tail){
  141. 						for(l=0;l<G->vcount;l++){
  142. 							if(G->vexs[l]->vertex-'0'==tail){
  143. 								G->vexs[l]->degree++;
  144. 							}
  145. 						}
  146. 						node1->endvex=j;
  147. 						node1->nextedge=G->vexs[k]->edgelist->nextedge;
  148. 						G->vexs[k]->edgelist->nextedge=node1; 
  149. 						break;
  150. 					}
  151. 				}
  152. 			}
  153. 		}
  154. 	
  155.  	}
  156.  }
  157.  return G;
  158. }
  159. void printGraphLit( GraphList *G)
  160. {
  161.  /*输出邻接表，输出格式：顶点->邻接顶点编号->...*/
  162.     int i;
  163. 	for(i=0;i<G->vcount;i++){
  164. 		printf("%c->",G->vexs[i]->vertex);
  165. 		EdgeList tp=G->vexs[i]->edgelist->nextedge;
  166. 		while(tp->nextedge!=NULL){
  167. 			printf("%d->",tp->endvex);
  168. 			tp=tp->nextedge;
  169. 		}
  170. 		printf("%d\n",tp->endvex);
  171. 	}
  172. }
  173. /*第三关 完成图的广度遍历（周游），可根据需要添加自定义函数
  174. */
  175. int visited[N]={0};
  176. void BFS_list(GraphList *G)
  177. {
  178. 	int i,j;
  179. 	printf("%c ",G->vexs[0]->vertex);
  180. 	visited[0]=1;
  181. 	EdgeList tp=G->vexs[i]->edgelist->nextedge;
  182. 	while(tp->nextedge!=NULL){
  183. 		printf("%d ",tp->endvex);
  184. 		visited[tp->endvex]=1;
  185. 		tp=tp->nextedge;
  186. 	}
  187. 	printf("%d ",tp->endvex);
  188. 	visited[tp->endvex]=1;
  189. 	for(i=N-1;i>=0;i--){
  190. 		if(visited[i]==1){
  191. 			EdgeList tp=G->vexs[i]->edgelist->nextedge;
  192. 			while(tp->nextedge!=NULL && visited[tp->endvex]==0){
  193. 			printf("%d ",tp->endvex);
  194. 			visited[tp->endvex]=1;
  195. 			tp=tp->nextedge;
  196. 			}
  197. 		}
  198. 	}
  199. 	
  200. }

第4关：图的深度遍历

本关任务：完成程序能实现图的深度遍历。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define N  6
  4. #define MAX 100
  5. typedef struct {
  6. 	int vex;
  7. 	int shortweight;
  8. }ShortWeight;
  9. typedef struct QueueNode{
  10. 	int val;
  11. 	struct QueueNode* next;
  12. }QueueNode;
  13.  
  14. typedef struct Queue{
  15. 	QueueNode *head;
  16. 	QueueNode *tail;
  17. }Queue;
  18. //邻接矩阵数据结构 
  19. typedef  struct{
  20.    int vcount;//顶点数
  21.    int type ;//0 无向图，1 有向图
  22.    char  vexs[N]  ;     // 顶点信息
  23.    int  arcs[N][N]; //关系矩阵
  24. } GraphMatrix;
  25.  
  26. //邻接表数据结构
  27. struct EdgeNode { //边表中的结点
  28.       int  endvex;    //相邻顶点在顶点表中下标
  29.       int  weight;  //边的权
  30.       struct EdgeNode  * nextedge;   //链字段
  31. };   
  32. typedef struct EdgeNode * EdgeList;
  33.  
  34. typedef struct
  35. {
  36.    char  vertex;  //记录顶点信息
  37.    int degree;//用于记录顶点的入度，在拓扑排序时需使用
  38.    EdgeList  edgelist;  //指向边表的指针
  39. } VexNode; 
  40. typedef struct{
  41.    VexNode  *vexs[N];  //N个顶点
  42.    int type ;//0 无向图，1 有向图
  43.    int vcount;//顶点数
  44. } GraphList; 
  45. /*第一关 完成图初始化-邻接矩阵
  46. */
  47. GraphMatrix *initGraphMatrix( )
  48. {
  49.   /*第一行输入图的类型、图的顶点数和边数，第二行输入各条边的两顶点的编号，按顶点编号从小到大的顺序输入。
  50. 输出邻接矩阵，不需要考虑输入的数字非法情况，不输入顶点的信息*/
  51.    GraphMatrix *G;
  52.    G=(GraphMatrix *)malloc(sizeof(GraphMatrix));
  53.    int t,v,s;
  54.    scanf("%d %d %d",&t,&v,&s);
  55.    G->vcount=v;
  56.    G->type=t;
  57.    int i,j;
  58.    for(i=0;i<N;i++){
  59.       for(j=0;j<N;j++){
  60.          G->arcs[i][j]=0;
  61.       }
  62.    }
  63.    int head,tail;
  64.    if(t==0)
  65.       for(i=0;i<N;i++){
  66.          scanf("%d %d",&head,&tail);
  67.          G->arcs[head][tail]=1;
  68.          G->arcs[tail][head]=1;
  69.       }
  70.    if(t==1){
  71.       for(i=0;i<N;i++){
  72.          scanf("%d %d",&head,&tail);
  73.          G->arcs[head][tail]=1;
  74.       }
  75.    }
  76.    return G;
  77. }
  78. /*第二关 完成图初始化-邻接表,并完成输出图的邻接表函数
  79. */
  80. GraphList *initGraphList()
  81. {
  82.   /*第一行输入图的类型、图的顶点数和边数，第二行输入各条边的两顶点的编号，按顶点编号从小到大的顺序输入。
  83. 输出邻接表。不需考虑输入的数字非法情况，输入顶点的信息*/
  84.  GraphList *G=(GraphList*)malloc(sizeof(GraphList));
  85.  int t,v,s;
  86.  scanf("%d%d%d",&t,&v,&s);
  87.  G->vcount=v;
  88.  G->type=t;
  89.  int i,j,k,l;
  90.  char vex[N];
  91.  char ch=getchar();
  92.  for(i=0;i<v;i++){
  93.  	scanf("%c",&vex[i]);
  94.  }
  95.  for(i=0;i<v;i++){
  96.  	G->vexs[i]=(VexNode *)malloc(sizeof(VexNode));
  97.  	G->vexs[i]->vertex=vex[i];
  98.  	G->vexs[i]->edgelist=(EdgeList)malloc(sizeof(struct EdgeNode));
  99.  	G->vexs[i]->edgelist->nextedge=NULL;
  100.  	G->vexs[i]->degree=0;
  101.  }
  102.  for(i=0;i<s;i++){
  103. 	int head,tail;
  104. 	scanf("%d %d",&head,&tail);
  105. 	if(t==0){
  106. 		for(k=0;k<v;k++){
  107. 			if(G->vexs[k]->vertex-'0'==head){
  108. 				EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
  109. 				for(j=0;j<v;j++){
  110. 					if(vex[j]-'0'==tail){
  111. 						node1->endvex=j;
  112. 						node1->nextedge=G->vexs[k]->edgelist->nextedge;
  113. 						G->vexs[k]->edgelist->nextedge=node1;
  114. 						break;
  115. 					}
  116. 				}
  117. 				for(j=0;j<v;j++){
  118. 					if(G->vexs[j]->vertex-'0'==tail){
  119. 						EdgeList node2=(EdgeList)malloc(sizeof(struct EdgeNode));
  120. 						for(l=0;l<v;l++){
  121. 							if(vex[l]-'0'==head){
  122. 								node2->endvex=l;
  123. 								node2->nextedge=G->vexs[j]->edgelist->nextedge;
  124. 								G->vexs[j]->edgelist->nextedge=node2;
  125. 								break;
  126. 							}
  127. 						}
  128. 					}
  129. 				}
  130. 			}
  131. 			
  132. 		
  133. 		}
  134. 	} 
  135. 	else if(t==1){
  136. 		for(k=0;k<v;k++){
  137. 			if(G->vexs[k]->vertex-'0'==head){
  138. 				EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
  139. 				for(j=0;j<v;j++){
  140. 					if(vex[j]-'0'==tail){
  141. 						for(l=0;l<G->vcount;l++){
  142. 							if(G->vexs[l]->vertex-'0'==tail){
  143. 								G->vexs[l]->degree++;
  144. 							}
  145. 						}
  146. 						node1->endvex=j;
  147. 						node1->nextedge=G->vexs[k]->edgelist->nextedge;
  148. 						G->vexs[k]->edgelist->nextedge=node1; 
  149. 						break;
  150. 					}
  151. 				}
  152. 			}
  153. 		}
  154. 	
  155.  	}
  156.  }
  157.  return G;
  158. }
  159. void printGraphLit( GraphList *G)
  160. {
  161.  /*输出邻接表，输出格式：顶点->邻接顶点编号->...*/
  162.     int i;
  163. 	for(i=0;i<G->vcount;i++){
  164. 		printf("%c->",G->vexs[i]->vertex);
  165. 		EdgeList tp=G->vexs[i]->edgelist->nextedge;
  166. 		while(tp->nextedge!=NULL){
  167. 			printf("%d->",tp->endvex);
  168. 			tp=tp->nextedge;
  169. 		}
  170. 		printf("%d\n",tp->endvex);
  171. 	}
  172. }
  173. /*第三关 完成图的广度遍历（周游），可根据需要添加自定义函数
  174. */
  175. int visited[N]={0};
  176. void BFS_list(GraphList *G)
  177. {
  178. 	int i,j;
  179. 	printf("%c ",G->vexs[0]->vertex);
  180. 	visited[0]=1;
  181. 	EdgeList tp=G->vexs[i]->edgelist->nextedge;
  182. 	while(tp->nextedge!=NULL){
  183. 		printf("%d ",tp->endvex);
  184. 		visited[tp->endvex]=1;
  185. 		tp=tp->nextedge;
  186. 	}
  187. 	printf("%d ",tp->endvex);
  188. 	visited[tp->endvex]=1;
  189. 	for(i=N-1;i>=0;i--){
  190. 		if(visited[i]==1){
  191. 			EdgeList tp=G->vexs[i]->edgelist->nextedge;
  192. 			while(tp->nextedge!=NULL && visited[tp->endvex]==0){
  193. 			printf("%d ",tp->endvex);
  194. 			visited[tp->endvex]=1;
  195. 			tp=tp->nextedge;
  196. 			}
  197. 		}
  198. 	}
  199. 	
  200. }
  201. /*第四关 完成图的深度遍历（周游），可根据需要添加自定义函数
  202. */
  203. int visited2[N];
  204. void DFS_list(GraphList *G)
  205. {
  206. 	int i,j,k;
  207. 	for(i=0;i<N;i++){
  208. 		visited2[i]=0;
  209. 	}
  210. 	printf("%c ",G->vexs[0]->vertex);
  211. 	visited2[0]=1;
  212. 	EdgeList tp=G->vexs[0]->edgelist->nextedge;
  213. 	printf("%d ",tp->endvex);
  214. 	visited2[tp->endvex]=1;
  215. 	int num=4;
  216. 	while(1){
  217. 		for(i=0;i<G->vcount;i++){
  218. 			if(G->vexs[i]->vertex-'0'==tp->endvex){
  219. 				EdgeList tp2=G->vexs[i]->edgelist->nextedge;
  220. 				if(visited2[tp2->endvex]==0){
  221. 					tp=tp2;
  222. 					printf("%d ",tp2->endvex);
  223. 					visited2[tp2->endvex]=1;
  224. 					break;
  225. 				}
  226. 				else if(visited2[tp2->endvex]==1){
  227. 					for(tp2=tp2->nextedge;tp2!=NULL;tp2=tp2->nextedge){
  228. 						if(visited2[tp2->endvex]==0){
  229. 							tp=tp2;
  230. 							printf("%d ",tp2->endvex);
  231. 							visited2[tp2->endvex]=1;
  232. 							break;
  233. 						}
  234. 					}
  235. 					
  236. 				}
  237. 				
  238. 			}
  239. 		}
  240. 		int count=0;
  241. 		for(i=0;i<N;i++){
  242. 			if(visited2[i]==1) count++;
  243. 		}
  244. 		if(count==G->vcount) break;
  245. 	}
  246. 	
  247. }

第5关：拓扑排序

本关任务：编写一个能输出有向无环图的拓扑排序的函数。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define N  6
  4. #define MAX 100
  5. typedef struct {
  6. 	int vex;
  7. 	int shortweight;
  8. }ShortWeight;
  9. typedef struct QueueNode{
  10. 	int val;
  11. 	struct QueueNode* next;
  12. }QueueNode;
  13.  
  14. typedef struct Queue{
  15. 	QueueNode *head;
  16. 	QueueNode *tail;
  17. }Queue;
  18. //邻接矩阵数据结构 
  19. typedef  struct{
  20.    int vcount;//顶点数
  21.    int type ;//0 无向图，1 有向图
  22.    char  vexs[N]  ;     // 顶点信息
  23.    int  arcs[N][N]; //关系矩阵
  24. } GraphMatrix;
  25.  
  26. //邻接表数据结构
  27. struct EdgeNode { //边表中的结点
  28.       int  endvex;    //相邻顶点在顶点表中下标
  29.       int  weight;  //边的权
  30.       struct EdgeNode  * nextedge;   //链字段
  31. };   
  32. typedef struct EdgeNode * EdgeList;
  33.  
  34. typedef struct
  35. {
  36.    char  vertex;  //记录顶点信息
  37.    int degree;//用于记录顶点的入度，在拓扑排序时需使用
  38.    EdgeList  edgelist;  //指向边表的指针
  39. } VexNode; 
  40. typedef struct{
  41.    VexNode  *vexs[N];  //N个顶点
  42.    int type ;//0 无向图，1 有向图
  43.    int vcount;//顶点数
  44. } GraphList; 
  45. /*第一关 完成图初始化-邻接矩阵
  46. */
  47. GraphMatrix *initGraphMatrix( )
  48. {
  49.   /*第一行输入图的类型、图的顶点数和边数，第二行输入各条边的两顶点的编号，按顶点编号从小到大的顺序输入。
  50. 输出邻接矩阵，不需要考虑输入的数字非法情况，不输入顶点的信息*/
  51.    GraphMatrix *G;
  52.    G=(GraphMatrix *)malloc(sizeof(GraphMatrix));
  53.    int t,v,s;
  54.    scanf("%d %d %d",&t,&v,&s);
  55.    G->vcount=v;
  56.    G->type=t;
  57.    int i,j;
  58.    for(i=0;i<N;i++){
  59.       for(j=0;j<N;j++){
  60.          G->arcs[i][j]=0;
  61.       }
  62.    }
  63.    int head,tail;
  64.    if(t==0)
  65.       for(i=0;i<N;i++){
  66.          scanf("%d %d",&head,&tail);
  67.          G->arcs[head][tail]=1;
  68.          G->arcs[tail][head]=1;
  69.       }
  70.    if(t==1){
  71.       for(i=0;i<N;i++){
  72.          scanf("%d %d",&head,&tail);
  73.          G->arcs[head][tail]=1;
  74.       }
  75.    }
  76.    return G;
  77. }
  78. /*第二关 完成图初始化-邻接表,并完成输出图的邻接表函数
  79. */
  80. GraphList *initGraphList()
  81. {
  82.   /*第一行输入图的类型、图的顶点数和边数，第二行输入各条边的两顶点的编号，按顶点编号从小到大的顺序输入。
  83. 输出邻接表。不需考虑输入的数字非法情况，输入顶点的信息*/
  84.  GraphList *G=(GraphList*)malloc(sizeof(GraphList));
  85.  int t,v,s;
  86.  scanf("%d%d%d",&t,&v,&s);
  87.  G->vcount=v;
  88.  G->type=t;
  89.  int i,j,k,l;
  90.  char vex[N];
  91.  char ch=getchar();
  92.  for(i=0;i<v;i++){
  93.  	scanf("%c",&vex[i]);
  94.  }
  95.  for(i=0;i<v;i++){
  96.  	G->vexs[i]=(VexNode *)malloc(sizeof(VexNode));
  97.  	G->vexs[i]->vertex=vex[i];
  98.  	G->vexs[i]->edgelist=(EdgeList)malloc(sizeof(struct EdgeNode));
  99.  	G->vexs[i]->edgelist->nextedge=NULL;
  100.  	G->vexs[i]->degree=0;
  101.  }
  102.  for(i=0;i<s;i++){
  103. 	int head,tail;
  104. 	scanf("%d %d",&head,&tail);
  105. 	if(t==0){
  106. 		for(k=0;k<v;k++){
  107. 			if(G->vexs[k]->vertex-'0'==head){
  108. 				EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
  109. 				for(j=0;j<v;j++){
  110. 					if(vex[j]-'0'==tail){
  111. 						node1->endvex=j;
  112. 						node1->nextedge=G->vexs[k]->edgelist->nextedge;
  113. 						G->vexs[k]->edgelist->nextedge=node1;
  114. 						break;
  115. 					}
  116. 				}
  117. 				for(j=0;j<v;j++){
  118. 					if(G->vexs[j]->vertex-'0'==tail){
  119. 						EdgeList node2=(EdgeList)malloc(sizeof(struct EdgeNode));
  120. 						for(l=0;l<v;l++){
  121. 							if(vex[l]-'0'==head){
  122. 								node2->endvex=l;
  123. 								node2->nextedge=G->vexs[j]->edgelist->nextedge;
  124. 								G->vexs[j]->edgelist->nextedge=node2;
  125. 								break;
  126. 							}
  127. 						}
  128. 					}
  129. 				}
  130. 			}
  131. 			
  132. 		
  133. 		}
  134. 	} 
  135. 	else if(t==1){
  136. 		for(k=0;k<v;k++){
  137. 			if(G->vexs[k]->vertex-'0'==head){
  138. 				EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
  139. 				for(j=0;j<v;j++){
  140. 					if(vex[j]-'0'==tail){
  141. 						for(l=0;l<G->vcount;l++){
  142. 							if(G->vexs[l]->vertex-'0'==tail){
  143. 								G->vexs[l]->degree++;
  144. 							}
  145. 						}
  146. 						node1->endvex=j;
  147. 						node1->nextedge=G->vexs[k]->edgelist->nextedge;
  148. 						G->vexs[k]->edgelist->nextedge=node1; 
  149. 						break;
  150. 					}
  151. 				}
  152. 			}
  153. 		}
  154. 	
  155.  	}
  156.  }
  157.  return G;
  158. }
  159. void printGraphLit( GraphList *G)
  160. {
  161.  /*输出邻接表，输出格式：顶点->邻接顶点编号->...*/
  162.     int i;
  163. 	for(i=0;i<G->vcount;i++){
  164. 		printf("%c->",G->vexs[i]->vertex);
  165. 		EdgeList tp=G->vexs[i]->edgelist->nextedge;
  166. 		while(tp->nextedge!=NULL){
  167. 			printf("%d->",tp->endvex);
  168. 			tp=tp->nextedge;
  169. 		}
  170. 		printf("%d\n",tp->endvex);
  171. 	}
  172. }
  173. /*第三关 完成图的广度遍历（周游），可根据需要添加自定义函数
  174. */
  175. int visited[N]={0};
  176. void BFS_list(GraphList *G)
  177. {
  178. 	int i,j;
  179. 	printf("%c ",G->vexs[0]->vertex);
  180. 	visited[0]=1;
  181. 	EdgeList tp=G->vexs[i]->edgelist->nextedge;
  182. 	while(tp->nextedge!=NULL){
  183. 		printf("%d ",tp->endvex);
  184. 		visited[tp->endvex]=1;
  185. 		tp=tp->nextedge;
  186. 	}
  187. 	printf("%d ",tp->endvex);
  188. 	visited[tp->endvex]=1;
  189. 	for(i=N-1;i>=0;i--){
  190. 		if(visited[i]==1){
  191. 			EdgeList tp=G->vexs[i]->edgelist->nextedge;
  192. 			while(tp->nextedge!=NULL && visited[tp->endvex]==0){
  193. 			printf("%d ",tp->endvex);
  194. 			visited[tp->endvex]=1;
  195. 			tp=tp->nextedge;
  196. 			}
  197. 		}
  198. 	}
  199. 	
  200. }
  201. /*第四关 完成图的深度遍历（周游），可根据需要添加自定义函数
  202. */
  203. int visited2[N];
  204. void DFS_list(GraphList *G)
  205. {
  206. 	int i,j,k;
  207. 	for(i=0;i<N;i++){
  208. 		visited2[i]=0;
  209. 	}
  210. 	printf("%c ",G->vexs[0]->vertex);
  211. 	visited2[0]=1;
  212. 	EdgeList tp=G->vexs[0]->edgelist->nextedge;
  213. 	printf("%d ",tp->endvex);
  214. 	visited2[tp->endvex]=1;
  215. 	int num=4;
  216. 	while(1){
  217. 		for(i=0;i<G->vcount;i++){
  218. 			if(G->vexs[i]->vertex-'0'==tp->endvex){
  219. 				EdgeList tp2=G->vexs[i]->edgelist->nextedge;
  220. 				if(visited2[tp2->endvex]==0){
  221. 					tp=tp2;
  222. 					printf("%d ",tp2->endvex);
  223. 					visited2[tp2->endvex]=1;
  224. 					break;
  225. 				}
  226. 				else if(visited2[tp2->endvex]==1){
  227. 					for(tp2=tp2->nextedge;tp2!=NULL;tp2=tp2->nextedge){
  228. 						if(visited2[tp2->endvex]==0){
  229. 							tp=tp2;
  230. 							printf("%d ",tp2->endvex);
  231. 							visited2[tp2->endvex]=1;
  232. 							break;
  233. 						}
  234. 					}
  235. 					
  236. 				}
  237. 				
  238. 			}
  239. 		}
  240. 		int count=0;
  241. 		for(i=0;i<N;i++){
  242. 			if(visited2[i]==1) count++;
  243. 		}
  244. 		if(count==G->vcount) break;
  245. 	}
  246. 	
  247. }
  248. /*第五关 生成图的拓扑排序，可根据需要添加自定义函数
  249. */
  250. void QueueInit(Queue* pq) {
  251. 	pq->head = pq->tail = NULL;
  252. }
  253. void QueuePush(Queue* pq, int x) {
  254. 	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  255. 	newnode->val = x;
  256. 	newnode->next = NULL;
  257. 	if (pq->tail == NULL) {
  258. 		pq->head = pq->tail = newnode;
  259. 	}
  260. 	else {
  261. 		pq->tail->next = newnode;
  262. 		pq->tail = newnode;
  263. 	}
  264. }
  265. void QueuePop(Queue* pq) {
  266. 	if (pq->head->next == NULL) {
  267. 		pq->head = pq->tail = NULL;
  268. 	}
  269. 	else {
  270. 		QueueNode* next = pq->head->next;
  271. 		pq->head = next;
  272. 	}
  273. }
  274. int QueueFront(Queue* pq) {
  275. 	return pq->head->val;
  276. }
  277. int QueueEmpty(Queue* pq) {
  278. 	return pq->head == NULL;
  279. }
  280. void Top_list(GraphList* G)
  281. {
  282. 	Queue* Q=(Queue *)malloc(sizeof(Queue));
  283. 	QueueInit(Q);
  284. 	int i;
  285. 	int deg[N];
  286. 	for (i = 0; i < N; i++) {
  287. 		deg[i] = 0;
  288. 	}
  289. 	for (i = 0; i < N; i++) {
  290. 		deg[i] = G->vexs[i]->degree;
  291. 	}
  292.  
  293. 	for (i = 0; i < N; i++) {
  294. 		if (deg[i] == 0) {
  295. 			QueuePush(Q, i);
  296. 		}
  297. 	}
  298. 	while (!QueueEmpty(Q)) {
  299. 		int j = QueueFront(Q);
  300. 		printf("%d ", j);
  301. 		QueuePop(Q);
  302. 		EdgeList p;
  303. 		p = G->vexs[j]->edgelist->nextedge;
  304. 		while (p != NULL) {
  305. 			deg[p->endvex]--;
  306. 			if (deg[p->endvex] == 0) {
  307. 				QueuePush(Q, p->endvex);
  308. 			}
  309. 			p = p->nextedge;
  310. 		}
  311. 	}
  312. }

第6关：prim算法生成最小生成树

本关任务：实现prim算法生成最小生成树。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define N  6
  4. #define MAX 100
  5. typedef struct {
  6. 	int vex;
  7. 	int shortweight;
  8. }ShortWeight;
  9. typedef struct QueueNode{
  10. 	int val;
  11. 	struct QueueNode* next;
  12. }QueueNode;
  13.  
  14. typedef struct Queue{
  15. 	QueueNode *head;
  16. 	QueueNode *tail;
  17. }Queue;
  18. //邻接矩阵数据结构 
  19. typedef  struct{
  20.    int vcount;//顶点数
  21.    int type ;//0 无向图，1 有向图
  22.    char  vexs[N]  ;     // 顶点信息
  23.    int  arcs[N][N]; //关系矩阵
  24. } GraphMatrix;
  25.  
  26. //邻接表数据结构
  27. struct EdgeNode { //边表中的结点
  28.       int  endvex;    //相邻顶点在顶点表中下标
  29.       int  weight;  //边的权
  30.       struct EdgeNode  * nextedge;   //链字段
  31. };   
  32. typedef struct EdgeNode * EdgeList;
  33.  
  34. typedef struct
  35. {
  36.    char  vertex;  //记录顶点信息
  37.    int degree;//用于记录顶点的入度，在拓扑排序时需使用
  38.    EdgeList  edgelist;  //指向边表的指针
  39. } VexNode; 
  40. typedef struct{
  41.    VexNode  *vexs[N];  //N个顶点
  42.    int type ;//0 无向图，1 有向图
  43.    int vcount;//顶点数
  44. } GraphList; 
  45. /*第一关 完成图初始化-邻接矩阵
  46. */
  47. GraphMatrix *initGraphMatrix( )
  48. {
  49.   /*第一行输入图的类型、图的顶点数和边数，第二行输入各条边的两顶点的编号，按顶点编号从小到大的顺序输入。
  50. 输出邻接矩阵，不需要考虑输入的数字非法情况，不输入顶点的信息*/
  51.    GraphMatrix *G;
  52.    G=(GraphMatrix *)malloc(sizeof(GraphMatrix));
  53.    int t,v,s;
  54.    scanf("%d %d %d",&t,&v,&s);
  55.    G->vcount=v;
  56.    G->type=t;
  57.    int i,j;
  58.    for(i=0;i<N;i++){
  59.       for(j=0;j<N;j++){
  60.          G->arcs[i][j]=0;
  61.       }
  62.    }
  63.    int head,tail;
  64.    if(t==0)
  65.       for(i=0;i<N;i++){
  66.          scanf("%d %d",&head,&tail);
  67.          G->arcs[head][tail]=1;
  68.          G->arcs[tail][head]=1;
  69.       }
  70.    if(t==1){
  71.       for(i=0;i<N;i++){
  72.          scanf("%d %d",&head,&tail);
  73.          G->arcs[head][tail]=1;
  74.       }
  75.    }
  76.    return G;
  77. }
  78. GraphList* initGraphList()
  79. {
  80. 	/*第一行输入图的类型、图的顶点数和边数，第二行输入各条边的两顶点的编号，按顶点编号从小到大的顺序输入。
  81.   输出邻接表。不需考虑输入的数字非法情况，输入顶点的信息*/
  82. 	GraphList* G = (GraphList*)malloc(sizeof(GraphList));
  83. 	int t, v, s;
  84. 	scanf("%d%d%d", &t, &v, &s);
  85. 	G->vcount = v;
  86. 	G->type = t;
  87. 	int i, j, k, l;
  88. 	char vex[N];
  89. 	char ch = getchar();
  90. 	for (i = 0; i < v; i++) {
  91. 		scanf("%c", &vex[i]);
  92. 	}
  93. 	for (i = 0; i < v; i++) {
  94. 		G->vexs[i] = (VexNode*)malloc(sizeof(VexNode));
  95. 		G->vexs[i]->vertex = vex[i];
  96. 		G->vexs[i]->edgelist = (EdgeList)malloc(sizeof(struct EdgeNode));
  97. 		G->vexs[i]->edgelist->nextedge = NULL;
  98. 	}
  99. 	for (i = 0; i < s; i++) {
  100. 		int head, tail,w;
  101. 		scanf("%d %d %d", &head, &tail,&w);
  102. 		if (t == 0) {
  103. 			for (k = 0; k < v; k++) {
  104. 				if (G->vexs[k]->vertex - '0' == head) {
  105. 					EdgeList node1 = (EdgeList)malloc(sizeof(struct EdgeNode));
  106. 					for (j = 0; j < v; j++) {
  107. 						if (vex[j] - '0' == tail) {
  108. 							node1->weight = w;
  109. 							node1->endvex = j;
  110. 							node1->nextedge = G->vexs[k]->edgelist->nextedge;
  111. 							G->vexs[k]->edgelist->nextedge = node1;
  112. 							break;
  113. 						}
  114. 					}
  115. 					for (j = 0; j < v; j++) {
  116. 						if (G->vexs[j]->vertex - '0' == tail) {
  117. 							EdgeList node2 = (EdgeList)malloc(sizeof(struct EdgeNode));
  118. 							for (l = 0; l < v; l++) {
  119. 								if (vex[l] - '0' == head) {
  120. 									node2->weight = w;
  121. 									node2->endvex = l;
  122. 									node2->nextedge = G->vexs[j]->edgelist->nextedge;
  123. 									G->vexs[j]->edgelist->nextedge = node2;
  124. 									break;
  125. 								}
  126. 							}
  127. 						}
  128. 					}
  129. 				}
  130.  
  131.  
  132. 			}
  133. 		}
  134. 	}
  135. 	return G;
  136. }
  137. /*第三关 完成图的广度遍历（周游），可根据需要添加自定义函数
  138. */
  139. int visited[N]={0};
  140. void BFS_list(GraphList *G)
  141. {
  142. 	int i,j;
  143. 	printf("%c ",G->vexs[0]->vertex);
  144. 	visited[0]=1;
  145. 	EdgeList tp=G->vexs[i]->edgelist->nextedge;
  146. 	while(tp->nextedge!=NULL){
  147. 		printf("%d ",tp->endvex);
  148. 		visited[tp->endvex]=1;
  149. 		tp=tp->nextedge;
  150. 	}
  151. 	printf("%d ",tp->endvex);
  152. 	visited[tp->endvex]=1;
  153. 	for(i=N-1;i>=0;i--){
  154. 		if(visited[i]==1){
  155. 			EdgeList tp=G->vexs[i]->edgelist->nextedge;
  156. 			while(tp->nextedge!=NULL && visited[tp->endvex]==0){
  157. 			printf("%d ",tp->endvex);
  158. 			visited[tp->endvex]=1;
  159. 			tp=tp->nextedge;
  160. 			}
  161. 		}
  162. 	}
  163. 	
  164. }
  165. /*第四关 完成图的深度遍历（周游），可根据需要添加自定义函数
  166. */
  167. int visited2[N];
  168. void DFS_list(GraphList *G)
  169. {
  170. 	int i,j,k;
  171. 	for(i=0;i<N;i++){
  172. 		visited2[i]=0;
  173. 	}
  174. 	printf("%c ",G->vexs[0]->vertex);
  175. 	visited2[0]=1;
  176. 	EdgeList tp=G->vexs[0]->edgelist->nextedge;
  177. 	printf("%d ",tp->endvex);
  178. 	visited2[tp->endvex]=1;
  179. 	int num=4;
  180. 	while(1){
  181. 		for(i=0;i<G->vcount;i++){
  182. 			if(G->vexs[i]->vertex-'0'==tp->endvex){
  183. 				EdgeList tp2=G->vexs[i]->edgelist->nextedge;
  184. 				if(visited2[tp2->endvex]==0){
  185. 					tp=tp2;
  186. 					printf("%d ",tp2->endvex);
  187. 					visited2[tp2->endvex]=1;
  188. 					break;
  189. 				}
  190. 				else if(visited2[tp2->endvex]==1){
  191. 					for(tp2=tp2->nextedge;tp2!=NULL;tp2=tp2->nextedge){
  192. 						if(visited2[tp2->endvex]==0){
  193. 							tp=tp2;
  194. 							printf("%d ",tp2->endvex);
  195. 							visited2[tp2->endvex]=1;
  196. 							break;
  197. 						}
  198. 					}
  199. 					
  200. 				}
  201. 				
  202. 			}
  203. 		}
  204. 		int count=0;
  205. 		for(i=0;i<N;i++){
  206. 			if(visited2[i]==1) count++;
  207. 		}
  208. 		if(count==G->vcount) break;
  209. 	}
  210. 	
  211. }
  212. /*第五关 生成图的拓扑排序，可根据需要添加自定义函数
  213. */
  214. void QueueInit(Queue* pq) {
  215. 	pq->head = pq->tail = NULL;
  216. }
  217. void QueuePush(Queue* pq, int x) {
  218. 	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  219. 	newnode->val = x;
  220. 	newnode->next = NULL;
  221. 	if (pq->tail == NULL) {
  222. 		pq->head = pq->tail = newnode;
  223. 	}
  224. 	else {
  225. 		pq->tail->next = newnode;
  226. 		pq->tail = newnode;
  227. 	}
  228. }
  229. void QueuePop(Queue* pq) {
  230. 	if (pq->head->next == NULL) {
  231. 		pq->head = pq->tail = NULL;
  232. 	}
  233. 	else {
  234. 		QueueNode* next = pq->head->next;
  235. 		pq->head = next;
  236. 	}
  237. }
  238. int QueueFront(Queue* pq) {
  239. 	return pq->head->val;
  240. }
  241. int QueueEmpty(Queue* pq) {
  242. 	return pq->head == NULL;
  243. }
  244. void Top_list(GraphList* G)
  245. {
  246. 	Queue* Q=(Queue *)malloc(sizeof(Queue));
  247. 	QueueInit(Q);
  248. 	int i;
  249. 	int deg[N];
  250. 	for (i = 0; i < N; i++) {
  251. 		deg[i] = 0;
  252. 	}
  253. 	for (i = 0; i < N; i++) {
  254. 		deg[i] = G->vexs[i]->degree;
  255. 	}
  256.  
  257. 	for (i = 0; i < N; i++) {
  258. 		if (deg[i] == 0) {
  259. 			QueuePush(Q, i);
  260. 		}
  261. 	}
  262. 	while (!QueueEmpty(Q)) {
  263. 		int j = QueueFront(Q);
  264. 		printf("%d ", j);
  265. 		QueuePop(Q);
  266. 		EdgeList p;
  267. 		p = G->vexs[j]->edgelist->nextedge;
  268. 		while (p != NULL) {
  269. 			deg[p->endvex]--;
  270. 			if (deg[p->endvex] == 0) {
  271. 				QueuePush(Q, p->endvex);
  272. 			}
  273. 			p = p->nextedge;
  274. 		}
  275. 	}
  276. }
  277. /*第六关 prim算法生成最小生成树
  278. */
  279. int GetShortWeight(GraphList* G,ShortWeight *shortw) {
  280. 	int i;
  281. 	int min = MAX;
  282. 	int loc;
  283. 	for (i = 1; i < G->vcount; i++) {
  284. 		if (min > shortw[i].shortweight && shortw[i].shortweight != 0) {
  285. 			min = shortw[i].shortweight;
  286. 			loc = i;
  287. 		}
  288. 	}
  289. 	return loc;
  290. }
  291.  
  292. void Prim_list(GraphList* G)
  293. {
  294. 	int i, j, k;
  295. 	ShortWeight shortw[10];
  296. 	for (i = 0; i < 10; i++) {
  297. 		shortw[i].shortweight = MAX;
  298. 	}
  299. 	k = 0;
  300. 	EdgeList tp = G->vexs[k]->edgelist->nextedge;
  301. 	while (tp) {
  302. 		shortw[tp->endvex].shortweight= tp->weight;
  303. 		shortw[tp->endvex].vex = k;
  304. 		tp = tp->nextedge;
  305. 	}
  306. 	shortw[k].shortweight = 0;
  307. 	for (i = 0; i < G->vcount - 1; i++) {
  308. 		k = GetShortWeight(G, shortw);
  309. 		printf("%d %d\n", shortw[k].vex, k);
  310. 		shortw[k].shortweight = 0;
  311. 		EdgeList tp2 = G->vexs[k]->edgelist->nextedge;
  312. 			while (tp2) {
  313. 				if (tp2->weight < shortw[tp2->endvex].shortweight) {
  314. 					shortw[tp2->endvex].shortweight = tp2->weight;
  315. 					shortw[tp2->endvex].vex = k;
  316. 				}
  317. 				tp2 = tp2->nextedge;
  318. 			}
  319. 	}
  320. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/756050
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号