生活随笔
收集整理的這篇文章主要介紹了
数据结构分析之——图
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
無向圖，鄰接矩陣結構
????????#include<iostream> ?using?namespace?std; ??#define?VertexNum?10????????//定義頂點數量最多10個，#define不帶分號 ???typedef?struct{???????????????????????????????????char?vexs[VertexNum];??????int??edges[VertexNum][VertexNum]; ?????int?v,e;????????????????????????????????}Graph; ???typedef?struct?qNode{ ?????int?front; ?????int?rear; ?????int?count; ?????int?p[VertexNum]; ?}queue; ???int?visited[VertexNum]; ??void?CreatGraph(Graph?*G);???????????void?FS(Graph?*G,int?choice);????????void?dfs(Graph?*G,int?i);???????????void?bfs(Graph?*G,int?i);?????????????int?main(void) ?{ ?????Graph?*graph; ?????graph?=?(Graph?*)malloc(sizeof(Graph)); ?????CreatGraph(graph); ?????cout?<<?"----DFS----"?<<?endl; ?????FS(graph,0); ?????cout?<<?"----BFS----"?<<?endl; ?????FS(graph,1); ?????return?0; ?} ???void?CreatGraph(Graph?*G) ?{ ?????int?i,j,k; ?????cout?<<?"Input?number?of?vertex?and?number?of?edges"?<<?endl; ?????cin?>>?G->v?>>?G->e; ?????cout?<<?"Input?data?of?vertex"?<<?endl; ?????for(i?=?0;i?<?G->v;?i++) ?????{ ?????????cin?>>?G->vexs[i]; ?????} ?????for(i?=?0;?i?<?G->v;?i++) ?????????for(j?=?0;j?<?G->v;?j++) ?????????{ ?????????????G->edges[i][j]?=?0;???????????????????????} ?????cout?<<?"Input?information?of?edges.e.g:input?1?and?2?represents?vertex?1?connects?with?2"?<<?endl; ?????for(k?=?0;?k?<?G->v;?k++) ?????{ ?????????cin?>>?i?>>?j; ?????????G->edges[i-1][j-1]=1;???????????????} ?} ???void?FS(Graph?*G,int?choice)??????????????????{ ?????int?i?=?0; ?????for(i?=?0;i?<?G->v;?i++) ?????????visited[i]?=?0;??????????????????????????switch(choice) ?????????????{ ?????????????????case?0: ?????????????????????for(i?=?0;i?<?G->v;?i++) ?????????????????????????dfs(G,i);??????????????????????????????????????break; ?????????????????case?1: ?????????????????????for(i?=?0;i?<?G->v;?i++) ?????????????????????????bfs(G,i); ?????????????????????break; ?????????????} ?} ???void?dfs(Graph?*G,int?i) ?{ ?????if(visited[i]?==?0) ?????{ ?????????cout?<<?"Vertex?"?<<?i+1?<<?"?has?been?visited!"?<<?endl; ?????????visited[i]?=?1; ?????????for(int?j?=?0;j?<?G->v;?j++) ?????????{ ?????????????if(G->edges[i][j]?!=?0?&&?visited[j]?==?0) ?????????????????dfs(G,j);??????????????????}??? ?????} ?} ???void?bfs(Graph?*G,int?i) ?{??? ?????int?j,k; ?????queue?*q=(queue?*)malloc(sizeof(queue));????????q->front?=?q->rear?=?q->count?=?0;??????????????????????? ?????visited[i]?=?1; ?????cout?<<?"Vertex?"?<<?i+1?<<?"?has?been?visited!"?<<?endl; ?????q->p[q->rear]?=?i;???????????????????????????????q->rear++; ?????q->count++;????????????????????while(q->count?>?0)???????????{ ?????????j?=?q->p[q->front]; ?????????q->front++; ?????????q->count--;???????????????????????????if(visited[j]?==?0) ?????????{ ?????????????for(k?=?0;?k?<?G->v;?k++) ?????????????{ ?????????????????if(G->edges[j][k]?!=?0?&&?visited[k]?==?0)????????????????????{ ?????????????????????cout?<<?"Vertex?"?<<?k+1?<<?"?has?been?visited!"?<<?endl; ?????????????????????visited[k]?=?1; ??????????????????????q->p[q->rear]?=?k; ?????????????????????q->rear++; ?????????????????????q->count++;???????????????????????????} ?????????????} ?????????} ?????} ?}? ?
轉載于:https://blog.51cto.com/4893836/847327
總結
以上是生活随笔為你收集整理的数据结构分析之——图的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
