面试题：C语言实现简单图的深度优先搜索

Question

假设有一个无向图，以邻接矩阵的形式存储在二维数组中，请用C语言编写一个函数，实现对该图从指定顶点出发的深度优先搜索，并打印出遍历的顶点顺序。函数原型为：void dfs(int graph[][100], int start, int n); 其中graph是邻接矩阵，start是起始顶点，n是顶点的数量。

Answer 1

#include <stdio.h>

// 全局数组，用于标记顶点是否被访问过
int visited[100];

// 深度优先搜索函数
void dfs(int graph[][100], int start, int n) {
    // 打印当前顶点
    printf("%d ", start);
    // 标记当前顶点为已访问
    visited[start] = 1;

    // 遍历所有顶点
    for (int i = 0; i < n; i++) {
        // 如果当前顶点与邻接顶点有边相连且邻接顶点未被访问
        if (graph[start][i] &&!visited[i]) {
            // 递归调用dfs函数
            dfs(graph, i, n);
        }
    }
}

你可以这样调用这个函数：

int main() {
    int graph[100][100];
    int n;
    // 假设这里已经初始化好了graph和n
    // 初始化visited数组
    for (int i = 0; i < 100; i++) {
        visited[i] = 0;
    }
    int start = 0; // 假设从0号顶点开始
    dfs(graph, start, n);
    return 0;
}