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,因为该顶点已经前移。

[timmycheng]

根据我老师和Wikipedia的说法，邻接矩阵中添加顶点的时间复杂度是O(n^2)

[timmycheng]

而且Google上针对这个问题基本上都是在困惑为什么是O(n^2)，解释一般都是（我看到两次）说矩阵在添加顶点的时候重新分配了内存，所以本质上是把所有现存的数组元素复制了一遍，关于这点我其实觉得蛮牵强的……

[sinabs]

java的代码里面的

PrintUtil.printMatrix(adjMat);

可以修改

adjMat.forEach(System.out::println);

输出的内容

顶点列表 = [1, 3, 2, 5, 4]
邻接矩阵 =
[0, 1, 0, 1, 0]
[1, 0, 1, 0, 0]
[0, 1, 0, 1, 1]
[1, 0, 1, 0, 1]
[0, 0, 1, 1, 0]

[2893197486]

邻接表Java写法顶点类是不是需要重写hashcode方法，相同值的顶点算是同一个

[huanghejian]

我去这个图和哪个树一样，有点难懂

[zhuiguang49]

基于邻接矩阵的实现中printVector()和printVectorMartix()函数是不是漏了函数定义？

void printVector(const vector<int>& vec) {
    cout << "[";
    for (size_t i = 0; i < vec.size(); i++) {
        cout << vec[i];
        if (i != vec.size() - 1) cout << ", "; 
    }
    cout << "]" << endl;
}

void printVectorMatrix(const vector<vector<int>>& mat) {
    for (const auto& row : mat) {
        for (size_t i = 0; i < row.size(); i++) {
            cout << row[i];
            if (i != row.size() - 1) cout << " "; 
        }
        cout << endl; 
    }
}

[ouyangyipeng]

这种到处都一样的一般是默认了~

[solaxido]

文中提到基于邻接表实现时，删除顶点需要遍历整个邻接表，然后删除对应的顶点和边。
不过如果是无向图，还能优化下，降低复杂度。
比如例子中删除顶点3，邻接表中记录与3相连的只有顶点2，那接下来只在顶点2中删除链表中的3就行了。这样就不用遍历整个邻接表了。
这样在图的节点比较多，而每个节点所对应的边较少时，效率也能够高。
不过在有向图就没办法这样子做了。

[0101qwe]

for edge in edges:
self.add_vertex(edge[0])
self.add_vertex(edge[1])
self.add_edge(edge[0], edge[1]) 这里edge[0], edge[1] 不是一个列表吗，怎么edge[0]会是Vertex

[MAKEE666]

这里的edges不是邻接矩阵，而是类似上一节定义的边的集合E：
E = {(1, 2), (1, 3), (1, 5), (2, 3), (2, 4), (2, 5), (4, 5)}
只是集合E里面存储的是顶点的值，edges里则换成顶点值的索引，即按照vertices = {1, 3, 2, 5, 4}的话，edges = {{0, 2}, {0, 1}, {0, 3}, {2, 1}, {2, 4}, {2, 3}, {4, 3}}，所以edge是{0, 2}等长度为2的数组，代表顶点1到顶点2的边；edge[0]就是顶点1的索引，edge[1]就是顶点2的索引。

[MAKEE666]

邻接表的话，没用列表索引，用的是Vertex类和哈希表，那edges = E = {{1, 2}, {1, 3}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {4, 5}}，edge就是{1, 2}等长度为2的数组，代表顶点1到顶点2的边；edge[0]就是顶点1，edge[1]就是顶点2。

[bzanniupiswadwas]

edges[0], edges[1]才是列表，edge[0]是Vertex，edge不是二维列表，edges才是哦！

[Weining2020]

Hi, 9.2.2 基于邻接表的实现 这里对于各种操作的复杂度分析，是关于 用链表实现的邻接表的分析吧？可是下面的graph_adjacency_list.cs却是用哈希表实现的邻接表，有没有用链表实现的邻接表的代码呢？我看的是c#代码。

[liriyao]

上面提到：如果每个顶点都是唯一的 Vertex 实例，删除某一顶点之后就无须改动其他顶点了。
但删除节点的代码不一样有：将该顶点之后的顶点向前移动，以填补空缺的操作吗？实例到底做了什么

[Hermesfish]

邻接矩阵删除顶点adjMat.RemoveAt(index);和邻接表删除顶点adjList.Remove(vet);。一个是二维数组，另一个是哈希表，具体的删除过程是不一样的。它两的名称不同：RemoveAt和Remove，参数也不同，一个是数组索引，另一个是key值。

[ChopperLee2011]

 // 删除边 vet1 - vet2
        this.adjList.get(vet1).splice(this.adjList.get(vet1).indexOf(vet2), 1);
        this.adjList.get(vet2).splice(this.adjList.get(vet2).indexOf(vet1), 1);

这里会因为indexOf没有找到返回-1，从而错误删除了数组末尾的元素
可以改成

    const edges1 = this.adjList.get(vet1)!;
    const index1 = edges1.indexOf(vet2);
if(index1 > -1 ) {
 edges1.splice(index1, 1)
}

[cuizisong]

我有一个想法，给邻接表添加边加一句判断这条边是否已经存在的语句，比如
for(Vertex *v : adjList[vet1]){
if(v==vet2) throw invalid_argument("这条边已经存在");
}//不过无向图的话需要两个这样的代码段而且不省时间

[Jiaminx7]

大神，基于哈希表的领接表，删除边的复杂度为啥是O(1)呢？如果我没理解错的话，文中用的python代码是用哈希表实现的，然后删除边的复杂度好像是O(m)呀，因为要遍历value这个list的所有vertex然后删除它，所以是O(m)。我哪儿理解错了么

[HaoxinLan]

“判断是否邻接 “也是要遍历value这个list吧，是不是也是O(m)，按照文中用哈希表来实现图存储，只是找顶点的时间是O(1)，涉及到边的比较仍是O(m)。如果将边改为用set来存储，那么查询的时间复杂度就是O(1)了

[Jiaminx7]

完全同意你说的，然而代码中用的是list不是set，所以看看能不能等到作者的解释吧哈哈

[krahets]

Hi，邻接表（链表）对应本文实现，而邻接表（哈希表）专指将所有链表替换为哈希表后的实现。已在文中添加说明，抱歉造成误解

[xiaozhuge123]

day07

[WangYun0918]

疑问：删除顶点：需遍历整个邻接表，删除包含指定顶点的所有边，使用
时间 O（n+m），从实现代码分析
public void removeVertex(Vertex vet) {
if (!adjList.containsKey(vet))
throw new IllegalArgumentException();
// 在邻接表中删除顶点 vet 对应的链表
adjList.remove(vet);
// 遍历其他顶点的链表，删除所有包含 vet 的边
for (List list : adjList.values()) {
list.remove(vet);
}
}

[WangYun0918]

疑问：
删除顶点：需遍历整个邻接表，删除包含指定顶点的所有边，使用
时间 O（n+m），从实现代码分析
public void removeVertex(Vertex vet) {
if (!adjList.containsKey(vet))
throw new IllegalArgumentException();
// 在邻接表中删除顶点 vet 对应的链表
adjList.remove(vet);
// 遍历其他顶点的链表，删除所有包含 vet 的边
for (List list : adjList.values()) {
list.remove(vet);
}
}
最后
// 遍历其他顶点的链表，删除所有包含 vet 的边
for (List list : adjList.values()) {
list.remove(vet);
}
这个时间复杂度不应该是 O（(n-1)*m）吗 ？为啥最后删除的时间复杂度变成了O(n+m)呢？表示不解

[Frankie18581]

希望可以出个伪代码呀，一是看一长串代码挺费时的，二是想先理解一下思路，自己写一写呢