侧边栏壁纸
  • 累计撰写 244 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论
隐藏侧边栏

图的遍历(上)—— 深度优先搜索

kaixindeken
2021-04-23 / 0 评论 / 0 点赞 / 95 阅读 / 997 字

图的遍历和树的遍历类似,最直接的理解就是,在图中某个顶点出发,访遍图中其余顶点,并且其中每个顶点仅被访问一次,这个过程就是图的遍历。

图的遍历主要有两种方式,一种是深度优先搜索,一种是广度优先搜索。我们先来看深度优先搜索。

深度优先搜索定义

深度优先搜索(Depth First Search),简称 DFS,这种算法有点像走迷宫,沿着一条路径一直走,如果某个路径不通,则回到前驱节点,以此为出发点继续尝试下一条路径,以此类推,直到访遍所有顶点。

深度优先搜索也是这样,它从图的某个顶点出发,访问此顶点,然后从该顶点未被访问的邻接顶点出发,深度遍历图,在未遇到已访问过的重复顶点前,我们约定右手优先原则,一直往前走,遇到已经访问过的顶点,则回溯到前驱顶点,访问与其相邻路径对应的邻接顶点,继续做上述判断,依次类推,直到图中所有与该顶点路径想通的顶点都被访问到,如下图所示:

1.png

如果还有顶点未被访问,则将其作为起点,重复上述过程,直到图中所有顶点都被访问到。

typedef int VertexType;
typedef int EdgeType;
//定义存储方式为邻接矩阵
typedef struct {
    VertexType vex[100];
    EdgeType edge[100];
    int vexNum, edgeNum;
}MGraph;

bool visited[100];
void DFSTravel(MGraph g) {
    int v;
    for ( v = 0; v < g.vexNum; ++v) {
        visited[v] = false;
    }
    for (v = 0; v < g.vexNum; v++) {
        if (!visited[v]) {
            DFS(G,v)
        }
    }
}
void DFS(MGraph g, int v) {
    std::cout<<v<<std::endl;
    visited[v] = true;
    for (int i = FirstNeighbor(G, v); i >= 0 ; i = NextNeighbor(G, v, i)) {
        if (!visited[i]) {
            DFS(G, i);
        }
    }
}
  • FirstNeighbor(G, v)表示顶点 v 在图 G 中的一个邻接点
  • NextNeighbor(G, v, i) 表示顶点 v 在图 G 中除 i 之外的其他邻接点

深度优先搜索的时间复杂度很显然是 O(v+e),其中 v 表示顶点数,e 表示边数,需要额外的数组存储已访问顶点和前驱顶点,对应的空间复杂度是 O(v)。

0

评论区