065.图的深度优先遍利
【摘要】
/*/*//* 图的深度优先遍历 *//*/*/#include <stdlib.h>#include <stdio.h> struct node /* 图顶点结构定义 */{...
-
/*/*/
-
/* 图的深度优先遍历 */
-
/*/*/
-
#include <stdlib.h>
-
#include <stdio.h>
-
-
struct node /* 图顶点结构定义 */
-
{
-
int vertex; /* 顶点数据信息 */
-
struct node *nextnode; /* 指下一顶点的指标 */
-
};
-
typedef struct node *graph; /* 图形的结构新型态 */
-
struct node head[9]; /* 图形顶点数组 */
-
int visited[9]; /* 遍历标记数组 */
-
-
-
-
/********************根据已有的信息建立邻接表********************/
-
void creategraph(int node[20][2],int num)/*num指的是图的边数*/
-
{
-
graph newnode; /*指向新节点的指针定义*/
-
graph ptr;
-
int from; /* 边的起点 */
-
int to; /* 边的终点 */
-
int i;
-
-
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;
-
-
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; /* 下一个顶点 */
-
}
-
}
-
-
-
/****************************** 主程序******************************/
-
-
void main()
-
{
-
graph ptr;
-
int node[20][2] = { {1, 2}, {2, 1}, /* 边线数组 */
-
{1, 3}, {3, 1},
-
{1, 4}, {4, 1},
-
{2, 5}, {5, 2},
-
{2, 6}, {6, 2},
-
{3, 7}, {7, 3},
-
{4, 7}, {4, 4},
-
{5, 8}, {8, 5},
-
{6, 7}, {7, 6},
-
{7, 8}, {8, 7} };
-
int i;
-
clrscr();
-
for ( i = 1; i <= 8; i++ ) /* 顶点数组初始化 */
-
{
-
head[i].vertex = i; /* 设定顶点值 */
-
head[i].nextnode = NULL; /* 指针为空 */
-
visited[i] = 0; /* 设定遍历初始标志 */
-
}
-
-
creategraph(node,20); /* 建立邻接表 */
-
printf("Content of the gragh's ADlist is:\n");
-
for ( i = 1; i <= 8; i++ )
-
{
-
printf("vertex%d ->",head[i].vertex); /* 顶点值 */
-
ptr = head[i].nextnode; /* 顶点位置 */
-
while ( ptr != NULL ) /* 遍历至链表尾 */
-
{
-
printf(" %d ",ptr->vertex); /* 印出顶点内容 */
-
ptr = ptr->nextnode; /* 下一个顶点 */
-
}
-
printf("\n"); /* 换行 */
-
}
-
printf("\nThe end of the dfs are:\n");
-
dfs(1); /* 打印输出遍历过程 */
-
printf("\n"); /* 换行 */
-
puts(" Press any key to quit...");
-
getch();
-
}
文章来源: blog.csdn.net，作者：程序员编程指南，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/weixin_41055260/article/details/124495755
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）