📄 图遍历应用_数据结构与算法_数据结构算法_c语言_c 语言之家.htm
字号:
printf("[%d]
",ptr->vertex);<BR>
}<BR>
ptr = ptr->nextnode; /*
下一个顶点
*/<BR>
}<BR> }<BR>}</P>
<P>/* ----------------------------------------
*/<BR>/*
图形的深度优先搜寻法
*/<BR>/* ----------------------------------------
*/<BR>void dfs(int current)<BR>{<BR>
graph ptr;</P>
<P> visited[current] =
1;
/* 记录已遍历过
*/<BR> printf("[%d]
",current); /*
印出遍历顶点值 */<BR>
ptr = head[current].nextnode; /*
顶点位置
*/<BR> while ( ptr != NULL
)
/* 遍历至链表尾
*/<BR>
{<BR> if (
visited[ptr->vertex] == 0 ) /* 如过没遍历过
*/<BR>
dfs(ptr->vertex);
/* 递回遍历呼叫 */<BR> ptr
=
ptr->nextnode;
/* 下一个顶点 */<BR> }<BR>}</P>
<P> </P>
<P>/* ----------------------------------------
*/<BR>/* 主程式:
建立图形后,将遍历内容印出.
*/<BR>/* ----------------------------------------
*/<BR>void main()<BR>{clrscr();</P>
<P>while(1)<BR>{<BR> char
c,a;<BR> graph ptr;<BR>
int i;<BR> int node[60][2] = { {1,
10}, {10, 1}, /*
边线数组
*/<BR>
{2, 10}, {10,
2},<BR>
{2, 3}, {3,
2},<BR>
{3, 4}, {4,
3},<BR>
{3, 12}, {12,
3},<BR>
{4, 13}, {13,
4},<BR>
{4, 5}, {5,
4},<BR>
{5, 6}, {6,
5},<BR>
{5, 7}, {7,
5},<BR>
{7, 8}, {8,
7},<BR>
{9, 10}, {10,
9},<BR>
{10, 11}, {11,
10},<BR>
{11, 14}, {14,
11},<BR>
{11, 12}, {12,
11},<BR>
{12, 15}, {15,
12},<BR>
{12, 13}, {13,
12},<BR>
{13, 16}, {16,
13},<BR>
{14, 17}, {17,
14},<BR>
{14, 18}, {18,
14},<BR>
{15, 19}, {19,
15},<BR>
{16, 20}, {20,
16},<BR>
{17, 18}, {18,
17},<BR>
{18, 23}, {23,
18},<BR>
{18, 19}, {19,
18},<BR>
{19, 23}, {23,
19},<BR>
{19, 24}, {24,
19},<BR>
{19, 20}, {20,
19},<BR>
{20, 21}, {21,
20},<BR>
{22, 23}, {23,
22},<BR>
{24, 25},
{25,24}<BR>
};<BR>clrscr();<BR>printf("\n\n\n");<BR>printf("/*------------------------------------------------------*/\n");<BR>printf("/*
欢 迎 使 用 本 程
序
*/\n");<BR>printf("/*------------------------------------------------------*/\n");<BR>printf("
本 程 序 是 有 关 图 的 遍 历 的 算 法 演 示,\n");<BR>printf("如 果
有 不 足 之 处 敬 请 原 谅!\n\n");<BR>printf("请 问 你 是 否 要 运
行 以 下 的 程 序:\n\n");<BR>printf(" 图 的 深
度 遍 历 和 广 度 遍 历?
Y/N?\n");<BR>c=getch();<BR>if(c!='y'&&'Y')<BR>exit(0);<BR> clrscr();</P>
<P>printf("\n\n");<BR>printf("请 注 意 以 下 为 各 城 市 的
代 码:\n\n");</P>
<P>printf("1:乌鲁木齐; 2:呼和浩特; 3:北京; 4:天津; 5:沈阳;
\n");<BR>printf("6:大连; 7:长春; 8:哈尔滨; 9:西宁;
10:兰州;\n");<BR>printf("11:西安; 12:郑州; 13:徐州; 14:成都;
15:武汉; \n");<BR>printf("16:上海; 17:昆明; 18:贵阳;
19:株州; 20:南昌;\n");<BR>printf("21:福州; 22:南宁; 23:柳州;
24:广州; 25:深圳.\n");</P>
<P> for (i=1;i<=25;i++
)<BR>
{<BR>
head[i].vertex=i;
/*
设定顶点值
*/<BR>
head[i].nextnode=NULL; /*
清除图形指标
*/<BR>
visited[i]=0;
/*
设定遍历初值
*/<BR> }<BR>
creategraph(node,60);
/*
建立图形
*/<BR> printf("图 形 的 邻 接 链 表 内
容:\n");<BR> for
(i=1;i<=25;i++)<BR> {
if(i%3==0)printf("\n");<BR>
printf("顶点%d=>",head[i].vertex); /*
顶点值
*/<BR>
ptr=head[i].nextnode;
/* 顶点位置
*/<BR>
while(ptr!=NULL)
/*
遍历至链表尾
*/<BR> {<BR>
printf("%d ",ptr->vertex); /*
印出顶点内容 */<BR>
ptr=ptr->nextnode;
/* 下一个顶点
*/<BR>
}<BR>
}<BR>printf("\n\n");<BR>printf("请 选 择 你 需 要 的 操
作\n");<BR>printf("1、图形的广度优先遍历请输入:'g'或'G'\n");<BR>printf("2、图形的深度优先遍历请输入:'s'或'S'\n");<BR> c=getch();<BR>
switch(c)<BR>{<BR>
case'g':case'G':<BR> printf("\n请 你 输 入
你 需 要 的 起 始 顶 点:\n");<BR>
scanf("%d",&i);<BR>
clrscr();<BR>
printf("\n\n");<BR> printf("请 注 意 以 下
为 各 城 市 的 代 码:\n\n");<BR>
printf("1:乌鲁木齐; 2:呼和浩特; 3:北京; 4:天津; 5:沈阳;
\n");<BR> printf("6:大连; 7:长春; 8:哈尔滨;
9:西宁; 10:兰州;\n");<BR> printf("11:西安;
12:郑州; 13:徐州; 14:成都; 15:武汉; \n");<BR>
printf("16:上海; 17:昆明; 18:贵阳; 19:株州;
20:南昌;\n");<BR> printf("21:福州; 22:南宁;
23:柳州; 24:广州; 25:深圳.\n");</P>
<P> printf("图 形 的
广 度 优 先 遍 历
的 顶 点 内
容:\n");<BR>
bfs(i);
/*
印出遍历过程
*/<BR>
printf("\n");
/*
换行
*/<BR>
break;<BR> case's':case'S':<BR>
printf("\n请 输 入 你 需 要 的 起 始 顶
点:\n");<BR>
scanf("%d",&i);<BR>
clrscr();<BR>
printf("\n\n");<BR> printf("请 注
意 以 下 为 各 城 市 的 代 码:\n\n");<BR>
printf("1:乌鲁木齐; 2:呼和浩特; 3:北京; 4:天津; 5:沈阳;
\n");<BR> printf("6:大连; 7:长春;
8:哈尔滨; 9:西宁; 10:兰州;\n");<BR>
printf("11:西安; 12:郑州; 13:徐州; 14:成都; 15:武汉;
\n");<BR> printf("16:上海; 17:昆明;
18:贵阳; 19:株州; 20:南昌;\n");<BR>
printf("21:福州; 22:南宁; 23:柳州; 24:广州;
25:深圳.\n");</P>
<P> printf("图 形
的 深 度 优 先 遍
历 的 顶 点 内
容:\n");<BR>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -