首页 > 代码库 > 图的邻接表存储c实现(DFS遍历)
图的邻接表存储c实现(DFS遍历)
先简要列出实现过程中所需要的数据结构。
如下图
对于这个图而言，它的邻接表可以这样表示，当然表现形式可以多样，这只是我随便画的一种表示方法。
顶点表 边表
我们把第一个表即上面标着fixedvex的这个表称作顶点表，后边的称为边表。
上图所示，边表的结构应该这样写：
//定义一个边表节点的结构 typedef struct node{ int adjvex; //int Mark; //用于标记是否被访问过 node *next;}VerAndedge;
包含一个adjvex，保存某个结点；
一个next指向下个边表结构，构成各个顶点间的联系。
既然有了边表的结构，那么顶点表的结构应该如下：
//顶点表 typedef struct Fixed{ int Mark; int fixedvex; node* firsthead;}Fixednode;
包含一个fixedvex保存顶点；
由图中可知，顶点表指向边表，所以理所当然包含一个指向边表的指针：一个 firsthead ;
有了以上这2个结构，我们便可以着手开始实现它了。
首先明确要有几个结点，也就是要有几个 fixedvex ，由于每个fixedvex都有其特定的关系，所以我们应该生成结构数组来保存这些内容，所以我们再建立如下的结构保存，为什么创建这个结构？下面将清晰。
//保存各个顶点信息。 typedef struct ALgarph{ int a,b; Fixednode adjlist[100];}ALgarph;
既然要创建一个邻接表，那就写一个函数吧
void creat(ALgarph *);
首先必须对这个函数传入内容，那我们便创建一个结构，并传入
ALgarph *S = (ALgarph*)malloc(sizeof(ALgarph));
creat(S);
这个creat到底怎么写呢，下面直接给出代码，读者通过注释自己理解。
void creat(ALgarph *S){ int i,x,y; printf("请输入顶点的个数和边的数量:"); scanf("%d%d",&S->a,&S->b); //获取到顶点和边的信息 for(i=0;i<S->a;i++) { printf("输入顶点，建立顶点表:"); //建立顶点表。 scanf("%d",&S->adjlist[i].fixedvex); S->adjlist[i].firsthead= NULL; //初始化firsthead S->adjlist[i].Mark = 0;//初始化标记 } printf("建立边表\n");//建立边表，在建立的同时将他们的关系对应 for(i=0;i<S->b;i++) { printf("读入(vi-vj):"); scanf("%d%d",&x,&y); VerAndedge * G = (VerAndedge *)malloc(sizeof(VerAndedge)); //生成一个边表结构 // G->Mark = 0; //标记为零表示未访问 G->adjvex= y; G->next= S->adjlist[x].firsthead; //插入到头部 S->adjlist[x].firsthead= G; //因为是无向图，所以调换个节点的关系，再次生成。 G= (VerAndedge *)malloc(sizeof(VerAndedge)); // G->Mark = 0; G->adjvex= x; G->next= S->adjlist[y].firsthead; //插入到头部 S->adjlist[y].firsthead= G; }}
创建完毕后就是输出这个邻接表了。
VerAndedge *current; for(i=0;i<S->a;i++) { printf("%d->",S->adjlist[i].fixedvex); current = S->adjlist[i].firsthead; while(current!=NULL) { printf("%d->",current->adjvex); current= current->next; } printf("\n"); }
好了，那么完整的程序如下：
/*2014/12/1*//*邻接表表示的图的深度优先遍历*//*这个代码是在昨天的基础上改写了，添加了DFS遍历的2个函数，注释着实觉得没有添加的必要.反正是采用了递归的方法 */#include <stdio.h>#include <stdlib.h>//定义一个边表节点的结构 typedef struct node{ int adjvex; //int Mark; //用于标记是否被访问过 node *next;}VerAndedge; //顶点表 typedef struct Fixed{ int Mark; int fixedvex; node* firsthead;}Fixednode;//保存各个顶点信息。 typedef struct ALgarph{ int a,b; Fixednode adjlist[100];}ALgarph;void creat(ALgarph *);void Adj_dfs(ALgarph *);void Adj_visit(ALgarph * ,int); int main(void){ int i; ALgarph * S = (ALgarph *)malloc(sizeof(ALgarph)); creat(S); VerAndedge *current; for(i=0;i<S->a;i++) { printf("%d->",S->adjlist[i].fixedvex); current = S->adjlist[i].firsthead; while(current!=NULL) { printf("%d->",current->adjvex); current= current->next; } printf("\n"); } Adj_dfs(S); return 0;} void creat(ALgarph *S){ int i,x,y; printf("请输入顶点的个数和边的数量:"); scanf("%d%d",&S->a,&S->b); //获取到顶点和边的信息 for(i=0;i<S->a;i++) { printf("输入顶点，建立顶点表:"); //建立顶点表。 scanf("%d",&S->adjlist[i].fixedvex); S->adjlist[i].firsthead= NULL; //初始化firsthead S->adjlist[i].Mark = 0;//初始化标记 } printf("建立边表\n");//建立边表，在建立的同时将他们的关系对应 for(i=0;i<S->b;i++) { printf("读入(vi-vj):"); scanf("%d%d",&x,&y); VerAndedge * G = (VerAndedge *)malloc(sizeof(VerAndedge)); //生成一个边表结构 // G->Mark = 0; //标记为零表示未访问 G->adjvex= y; G->next= S->adjlist[x].firsthead; //插入到头部 S->adjlist[x].firsthead= G; //因为是无向图，所以调换个节点的关系，再次生成。 G= (VerAndedge *)malloc(sizeof(VerAndedge)); // G->Mark = 0; G->adjvex= x; G->next= S->adjlist[y].firsthead; //插入到头部 S->adjlist[y].firsthead= G; }}void Adj_dfs(ALgarph *S){ int vi; printf("请输入源点：\n"); scanf("%d",&vi); printf("遍历结果如下:"); Adj_visit(S,vi);}void Adj_visit(ALgarph * S,int vi){ if(S->adjlist[vi].Mark == 0) { printf("%-2d",S->adjlist[vi].fixedvex); S->adjlist[vi].Mark = 1; } VerAndedge * current = S->adjlist[vi].firsthead; for(;current!=NULL;current=current->next) { if(S->adjlist[current->adjvex].Mark==0) Adj_visit(S,current->adjvex); } }
运行结果如下
图的邻接表存储c实现(DFS遍历)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。