C言語のDFSアルゴリズムの実装方法

DFSアルゴリズムをC言語で実装する一般的な方法は再帰を使用することです。以下に簡単な例を示します。

#include <stdio.h>

#define MAX_VERTICES 100

int graph[MAX_VERTICES][MAX_VERTICES]; // 图的邻接矩阵表示
int visited[MAX_VERTICES]; // 记录顶点是否已访问

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

    // 遍历邻接矩阵中与当前顶点相邻的所有顶点
    for (int i = 0; i < n; i++) {
        if (graph[v][i] && !visited[i]) {
            dfs(i, n); // 递归搜索相邻顶点
        }
    }
}

int main() {
    int n, m; // n为顶点数，m为边数
    scanf("%d %d", &n, &m);

    // 初始化邻接矩阵和visited数组
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
        for (int j = 0; j < n; j++) {
            graph[i][j] = 0;
        }
    }

    // 读入边的信息，并构建邻接矩阵
    for (int i = 0; i < m; i++) {
        int u, v; // 边的两个顶点
        scanf("%d %d", &u, &v);
        graph[u][v] = 1;
        graph[v][u] = 1; // 若图为无向图，还需设置对称位置为1
    }

    // 从顶点0开始进行深度优先搜索
    dfs(0, n);

    return 0;
}

グラフの接続関係を表す隣接行列のgraphと、頂点の訪問履歴を記録するvisitedを定義し、dfs関数が再帰的に探索を行います。

メイン関数では, まず頂点数と辺数を読み込み, 隣接行列と訪問済み配列を初期化する. 次に, 入力された辺の情報に従って，隣接行列を作成する. 最後に，頂点0から深さ優先探索を行う.

上記のコードは単純な深さ優先探索アルゴリズムの実装であり、必要に応じて変更・拡張することができます。