《数据结构C语言版——图的建立与遍历》由会员分享，可在线阅读，更多相关《数据结构C语言版——图的建立与遍历（4页珍藏版）》请在金锄头文库上搜索。
1、/*-数据结构 C 语言版图的建立与遍历编程环境 VC+ 6.0Damon2012 年 4 月 26 号-*/#include#include#include #include#define null 0#define TRUE 1#define FALSE 0#define OVERFLOW -2#define OK 1#define ERROR 0typedef int Status;/图的邻接矩阵数组存储表示-#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20typedef int VRType;typedef char VertexTyp
2、e20;typedef int Boolean;typedef struct ArcCellVRType adj;/InfoType *info;ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;MGraph;/*图的临接表存储表示-typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;InfoType *info;ArcNode;typed
3、ef struct VNodeVertexType data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum;int kind;ALGraph; */采用数组（邻接矩阵）表示法，构造无向图 G-int LocateVex(MGraph *G,VertexType v);int CreateGraph(MGraph *G)int i,j,k;VertexType v1,v2;printf(请依次输入无向网的顶点数和弧数：n);scanf(%d%d,&G-v
4、exnum,&G-arcnum);printf(请输入 %d 顶点向量： ,G-vexnum);for(i=0;ivexnum;i+)scanf(%s,G-vexsi);printf(顶点列表：n);for(i=0;ivexnum;i+)puts(G-vexsi);for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)G-arcsij.adj=0;printf(n 请输入 %d 条弧关系的邻接矩阵：n,G-arcnum);for(k=0;karcnum;k+)scanf(%s%s,v1,v2);i=LocateVex(G,v1);j=LocateVex(G,v2);G-a
5、rcsij.adj=1;G-arcsji=G-arcsij;return(1);int LocateVex(MGraph *G,VertexType v)int i;for(i=0;ivexnum;i+)if (strcmp(v,G-vexsi)=0) break;return(i);/查找第一个邻接点-int FirstAdjVex(MGraph *G,int v)int j,p=-1;for(j=0;jvexnum;j+)if(G-arcsvj.adj=1)p=j;break;return(p);/查找下一个邻接点-int NextAdjVex(MGraph *G,int v,int w)
6、int j,p=-1;for(j=w+1;jvexnum;j+)if(G-arcsvj.adj=1)p=j; break;return(p);/按邻接矩阵方式输出无向图-void PrintGraph(MGraph *G)int i,j;printf(n 无向图为:n);for(i=0;ivexnum;i+)printf(%10s,G-vexsi);for(j=0;jvexnum;j+)printf(%4d,G-arcsij.adj);printf(n);/图的深度遍历-Boolean visitedMAX_VERTEX_NUM;void Dfs(MGraph *G,int v)int w;v
7、isitedv=TRUE;printf(%s,G-vexsv);for(w=FirstAdjVex(G,v); w=0;w=NextAdjVex(G,v,w)if(!visitedw) Dfs(G,w);void DfsTraverse(MGraph *G)int v;for (v=0;vvexnum;v+)visitedv=FALSE;for(v=0;vvexnum;v+)if(!visitedv) Dfs(G,v);/主函数用采用数组（邻接矩阵）表示法，构造无向网 G-void main()MGraph G;CreateGraph(&G);PrintGraph(&G);printf(n 深度遍历:n); DfsTraverse(&G); printf(n);
