图和其遍历算法

在这个部分,我们将了解什么是图数据结构,以及对它的遍历算法.

图 是一种非线性数据结构.它由一些节点和它们连接的边组成.这些边可以是有向的或无向的.这个图可以表示为G(V,E).下面的图可以表示为G({A,B,C,D,E}, {(A,B), (B,D), (D,E), (B,C), (C,A)})

图有两种遍历算法.它们分别是广度优先搜索(BFS)和深度优先搜索(DFS).

广度优先搜索(BFS)

广度优先搜索 (BFS)是一种用来访问给定图的所有节点的算法.在这个遍历算法中,先选取一个节点,然后逐个访问所有相邻的节点.在完成所有相邻的顶点之后,它继续检查另一个顶点并再次检查它的相邻顶点.

算法

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）是一种图遍历算法。在此算法中，给定一个起始顶点，在找到相邻顶点时，首先移动到该相邻顶点，并尝试以相同的方式遍历。

算法

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