#include <stdio.h>
/*
* 邻接矩阵,深度优先遍历
*
*/
#define MAX 100
#define INFINITY 65535
int visited[MAX]; // 标记遍历过的顶点下标
typedef struct {
char vexs[MAX]; // 顶点的数组,顶点类型为了简单使用char
int arc[MAX][MAX]; // 边表二维数组,对,行列的下标对应实际存在的顶点,值为1表示两顶点间有边
int numVex, numEdg; // 顶点和边的数量,创建的时候用
}GRAPH, *PGRAPH;
void create(PGRAPH);
void traverse_dfs(GRAPH);
void dfs(GRAPH, int);
void dfs(GRAPH graph, int i)
{
int j;
// 先打印,并更新visited数组
printf("%c ", graph.vexs[i]);
visited[i] = 1;
// 在顶点i的行中查找,一旦找到没有访问的顶点,则递归调用
for (j=0; j<graph.numVex; j++) {
if (graph.arc[i][j] == 1 && !visited[j] ) {
dfs(graph, j);
}
}
}
void traverse_dfs(GRAPH graph)
{
int i;
// 先初始化标记数组visited
for (i=0; i<graph.numVex; i++) {
visited[i] = 0;
}
// 开始遍历
for (i=0; i<graph.numVex; i++) {
if (!visited[i])
dfs(graph, i);
}
}
void create(PGRAPH g)
{
int i, j, k, w;
printf("请输入顶点及边的个数:\n"); // 这里输入边的个数也就只有在创建的时候用得着
scanf("%d %d", &g->numVex, &g->numEdg);
// 创建顶点
printf("请一次性输入顶点的值:\n");
getchar();
for (i=0; i<g->numVex; i++) {
scanf("%c", &g->vexs[i]);
}
// 初始化边表
for (i=0; i<g->numVex; i++) {
for (j=0; j<g->numVex; j++) {
g->arc[i][j] = INFINITY;
}
}
// 创建表
for (k=0; k<g->numEdg; k++) {
printf("请输入边的顶点下标和权:\n"); // 本例中并没有对权有操作
scanf("%d %d %d", &i, &j, &w);
g->arc[i][j] = g->arc[j][i] = w;
}
}
int main(void)
{
GRAPH graph;
create(&graph);
printf("深度优先遍历结果: ");
traverse_dfs(graph);
putchar(‘\n‘);
return 0;
}
output
[root@8be225462e66 c]# gcc dfs_adMatrix.c && ./a.out
请输入顶点及边的个数:
8 9
请一次性输入顶点的值:
ABCDEFGH
请输入边的顶点下标和权:
0 1 1
请输入边的顶点下标和权:
1 2 1
请输入边的顶点下标和权:
2 5 1
请输入边的顶点下标和权:
1 4 1
请输入边的顶点下标和权:
0 4 1
请输入边的顶点下标和权:
0 3 1
请输入边的顶点下标和权:
3 6 1
请输入边的顶点下标和权:
6 4 1 #输入 4 6 1也可以,因为是对称矩阵
请输入边的顶点下标和权:
6 7 1
深度优先遍历结果: A B C F E G D H
[root@8be225462e66 c]
原文:https://blog.51cto.com/sndapk/2693061