chapter_graph/graph_traversal/

[giscus[bot]]

chapter_graph/graph_traversal/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_graph/graph_traversal/

[ignorantshr]

发现一个问题，就是在一个图中如果有顶点不与其它顶点相连的话就遍历不到了。

[krahets]

是的，在非连通图中，从某个顶点出发，至少有一个顶点不可达。如果要完整遍历，需要设定多个起点，遍历图的所有连通分量。

[is-liu]

就前几周的leetcode周赛，有一个题就是用到了多源BFS。虽然和你问的可能不大相关，但是可以看一下
2812. 找出最安全路径

[GyBernstein]

这里会讲有向图相关的内容吗

[krahets]

暂时没有，可能会通过一些例题来体现

[rinuandengfeng]

你好，K神！有一个想法，可以在代码中添加一些测试用例嘛？这样在调试代码的过程中更好的理解代码。

[krahets]

Hi! 本书提供一键可运行的源代码，其中包含测试样例。本文代码传送门：

• https://github.com/krahets/hello-algo/blob/main/codes/java/chapter_graph/graph_bfs.java
• https://github.com/krahets/hello-algo/blob/main/codes/java/chapter_graph/graph_dfs.java

你可以在源码中修改现有测试样例。还是说你想让源码自带更多测试样例？

[rookiexxj]

wc，之前一直不知道🆒

[jiangyigithub]

i suggest to add some classic algorithms for Graph ,like the Dijkstra algorithm

[krahets]

Got it!

[zenoskongfu]

help do this

[1669119595]

graph.adjList.keySet 不是就可以获取所有的节点了吗，还是图遍历必须是走边才行呢？

[krahets]

是的，因为“获取所有节点”和“遍历”是两种不同的操作。遍历需要在图中走一遍，要用到边的信息。链表和二叉树也同理。

[1669119595]

感谢

[insomnia-city]

我看了下关于CSharp的代码，遍历方式更像是一笔画方式，如果说图不满足一笔画，也可以实现BFS所有元素吗

[insomnia-city]

只是以哈希来保证元素的不重复的话，当不满足一笔画时，就无法BFS，DFS所有元素吧

[voiov]

一笔画只是要求奇点小于等于2,与能否遍历不等价.

[theNefelibatas]

你好，

1. 在基于递归实现的DFS里面visited哈希表似乎并不是必须的？可以直接通过判断res里面是否已存在来决定是否跳过结点；使用visited是考虑到通过哈希表来查找元素的时间复杂度为 $O(1)$ 吗？

2. 除了基于递归实现的DFS，还可以借助栈来实现：

/* 深度优先遍历 DFS */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
vector<Vertex *> graphDFS(GraphAdjList &graph, Vertex *startVet) {
    // 顶点遍历序列
    vector<Vertex *> res;
    // 哈希表，用于记录已被访问过的顶点
    unordered_set<Vertex *> visited;
    // 栈用于实现 DFS
    stack<Vertex *> stk;
    stk.push(startVet);
    // 以顶点 vet 为起点，循环直至访问完所有顶点
    while (!stk.empty()) {
        Vertex *vet = stk.top();
        stk.pop();          // 栈顶顶点出栈
        res.push_back(vet); // 记录访问顶点
        // 遍历该顶点的所有邻接顶点
        for (auto adjVet : graph.adjList[vet]) {
            if (visited.count(adjVet))
                continue;            // 跳过已被访问过的顶点
            stk.push(adjVet);        // 只入栈未访问的顶点
            visited.emplace(adjVet); // 标记该节点已入栈
        }
    }
    // 返回顶点遍历序列
    return res;
}

/* 深度优先遍历 BFS */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
func graphDFS(g *graphAdjList, startVet Vertex) []Vertex {
	// 顶点遍历序列
	res := make([]Vertex, 0)
	// 哈希表，用于记录已被访问过的顶点
	visited := make(map[Vertex]struct{})
	visited[startVet] = struct{}{}
	// 栈用于实现 BFS, 使用切片模拟栈
	stack := make([]Vertex, 0)
	stack = append(stack, startVet)
	// 以顶点 vet 为起点，循环直至访问完所有顶点
	for len(stack) > 0 {
		// 队首顶点出队
		vet := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		// 记录访问顶点
		res = append(res, vet)
		// 遍历该顶点的所有邻接顶点
		for _, adjVet := range g.adjList[vet] {
			_, isExist := visited[adjVet]
			// 只入栈未访问的顶点
			if !isExist {
				stack = append(stack, adjVet)
				visited[adjVet] = struct{}{}
			}
		}
	}
	// 返回顶点遍历序列
	return res
}

[krahets]

Hi，是的，在 res 中判断需要进行遍历，时间复杂度为 $O(1)$ 。

[cjvox]

实际上DFS就是栈的实现，虽然代码中没有显示使用栈，但是递归调用的底层是使用了隐式栈的

[topul]

/**
         * 0 1 2
         * 3 4 5
         * 6 7 8
         */
        Vertex vet0 = new Vertex(0);
        Vertex vet1 = new Vertex(1);
        Vertex vet2 = new Vertex(2);
        Vertex vet3 = new Vertex(3);
        Vertex vet4 = new Vertex(4);
        Vertex vet5 = new Vertex(5);
        Vertex vet6 = new Vertex(6);
        Vertex vet7 = new Vertex(7);
        Vertex vet8 = new Vertex(8);
        Vertex[][] vertex = new Vertex[][]{
                {vet0, vet1}, {vet0, vet3},
                {vet1, vet2}, {vet1, vet0}, {vet1, vet4},
                {vet2, vet1}, {vet2, vet5},
                {vet3, vet0}, {vet3, vet4}, {vet3, vet6},
                {vet4, vet1}, {vet4, vet3}, {vet4, vet5}, {vet4, vet7},
                {vet5, vet2}, {vet5, vet4}, {vet5, vet8},
                {vet6, vet3}, {vet6, vet7},
                {vet7, vet4}, {vet7, vet6}, {vet7, vet8},
                {vet8, vet5}, {vet8, vet7}};

构造出来这个图好麻烦，有没有简洁的方式？

[topul]

Vertex[][] vertex = new Vertex[][]{
                {vet0, vet1}, {vet0, vet3},
                {vet1, vet2}, {vet1, vet4},
                {vet2, vet5},
                {vet3, vet4}, {vet3, vet6},
                {vet4, vet5}, {vet4, vet7},
                {vet5, vet8},
                {vet6, vet7},
                {vet7, vet8}};

因为是无向图，可以把重复的删掉，还是觉得麻烦

[krahets]

写个 UI 界面，手动创建节点和边 😎

[voiov]

建议备注 哈希表 visited 不一定保证元素顺序,只能保证元素唯一.

[wbzyo]

确实，但唯一就够用了，需要保证顺序的是res列表，visited只是验证是否访问过该节点

[noobcodemaker]

k神您好，我作为初学者对递归算法理解的一直不是太到位，看完本篇有两点疑问：
1.关于本篇提到的深度优先遍历的python代码中，dfs这个子函数并没有return语句，也就是相当于并没有出现显式的判断来执行回溯过程，其执行逻辑是不是这样的：该函数某次递归的for循环语句结束后，系统自动出栈回溯至递归函数的上一次调用的位置。
2.关于二叉树的深度优先搜索中，我们一直使用类似于 if root is None: return的语句来显式的判断递归终止或者说是回溯，但是在图中，是否是因为难以找到一个显式的终止条件来结束递归，因此采用的是建立一个set集合来存储已遍历的值，并通过for循环来实现隐式的递归呢

[krahets]

你好哇！

1. 是的，可以理解为 rerturn 在函数的最后一行。由于是 void 函数，这个 return 可以省略，函数执行完毕后，就“回溯”了。
2. 这和“困难”与否没有关系，是因为遍历方式不同导致的。遍历图是通过遍历节点的“邻接节点”实现的，当邻接节点列表为空时就会停止遍历了。当然你可以显式地写出来提前 return ，但没有必要：

# 假设是有向图
# 省略...
if len(graph.adj_list[vet]) == 0:
    return
# 遍历该顶点的所有邻接顶点
for adjVet in graph.adj_list[vet]:
# 省略...

反过来讲，树是图的一种特殊情况。因此我们也可以在像遍历图这样来遍历树（将树看作是每个节点有两个邻接节点的图），这样也不用写提前 return 了，但代码会变臃肿。

[clearwater753]

您好，上面代码里的len(graph.adj_list[vet])应该不等于0吧。
我这样在for循环后面加一个return行不行？

def dfs(graph: GraphAdjList, visited: set[Vertex], res: list[Vertex], vet: Vertex):
    """深度优先遍历 DFS 辅助函数"""
    res.append(vet)  # 记录访问顶点
    visited.add(vet)  # 标记该顶点已被访问
    # 遍历该顶点的所有邻接顶点
    for adjVet in graph.adj_list[vet]:
        if adjVet in visited:
            continue  # 跳过已被访问过的顶点
        # 递归访问邻接顶点
        dfs(graph, visited, res, adjVet)
    return

[krahets]

@clearwater753 Hi，在有向图下可能为 0 。也可以的～

[buynonsense]

你好，我是初学者，我有一个疑问。（9.3.1→ 2.复杂度分析）

在询问chatgpt时：“在最坏情况下，如果图是连通的（每个节点都能直接或间接到达其他节点），则 |E| 最多为 O(|V|^2)，因此 BFS 的时间复杂度可以近似表示为 O(|V| + |V|^2)。”

但是在询问Monica时：“然而，需要注意的是，在实际应用中，图的边数通常不会达到 O(|V|^2)，因此广度优先搜索的时间复杂度可以简化为 O(|V|)。”

[hpstory]

@Kkkazecn , 我认为两种说法都是对的，讨论的前提是图的类型，如果一张图的边数接近其点数的平方，那么它是一张稠密图 (dense graph)。这时候时间复杂度为O(|V|^2)，如果一张图的边数远小于其点数的平方，那么它是一张稀疏图 (sparse graph)。这个时候时间复杂度可以认为是O(|V|)。通常情况下一般讨论图，假设都是稀疏图。无论哪种情况，总体的时间复杂度都是O(|V| + |E|)。在算法题目中一般都会对点和边的数量进行限制，可以根据情况选择对应的算法。

[caolib]

求一个kruskal算法，还有与之相关的并查集实现

[krahets]

收到，已加入 waiting list

[danghfz]

对于广度优先遍历bfs，如果有一个节点没有与任何节点连接，那么可能就访问不到该节点，或者该起始节点没有与其他节点连接，那么访问不到除起始节点外的任何节点

[krahets]

是的，这个就是做非连通图。无论 BFS 还是 DFS 都一样无法访问到其他节点，因为没有“边”通向它们。

[cjvox]

这里作者没有写使用邻接矩阵实现BFS和DFS遍历，大家可以去做一下 力扣547省份数量
注意点

• 这道题的邻接矩阵对角线是默认为1
• 使用邻接矩阵最重要还是区分已经访问过的元素
• 贴自己写的题解（代码写的可能不是很好，但是我是利用对角线去重，和官方题解不太一样）

[amoyonglee]

谢谢你的补充!! 通过这个题还学习了并查集的运用 图解并查集 , 不过有点分不清这属于 BFS 还是 DFS

[OnlyGray]

    # 哈希表，用于记录已被访问过的顶点
    visited = set[Vertex]([start_vet])
    # 队列用于实现 BFS
    que = deque[Vertex]([start_vet])

你好，请问这里的[start_vet]为什么要加[]

[hpstory]

Hi @OnlyGray，python使用set()创建集合时需要将元素放在一个可迭代的对象中，比如列表，如果不加[]会报错，因为start_vet不是一个可迭代的对象。

[DracoYus]

感觉在图的语境下，遍历这个概念发生了变化。
遍历给我的直观感受是，获取数据结构中存储的所有数据。
前章内容都符合这个定义。如果存储数据在内存中是连续地址，那么只需首地址和偏移量就可以访问所有元素。如果是链表形势，那么需要通过指针逐元素访问。
但在图这一章节，数据概念不仅包括节点本身，还包括了边。遍历这一行为自然也拆分为遍历所有节点和遍历所有边。
由于图的数据结构中，节点信息是使用列表进行存储。按照直观感受，遍历就是返回图中存储的节点列表。
文中代码展示了获取所有和起点联通的节点。使得遍历这个行为，可能不会包含图中所有节点。这和之前理解的遍历有所差别。
而BFS和DFS像是某种条件限制下，沿着某个起点对所有联通的节点进行排序的过程，和直观感受的遍历发生了偏差。
而后查询了遍历的定义，指的是按照某种规则不重复走访所有节点的过程。按照这个定义，BFS和DFS由于无法访问所有节点，不是完全意义上的遍历（可能不联通意味着这不是一个图而是多个图？）。而直接返回存储节点的列表，满足了遍历的定义。
感觉在概念上存在歧义，看评论区发现之前也有类似讨论。因此总结想法并写了出来。

[krahets]

Hi，很好的思考！对于非连通图，需要设定多个遍历起点，才能完整遍历。
BFS 和 DFS 是遍历图的方法，本文主要关注 BFS 和 DFS 的实现，使用连通无向图（最简单的情况）作为案例～

[sidneycao]

请问时间复杂度O(|V|)中的绝对值符号表示啥意思？

[krahets]

Hi，在这里 V 是顶点集合，它的元素数量（即顶点数量）记为 |V|

[sidneycao]

多谢解答～

[fankaikai]

前面时间复杂度都是O(n)这样表示，请问这节BFS的时间复杂度怎么突然变成O(|V|)了？有什么特殊意义吗

[krahets]

没有特殊意义，在这里 V 是顶点集合，它的元素数量（即顶点数量）记为 |V|

[Oscarwasoccupied]

想问下 visited = setVertex是python哪个标准的写法啊？
不应该是visited: Set[Vertex] = {start_vet} 吗

[Oscarwasoccupied]

visited = set[Vertex]([start_vet])
visited: Set[Vertex] = {start_vet}

[Hydrocarbon2023]

同没看懂，visited = {start_vet}就行吧

[liweijian199011]

用java广度优先遍历时，res和visited两个集合是否可换成一个LinkedHashSet，可以包含两个集合的功能，既能判断是否存在，也可以按顺序保存。

[liweijian199011]

附上java用LinkedHashMap来实现，相对来说更加简洁明了一点。

[liweijian199011]

public static Set<Vertex> graphBFS(GraphAdjList graph, Vertex start) {
        Set<Vertex> visited = new LinkedHashSet<>();
        visited.add(start);
        Queue<Vertex> queue = new LinkedList<>();
        queue.offer(start);

        while (!queue.isEmpty()) {
            Vertex v = queue.poll();

            for (Vertex tmp: graph.adjList.get(v)) {
                if (!visited.contains(tmp)) {
                    queue.offer(tmp);
                    visited.add(tmp);
                }
            }
        }
        return visited;
    }

[8456056ftw]

上面说的无序应该是取出来时候的无序 ，而不是指Queue类取值无序。
// -> graph.adjList.get(vet)
for (Vertex adjVet : graph.adjList.get(vet)) {
if (visited.contains(adjVet))
continue; // 跳过已被访问的顶点
que.offer(adjVet); // 只入队未访问的顶点
visited.add(adjVet); // 标记该顶点已被访问
}

[sudashuiqifei]

没有考虑非连通图呀

[UIBEjingqichen]

visited = setVertex 让新手有点晕了，我只了解有两种
visited: Set[Vertex] = set([start_vet])
visited = set([start_vet])

[krahets]

平时就用 visited = set([start_vet]) 最简单的就好～

[1037861070]

邻接矩阵的BFS：

    public static List<Integer> BFS(int A[][], int n) {
        int[] visited = new int[n];
        //BFS遍历结果
        List<Integer> res = new ArrayList<Integer>();
        //辅助队列，用于遍历
        Queue<Integer> queue = new LinkedList<>();
        //找到第一个符合的顶点
        for (int i = 0; i < n; i++) {
            if (!queue.isEmpty()) {
                break;
            }
            for (int j = 0; j < n; j++) {
                if (A[i][j] == 1) {
                    queue.add(i);
                    visited[i] = 1;
                    break;
                }
            }
        }
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            //加入结果
            res.add(cur);
            for (int j = 0; j < n; j++) {
                //不存在边，则跳过
                if (A[cur][j] != 1) {
                    continue;
                }
                //已经访问过，进行跳过
                if (visited[j] == 1) {
                    continue;
                }
                //将当前顶点加入队列继续访问
                queue.add(j);
                //访问当前入队顶点
                visited[j] = 1;
            }
        }
        return res;
    }

邻接矩阵DFS

public static void DFS(int A[][], int cur, int[] visited, List<Integer> res) {
        visited[cur] = 1;
        res.add(cur);
        for (int i = 0; i < A.length; i++) {
            if (A[cur][i] != 1)
                continue;
            if (visited[i] == 1)
                continue;
            DFS(A, i, visited, res);
        }
    }

[Lijingwoquan]

这个bfs和dfs的图太棒了 看明白了 谢谢作者！

[HzcIrving]

尝试写了一版本邻接矩阵版本的BFS

1. 需要在临接矩阵图的类中加上两个功能函数：

    int getVet(int index){
        cout << "节点:" << vertices[index] << endl;
        return vertices[index]; 
    }

    int getIndex(int val){
        int index = find(vertices.begin(), vertices.end(), val) - vertices.begin();
        if (index == size()) {
            throw out_of_range("顶点不存在");
        }
        return index; 
    }

2. 实现方式(BFS)

vector<int> graphBFSAdjMat(GraphAdj &graph, int start){
    /*顶点遍历序列*/   
    vector<int> res;     

    /*获得节点数量*/  
    int nNodes = graph.size(); 

    /*记录访问过的节点*/  
    unordered_set<int> visited = {start}; 

    /*队列，用于实现BFS，FIFO*/ 
    queue<int> que; 
    que.push(start);

    while(!que.empty()){
        int u = que.front();  // FIFO  
        /*获得u对应的节点编号*/ 
        int u_idx = graph.getIndex(u);  

        que.pop(); 
        res.emplace_back(u);  

        int tmp_vet;

        for(int i = 0; i<nNodes; i++){  
            pair<int,int> p = make_pair(u_idx,i);   
            tmp_vet = graph.getVet(i);
            if(graph[p] && visited.count(tmp_vet) == 0){
                visited.emplace(tmp_vet);  
                que.push(tmp_vet); 
            }
        } 
    } 
    return res;  
}

[HzcIrving]

DFS版本

 /*邻接矩阵版本的DFS*/ 
void dfsAdjMat(GraphAdj &graph, unordered_set<int> &visited, vector<int> &res, int vet){  
    visited.emplace(vet);  
    int vet_idx = graph.getIndex(vet);    
    res.emplace_back(vet);  

    for(int i = 0; i<graph.size(); i++){
        pair<int,int> p = make_pair(vet_idx,i);   
        int neighbor = graph.getVet(i);
        if(graph[p] && !visited.count(neighbor)){
            dfsAdjMat(graph, visited, res, neighbor);
        }
    }

}

vector<int> graphDFSAdjMat(GraphAdj &graph, int start){
    /*遍历结果*/ 
    vector<int> res;  

    /*记录访问节点*/ 
    unordered_set<int> visited;   

    // dfs(graph) 
    dfsAdjMat(graph, visited, res, start); 

    return res; 
}


void testBfsAdj(){
    // 顶点列表
    vector<int> vertices = {0, 1, 2, 3, 4, 5, 6};
    // 边列表
    vector<vector<int>> edges = {{0, 1}, {0, 3}, {1, 2}, {2, 5}, {5, 4}, {5, 6}}; 
    GraphAdj graph(vertices, edges);
    // graph.print();  


    vector<int> res = graphBFSAdjMat(graph, 0);  
    vector<int> res_dfs = graphDFSAdjMat(graph, 0);

    cout << "BFS遍历结果"; 
    for(auto& vet:res){
        cout << vet << " ";
    }cout << endl;

    cout << "DFS遍历结果"; 
    for(auto& vet:res_dfs){
        cout << vet << " ";
    }cout << endl;

[nors1993]

对邻接顶点有个疑问：图9-10步骤3中的节点3，没有跟节点1相连的边，不属于节点1的邻接顶点吧？后续步骤没有边与顶点相连的也一样。

[hpstory]

Hi @nors1993 , 是不属于邻接点，队列中的节点只代表接下来要处理的节点，以步骤3为例，处理节点1时，与节点1相连的节点2，4入队，步骤4时，处理节点3，与节点3相连的节点4，6入队，由于有visited的存在，节点4不需要重复处理。

[nors1993]

好的，谢谢，那图中的示例可能需要改下，不然后续的算法小白可能都会有这个疑惑。