无向图的构建及深度优先遍历-邻接表实现
无向图的构建及深度优先遍历---邻接表实现
关于数据结构中图的两种存储方式---邻接矩阵和邻接表,可以通过下面的两幅图直观地进行理解。
通过上面的两幅图可以看出,邻接表较邻接矩阵对于内存的使用更高效。
code(程序中使用上图)
/* 无向图的构建(邻接表实现)及其深度优先遍历 */ #include <stdio.h> #include <stdlib.h> #define MAX_VERTEX_NUM 30 typedef char VtType; bool visted[MAX_VERTEX_NUM]; //遍历标记 typedef struct ARC { int adj; struct ARC* nextarc; }ArcNode; //表节点 typedef struct { VtType data; ArcNode* firstarc; }VNODE,VList[MAX_VERTEX_NUM]; //一维表头 typedef struct { VList vertices; int vexnum,arcnum; }VLGraph; //邻接表图 void AddArc(VLGraph &G,int m,int n) //表中添加m结点到n结点的路径 { ArcNode* np,*curp,*save; np=(ArcNode*)malloc(sizeof(ArcNode)); np->adj=n; np->nextarc=NULL; curp=G.vertices[m].firstarc; if(curp==NULL) { G.vertices[m].firstarc=np; //第一个节点为空直接添加 } else { while(curp->adj < np->adj) //不为空时,后移实现节点索引的递增排列 { save=curp; curp=curp->nextarc; if(curp==NULL) { break; } } if(curp==NULL) { save->nextarc=np; } else { if(curp==G.vertices[m].firstarc) { save=G.vertices[m].firstarc; G.vertices[m].firstarc=np; np->nextarc=save; } else { save->nextarc=np; np->nextarc=curp; } } } } void CreateG(VLGraph &G) //创建无向图 { int i; G.vexnum=8; G.arcnum=9; for(i=0;i<G.vexnum;i++) { G.vertices[i].firstarc=NULL; G.vertices[i].data=97+i; } AddArc(G,0,1); AddArc(G,1,0); AddArc(G,3,1); AddArc(G,1,3); AddArc(G,3,7); AddArc(G,7,3); AddArc(G,4,7); AddArc(G,7,4); AddArc(G,4,1); AddArc(G,1,4); AddArc(G,0,2); AddArc(G,2,0); AddArc(G,2,5); AddArc(G,5,2); AddArc(G,2,6); AddArc(G,6,2); AddArc(G,5,6); AddArc(G,6,5); return; } void ShowVlist(VLGraph G) //邻接表输出 { int i; ArcNode* curp; printf("The adjacent list is:\n"); for(i=0;i<G.vexnum;i++) { printf("%c",G.vertices[i].data); curp=G.vertices[i].firstarc; while(curp!=NULL) { printf("-->%d",curp->adj); curp=curp->nextarc; } printf("-->NULL\n"); } return; } void DFS(VLGraph G,int v) //深度优先遍历递归函数 { ArcNode* curp; while(visted[v]==false) { printf("%c ",G.vertices[v].data); visted[v]=true; curp=G.vertices[v].firstarc; while(curp!=NULL && visted[curp->adj]==true) { curp=curp->nextarc; } if(curp==NULL) { break; } else { DFS(G,curp->adj); } } return; } void DFSTraverse(VLGraph G) //深度优先遍历接口函数 { int i; printf("The depth traverse result is:\n"); for(i=0;i<G.vexnum;i++) { visted[i]=false; } for(i=0;i<G.vexnum;i++) { if(visted[i]==false) { DFS(G,i); } } return; } int main(void) { VLGraph G; CreateG(G); ShowVlist(G); printf("\n"); DFSTraverse(G); printf("\n\n"); system("pause"); return 0; }