图的深度优先搜索(DFS)

如题所述

第1个回答  2022-06-23

图有顶点和顶点之间的边组成;
图分为 有向图 无向图 ,还可以根据边长分为 有权图 无权图
我们用临结表来构造图,label表示顶点,动态数组vector中存储从当前顶点出发与当前顶点相通的顶点;
例如,从顶点 0 出发,顶点 0 和 1,2相通,那么我们就令label = 0,vector中存入顶点1,顶点2的图结构即可;

输入图中所示的图结构,对其进行深度优先搜索:

对于图中顶点 0 ,若 0 未被访问,判断由 0 出发的路径相通的点中未被访问的点,首先找到了 1 ,打印顶点 1 ,然后继续向下搜索,从 1 出发,找到了尚未被访问的 2 ,打印顶点 2 ,从 2 出发,发现 0 被访问过,return;
顶点 2 中没有相通的顶点了,该层结束,return;
顶点 1 中没有相通的顶点了,该层结束,return;
继续从顶点 0 出发,判断其他的路径相通的点中未被访问的点,找到了 4 ,打印顶点 4 ,顶点 4 中没有相通的顶点了,该层结束,return;
顶点 1 中没有相通的顶点了,该层结束,自此,顶点 0 的递归结束了;
然后继续遍历,依次判断图中剩余的 4 个顶点,顶点 1 被访问过,不递归;顶点 2 被访问过,不递归;顶点 3 未被访问过,打印顶点 3 ,递归,发现不存在 3 出发的路径相通的点中未被访问的点;递归结束;顶点 4 被访问过,不递归;