chapter_graph/graph_operations/

[giscus[bot]]

chapter_graph/graph_operations/

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

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

[xumaxie]

大佬，在GraphAdjMat 中

for (int[] e : edges) {
    addEdge(e[0], e[1]);
}

这里的edges 能否对应图给个具体的值，这里想不明白。谢谢！

[xumaxie]

for (int[] e : edges) {
addEdge(e[0], e[1]);
}

[krahets]

Hi，请注意区分顶点值和索引的区别。每一个 e 中包含两个顶点，e[0] 和 e[1] ，它们不是顶点的值而是列表索引。

例如，顶点 1 和顶点 2 在顶点列表中的索引分别为 0 和 2，所以在向添加边方法传入的是 (0, 2)

        /* 添加边 */
        // 顶点 1, 2 的索引分别为 0, 2
        graph.addEdge(0, 2);

[kalu5]

Hello! 我刚开始看这里的时候也是很懵，仔细推敲了下，这里的edges的值为边集合，可以参考下面代码，希望有所帮助，不对的地方还望指正。

class Vertex {
  constructor(key, val) {
    this.key= key;
    this.val = val
  }
}

const v0 = new Vertex(0, 1)
const v1 = new Vertex(1, 3)
const v2 = new Vertex(2, 2)
const v3 = new Vertex(3, 5)
const v4 = new Vertex(4, 4)
// [0, 1], [1, 2], [2, 3], [2, 4], [4, 3], [3, 0]
const graph2 = new GraphAdjList(
  [
    [v0, v1],
    [v1, v2],
    [v2, v3],
    [v2, v4],
    [v4, v3],
    [v3, v0],
  ]
)

[FangYuan33]

Hello, Baby K! 有一个微不足道的想法，邻接矩阵 addVertex() 方法中，是不是先向 vertices 中添加顶点值，再获取它的 size() 更合适呢？

[FangYuan33]

我懂了... （为什么没有删除评论的地方....

[SunAlsoRise97]

自定义Vertex对象，将该节点的邻接点列表包含其中，可以省一点空间？不知是否会影响效率

public class Vertex {
    int id;
    int value; 
    List<Vertex> neighbors; // 节点邻居列表
    ...
}

[Ray2310]

在使用邻接表添加边这里有问题， 如果边已经存在那么他还是会添加进去

 /* 添加边 */
    public void addEdge(Vertex vet1, Vertex vet2) {
        if (!adjList.containsKey(vet1) || !adjList.containsKey(vet2) || vet1 == vet2)
            throw new IllegalArgumentException();
        // 添加边 vet1 - vet2
        adjList.get(vet1).add(vet2);
        adjList.get(vet2).add(vet1);
    }

我做的修改是

    public void addEdge(Vertex vet1, Vertex vet2) {
        if (!adjList.containsKey(vet1) || !adjList.containsKey(vet2) || vet1 == vet2)
            throw new IllegalArgumentException();
        // 添加边 vet1 - vet2
        if (!adjList.get(vet1).contains(vet2)){
            adjList.get(vet1).add(vet2);
        }   
        if (!adjList.get(vet2).contains(vet1)){
            adjList.get(vet2).add(vet1);
        }
        
        
    }

[krahets]

Hi，本文没有特别规定两个顶点之间是否可以有多条边相连。在实际中，我们需要根据具体需求来选择。

• 在本文的邻接矩阵实现中，两个顶点之间的边是唯一的；
• 在本文的邻接表实现中，两个顶点之间可以存在多条边；

您的修改可以避免重复，只是会使得添加边的时间复杂度变为 $O(n)$ 。如果需要避免重复边存在，建议使用 HashSet 代替链表存储。

[Ray2310]

ok, thanks

[curly210102]

邻接表删除顶点的复杂度为什么是 O(n + m) 呢？
如果删除边是 O(m)，那么遍历一个顶点的所有邻接点再逐个删除边是 O(m * m)，如果遍历整个邻接表删除边是 O(n * m)？没有领悟到 O(n + m) 的来源🤔

[momomobinx]

不需要遍历，位置是定下来的，直接通过索引删除了

[momomobinx]

你看c++ 的实现好理解

[krahets]

Hi 所有边的数量为 m ，分布在 n 条链表（n 个顶点）中。因此，最差情况下我们需要遍历所有顶点 + 所有边。

[Lztmeow]

Hi, 邻接表删除边(a,b)为什么需要O(m)，O(n)是否就足够了，即从a的表遍历找b—O(n)

[hezhiyun]

Hello，K神. 请问一下/添加顶点/里面的emplace_back(n, 0)如何理解？不太懂

    /* 添加顶点 */
    void addVertex(int val) {
        int n = size();
        // 向顶点列表中添加新顶点的值
        vertices.push_back(val);
        // 在邻接矩阵中添加一行
        adjMat.emplace_back(n, 0);
        // 在邻接矩阵中添加一列
        for (vector<int>& row : adjMat) {
            row.push_back(0);
        }
    }

[krahets]

在这里等价于 adjMat.emplace_back(vector<int>(n, 0)); ，文中的是一种语法糖写法～

[hezhiyun]

噢噢明白了，感谢回答！

[Syl-Ying]

hii, 不太理解用hashtable实现的删除边、删除节点的时间复杂度为什么分别是O(1)， O(n)?

def remove_edge(self, vet1: Vertex, vet2: Vertex):
    """删除边"""
    if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2:
        raise ValueError()
    # 删除边 vet1 - vet2
    self.adj_list[vet1].remove(vet2) # list.remove()最坏情况下遍历vet1跟所有边都相连，需要O(m)？
    self.adj_list[vet2].remove(vet1)

def remove_vertex(self, vet: Vertex):
    """删除顶点O(n+m)"""
    if vet not in self.adj_list:
        raise ValueError()
    # 在邻接表中删除顶点 vet 对应的链表
    self.adj_list.pop(vet)
    # 遍历其他顶点的链表，删除所有包含 vet 的边
    for vertex in self.adj_list: # O(n)
        if vet in self.adj_list[vertex]: # list用in最坏需要O(n)
            self.adj_list[vertex].remove(vet) # list.remove()最坏情况下遍历vet1跟所有边都相连，需要O(m)？

[krahets]

Hi ，这里哈希表实现指的是，每条链表也用哈希表实现，这样删除边就变为在哈希表内删除了

[zhuasdfg]

// 请注意，edges 元素代表顶点索引，即对应 vertices 元素索引
for (int[] e : edges) {
addEdge(e[0], e[1]);
}这里看了好久，才突然发现这是9.1节里讲的边集

[hekpwho]

不好意思，初学者想问一下，那个java实现的邻接表里，关于添加节点的代码

  // 遍历其他顶点的链表，删除所有包含 vet 的边
        for (List<Vertex> list : adjList.values()) {
            list.remove(vet);
        }

remove只会删除list里第一次出现的vet,要是假如出现了重边,即添加了两次addEdge(n6, n7);
即内部结构会变成n6——[n7,n7],n7——[n6,n6],
再执行 G.removeVertex(n7)结果只会变成n6——[n7],这不是不符合实际吗？
我的改法是这样的

// 遍历其他顶点的链表,删除所有包含 vet 的边
        for (List<Vertex> list : graph.values())
            for (int i = 0; i < list.size(); i++) {
                if (list.get(i).equals(vet))
                 {   list.remove(i);//使用list.remove(i)删除节点
                     i--;//并将索引i递减以保持正确的循环遍历
                    }
            }

这样也行吧，感觉这两种存储方式都没考虑到重边

[krahets]

是的，没有考虑重复边的情况

[danghfz]

@hekpwho 你好，首先我认为在遍历的时候去删除节点是不安全的一种行为。
我认为可以在添加边的时候，在遇到重复边的时候就不要添加

/** 添加边 */
    public void addEdge(Character c1, Character c2){
        // 分别在两个顶点的邻接表中添加对方
        if (!adjList.containsKey(c1) || !adjList.containsKey(c2)){
            throw new IllegalArgumentException(c1 + " or " + c2 + " is not a vertex");
        }
        // 考虑重复边的情况
       // 因为如果 c1 链接 c2 那么 c2 链接 c1 （无向图）
        if (adjList.get(c1).contains(c2) || adjList.get(c2).contains(c1)){
            return;
        }
        adjList.get(c1).add(c2);
        adjList.get(c2).add(c1);
    }

[Jaynxe]

hi，想问一下在用链表实现的邻接表中，添加边的复杂度不应该是O(n)吗，因为要遍历找到要添加边的顶点，初学者/(ㄒoㄒ)/~~

[krahets]

Hi 顶点是存在列表中的，可以使用索引直接访问到，然后再插入到以该节点为头节点的链表中，复杂度是 O(1)

[ForBetterCodeNine]

对不起我比较笨， 我想请问一下java的vertex类是怎么实现的呢？

[krahets]

Hi，是在 java/utils/Vertex.java 里实现的，诸如 ListNode , TreeNode 这些公用的类都在 java/utils 文件夹里

[ForBetterCodeNine]

谢谢您，我学到了很多

[ChinaYong]

是不是释放二级指针p总是需要free(p[0]);free(p);这样两个语句？我看C语言的邻接矩阵实现中添加节点操作用到这种操作，但是后面，邻接列表的添加顶点操作只用了free(t->verticesList); 来释放内存，这两者之间有什么差别吗？

[S1-19027]

self.adj_list = dictVertex, list[Vertex]，这段代码不是建立了一个字典吗？不应该是"{}"吗？

[krahets]

可以直接用 {} ，文中的 dict[Vertex, list[Vertex]]() 是更规范的写法，用于表明 key, val 分别是什么类型。请注意，Python 不会强制约束元素类型，即使这样声明，我们仍然可以存储其他类型的数据。

[S1-19027]

”添加顶点：在邻接表中添加一个链表，并将新增顶点作为链表头节点“。我并没有找到有关链表的实现，请问是哪一步？

[krahets]

Hi，在具体实现中，逻辑上是链表，具体使用的是列表：

        # 在邻接表中添加一个新链表
        self.adj_list[vet] = []

[fl0w1nd]

graph_adjacency_list.c有一处注释错误，位于删除顶点函数中

graph->vertices[graph->size - 1] = 0; // 将被删除顶点的位置置 0

这个注释应该是将最后一个顶点的位置置0,因为该顶点已经前移。

[pluvi0phile]

求树和图的其它内容，包括prim，kruskal，dijkstra，Floyd，topological sorting，critical path算法，如果以后能包含更多严书的内容，肯定能吸引来许多考研的读者

[krahets]

好的，等有时间会写的～

[liweijian199011]

想问一下，邻接表链表的实现方式是什么样的。是指顶点是一个单独的List，边是相连的顶点组成的链表吗？

[hpstory]

Hi @liweijian199011 ， 你可以理解为邻接表就是图中每个顶点对应一个与该顶点相连的所有顶点的集合，这个集合可以是列表也可以是链表。两个点a, b之间有边就相当于b在a对应的集合中，或者a在b对应的集合中。

[liweijian199011]

因为看到你上面对比复杂度的时候是把邻接表链表的方式和邻接表哈稀表的方式分开比较了，但是文章中并没有提及邻接表链表的实现方式。你上面评论表述的我看用哈稀表的方式已经表现出来了，邻接表链表的方式应该也是同样的思想，但是具体实现方式要怎么来实现？比如是用一个列表中嵌套链表的方式，列表中每个元素都是一个顶点相连顶点的链表，这样是否可以？

[hpstory]

Hi @liweijian199011 ，可以的，列表的每个元素是链表的头节点。

[kneep]

// 请注意，edges 元素代表顶点索引，即对应 vertices 元素索引
for (const vector<int> &edge : edges) {
      addEdge(edge[0], edge[1]);
}

edges既然是注释中所说的意思，用std::pair逻辑上是不是更清晰？

[StefanGuan]

听你这么说这几句才看懂

[Dean-Q]

hi, 大佬，有没有可能实现代码全屏观看的时候，设置prev 和 next 按钮悬停在页面上可移动啊，不然会遮盖代码和图示了

[krahets]

Hi 全屏观看实际上是打开了一个新的网页，你可以把文章和新网页任意排布大小和位置～

[liweijian199011]

请问在java实现中，用HashMap来实现邻接表，value是一个ArrayList，那删除边的操作就不用遍历了，删除边的时间复杂度不应该O(1)吗？但是看9.2.2中描述的删除边的操作时间复杂度是O(m)。

[krahets]

Hi，这里统计的是最差时间复杂度。最差情况下，所有边都集中在一个链表上（在这里是 ArrayList），此时遍历这个 ArrayList 需要 O(m) 时间。

[Fulin-Gao]

效率对比部分不是很理解，请问邻接表（链表）和邻接表（哈希表）的区别是什么？
一个链表包含的是与对应顶点相连的顶点集合；哈希表的键是各个顶点，值是与对应顶点相连的顶点集合。
如果是这样请问，邻接表（哈希表）的删除顶点为什么是O(n)呢，直接定位到待删除顶点O(1)，寻找其它相关边的时间复杂度应该怎么算呢，不需要遍历吗？

[krahets]

Hi，在最差情况下，所有节点集中在一个链表（列表中），此时从这个长度为 n 的列表中删除节点，达到最差时间复杂度 O(n)

[xinzaibuyan]

邻接表的添加边函数，需要加一点代码

[xinzaibuyan]

for(auto vel : adjList[vel1]){
    if(vel->val == vel2->val){
           return;
    }
}

邻接表的添加边函数，需要加一点代码，否则边会重复添加

[krahets]

我们没有严格规定两条节点之间只能有一条边，所以不加这段也行

[Lijingwoquan]

9.2.1的删除操作

/* 删除顶点 */
void removeVertex(GraphAdjMat *graph, int index) {
    if (index < 0 || index >= graph->size) {
        fprintf(stderr, "顶点索引越界\n");
        return;
    }
    // 在顶点列表中移除索引 index 的顶点
    for (int i = index; i < graph->size - 1; i++) {
        graph->vertices[i] = graph->vertices[i + 1];
    }
    // 在邻接矩阵中删除索引 index 的行
    for (int i = index; i < graph->size - 1; i++) {
        for (int j = 0; j < graph->size; j++) {
            graph->adjMat[i][j] = graph->adjMat[i + 1][j];
        }
    }
    // 在邻接矩阵中删除索引 index 的列
    for (int i = 0; i < graph->size; i++) {
        for (int j = index; j < graph->size - 1; j++) {
            graph->adjMat[i][j] = graph->adjMat[i][j + 1];
        }
    }
    graph->size--;
}

我觉得最后一个循环的i应该可以是i < graph->size - 1

[Lijingwoquan]

因为第二个循环以及删除一行了 下面删除列的时候不用再考虑那一行了

[Dynamite2003]

希望作者可以添加一下其他的表示方式比如关联矩阵，正向表和逆向表之类的，谢谢！

[user-po]

hello，请问为什么初始化的时候我看只初始化了整个矩阵的一半呢，跟图中不太符合呀

[Tianyu-Huang-letsgo]

在邻接表删除顶点函数实现中，是否可以遍历要删除顶点的列表，再用邻接表索引遍历到的顶点进行删除操作，这样最大复杂度也是O(n+m),但是当顶点足够多，边足够少复杂度会降到O(1+m)

[HuaWang135608]

邻接表这种写法不能表示非连通图吧

[1435646097]

链表中只有当前顶点，不就是非连通图了

[CcYcC8]

请问下大佬，C#的这个Vertex是一个特殊的类吗？有没有相关介绍啊，看不懂了o(╥﹏╥)o

[krahets]

建议前往代码仓库 https://github.com/krahets/hello-algo 下载完整的源代码，可一键运行

[Yerosius]

建议增加链式前向星