C++ 再帰関数をグラフ データ構造に適用しますか?

C 再帰関数は、グラフ データ構造、特に深さ優先検索 (DFS) などのアルゴリズムで広く使用されています。 DFS アルゴリズムは、ノードの近傍を再帰的に探索することによってグラフを横断し、パス、接続されたコンポーネント、およびサイクルを見つけるために使用できます。次の C 関数は DFS アルゴリズムを実装します: DFS(graph, node) {}。graph はグラフ、node は現在のノードです。この関数は、現在のノードを訪問済みとしてマークし、すべての未訪問の隣接ノードを再帰的に走査します。

C グラフ データ構造における再帰関数の適用

再帰関数は、グラフ データ構造、特にアルゴリズムにおけるグラフの走査と検索で広く使用されています。この記事では、C の再帰関数を使用してグラフ上で深さ優先検索 (DFS) を実行する方法について説明します。

深さ優先検索 (DFS)

DFS アルゴリズムは、各ノードのすべての未探索の隣接ノードを再帰的に探索することにより、グラフを横断します。このアルゴリズムは、グラフ内のパス、接続成分、およびサイクルを見つけるために使用できます。

C 再帰 DFS 関数

次の C 関数は DFS アルゴリズムを実装します:

void DFS(Graph& graph, int node) {
  // 标记给定节点已访问
  graph.visit(node);

  // 递归遍历所有未访问的邻接节点
  for (auto adjacent_node : graph.get_adjacent_nodes(node)) {
    if (!graph.is_visited(adjacent_node)) {
      DFS(graph, adjacent_node);
    }
  }
}

実用的なケース

次の無向グラフを考えてみましょう:

1 -- 2
| /  |
3 -- 4

このグラフを DFS するには、ノードから開始して、その未訪問の隣接ノードをすべて再帰的にアクセスする必要があります:

Graph graph;
// 添加节点和边
graph.add_edge(1, 2);
graph.add_edge(1, 3);
graph.add_edge(2, 4);
graph.add_edge(3, 4);

// 从节点 1 开始 DFS
DFS(graph, 1);

DFS は次のアクセス シーケンスを出力します: 1、2、4、3

結論

再帰関数は、グラフ データ構造にさまざまなトラバーサルおよび検索アルゴリズムを実装するための簡潔かつ強力な方法を提供します。この記事では、C の再帰関数を使用して DFS を実行する方法について説明し、その応用例を示す実践的なケースを示します。

以上がC++ 再帰関数をグラフ データ構造に適用しますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。