现在你扮演一名学生,已知typedef int ElemType; #define N 10 //用于存储图的邻接矩阵的数组 struct MGraph{ ElemType vertex[N];//用于存储顶点信息的数组 int arc[N][N]; //邻接矩阵,用于存储边信息的数组 int degree_out[N]; //顶点的出度 int degree_in[N]; //顶点的入度 }mGraph;为C语言函数定义部分,请你写出一个以DFS为函数名的深度优先遍历算法
时间: 2024-01-21 08:04:22 浏览: 64
图的邻接表存储实现及深度优先遍历
4星 · 用户满意度95%
好的,我来给你写一个深度优先遍历算法。如下所示:
```
void DFS(int v, bool visited[]) {
visited[v] = true; // 标记当前顶点已访问
printf("%d ", mGraph.vertex[v]); // 访问当前顶点
// 遍历当前顶点的邻接点
for (int i = 0; i < N; i++) {
if (mGraph.arc[v][i] == 1 && !visited[i]) {
DFS(i, visited); // 递归访问邻接点
}
}
}
void DFSTraverse() {
bool visited[N] = { false }; // 初始化为所有顶点未访问状态
for (int i = 0; i < N; i++) {
if (!visited[i]) {
DFS(i, visited); // 对未访问过的顶点进行深度优先遍历
}
}
}
```
其中,`DFS`函数是深度优先遍历的核心操作,参数`v`表示当前访问的顶点在`mGraph.vertex`数组中的下标,`visited`数组用于记录每个顶点是否已被访问过。该函数首先将当前顶点标记为已访问,并输出当前顶点的值,然后遍历当前顶点的所有邻接点,对未访问过的邻接点进行递归访问。
`DFSTraverse`函数是对整个图进行深度优先遍历的入口函数,它首先将所有顶点初始化为未访问状态,然后对未访问过的顶点依次进行深度优先遍历。
阅读全文