数据结构C语言版——图的建立与遍历.docx

/*-数据结构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 INFINITYINT_MAX#define MAX_VERTEX_NUM20typedef int VRType;typedef char VertexType20;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;typedef 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-vexnum,&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-arcsij.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)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;visitedv=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);/主函数用采用数组（邻接矩阵）