图的深度优先遍历~
继续练习数据结构~附上注释感觉有基础的不难理解~
程序代码：#include<stdio.h>
#include<stdlib.h>
struct Node /*图的结构体定义*/
{
int vertex; /*顶点数据信息*/
struct Node* nextnode; /*指下一顶点的指标*/
};
typedef struct Node* Graph; /*图形的结构新形态*/
struct Node head[9]={0}; /*图形顶点数组*/
int visited[9]={0}; /*遍历记录数组*/
/*根据已有的信息建立邻接表*/
void creatgraph(int node[20][2],int num); /*num指的是图的边数*/
void dfs(int current);/*图的深度优先搜寻法*/
int main()
{
Graph ptr=NULL;
int node[20][2]=
{
{1,3},{3,1},
{1,4},{4,1},
{2,5},{5,2},
{2,6},{6,2},
{3,7},{7,3},
{4,7},{7,4},
{5,8},{8,5},
{6,7},{7,6},
{7,8},{8,7},
};
int i=0;
for (i=1;i!=9;++i)
{
head[i].vertex=i; /*设定顶点值*/
head[i].nextnode=NULL; /*指针为空*/
visited[i]=0; /*设定遍历初始标志*/
}
creatgraph(node,20); /*建立邻接表*/
puts("Content of the graph's ADlist is");
for (i=1;i!=9;++i)
{
printf("vertex%d->",head[i].vertex); /*顶点值*/
ptr=head[i].nextnode; /*顶点位置*/
while (ptr!=NULL)
{
printf("%d ",ptr->vertex); /*印出顶点内容*/
ptr=ptr->nextnode; /*下一个顶点*/
}
puts(""); /*换行*/
}
puts("\nThe end of the def are:");
dfs(1); /*打印遍历输出过程*/
puts(""); /*换行*/
return 0;
}
void creatgraph(int node[20][2],int num) /*num指的是图的边数*/
{
Graph newnode=NULL;/*指向新节点的指针*/
Graph ptr=NULL;
int from=0; /*边的起点*/
int to=0; /*边的终点*/
int i=0;
for (i=0;i!=num;++i)
{
from=node[i][0]; /*边的起点*/
to=node[i][1]; /*边的终点*/
/*建立新的顶点*/
newnode=(Graph)malloc(sizeof (struct Node));
newnode->vertex=to; /*建立顶点内容*/
newnode->nextnode=NULL; /*设置指标初值*/
ptr=&(head[from]); /*顶点位置*/
while (ptr->nextnode!=NULL) /*遍历至链表结尾*/
ptr=ptr->nextnode;
ptr->nextnode=newnode; /*插入节点*/
}
}
void dfs(int current)
{
Graph ptr=NULL;
visited[current]=1; /*记录遍历过的数据*/
printf("vertex[%d]\n",current); /*输出遍历顶点值*/
ptr=head[current].nextnode; /*顶点位置*/
while (ptr!=NULL)
{
if (visited[ptr->vertex]==0) /*如果没有遍历过*/
dfs(ptr->vertex); /*递归遍历呼叫*/
ptr=ptr->nextnode; /*下一个顶点*/
}
}
PS:感觉这是一个无向图~如果把二维数组的倒过来赋值部分去掉就变成有向图了~
