グラフとその走査アルゴリズム

このセクションでは、グラフデータ構造とそのトラバーサルアルゴリズムについて説明します。

グラフは1つの非線形データ構造です。これは、いくつかのノードとそれらの接続されたエッジで構成されています。エッジは、ディレクターまたは無向の場合があります。このグラフは、G（V、E）として表すことができます。次のグラフは、G（{A、B、C、D、E}、{（A、B）、（B、D）、（D、E）、（B、C）、（C、A ）}）

グラフには、2種類のトラバーサルアルゴリズムがあります。これらは、幅優先探索および深さ優先探索と呼ばれます。

幅優先探索（BFS）

幅優先探索（BFS）トラバーサルはアルゴリズムであり、特定のグラフのすべてのノードにアクセスするために使用されます。このトラバーサルアルゴリズムでは、1つのノードが選択され、隣接するすべてのノードが1つずつ訪問されます。隣接するすべての頂点を完了すると、さらに移動して別の頂点をチェックし、隣接する頂点を再度チェックします。

アルゴリズム

bfs(vertices, start)
Input: The list of vertices, and the start vertex.
Output: Traverse all of the nodes, if the graph is connected.
Begin
   define an empty queue que
   at first mark all nodes status as unvisited
   add the start vertex into the que
   while que is not empty, do
      delete item from que and set to u
      display the vertex u
      for all vertices 1 adjacent with u, do
         if vertices[i] is unvisited, then
            mark vertices[i] as temporarily visited
            add v into the queue
         mark
      done
      mark u as completely visited
   done
End

深さ優先探索（DFS）

深さ優先探索（DFS）は、グラフ走査アルゴリズムです。このアルゴリズムでは、開始頂点が1つ与えられ、隣接する頂点が見つかると、最初にその隣接する頂点に移動し、同じ方法でトラバースを試みます。

アルゴリズム

dfs(vertices, start)
Input: The list of all vertices, and the start node.
Output: Traverse all nodes in the graph.
Begin
   initially make the state to unvisited for all nodes
   push start into the stack
   while stack is not empty, do
      pop element from stack and set to u
      display the node u
      if u is not visited, then
         mark u as visited
         for all nodes i connected to u, do
            if ith vertex is unvisited, then
               push ith vertex into the stack
               mark ith vertex as visited
         done
   done
End