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

[danielwgo]

  /* 删除顶点 */
    removeVertex(index) {
        if (index >= this.size()) {
            throw new RangeError('Index Out Of Bounds Exception');
        }
        // 在顶点列表中移除索引 index 的顶点
        this.vertices.splice(index, 1);

        // 在邻接矩阵中删除索引 index 的行
        this.adjMat.splice(index, 1);
        // 在邻接矩阵中删除索引 index 的列
        for (const row of this.adjMat) {
            row.splice(index, 1);
        }
    }

删除顶点：在邻接矩阵中删除一行一列。当删除首行首列时达到最差情况，需要将(n - 1)^2个元素“向左上移动”，从而使用O(n^2)时间。

原文有误，在邻接矩阵中删除顶点的时间复杂度应该为 O(n)，而不是O(n^2)。

[ghost]

graph_adjacency_list.c：
删除顶点函数removeVertex在遍历其它顶点的链表时（第一个for循环），进入了死循环，程序运行时卡在了删除顶点函数那里。原函数在遍历其它顶点的链表时，是遍历的整个图，即所有的链表，包括已经删除的链表。但以待删除节点为顶点的链表在第一个while循环之后，其头节点和邻接节点都成为了悬空指针，因此不应该访问这个链表。所以加一个if语句，不要遍历以待删除节点为顶点的链表即可：

/* 删除顶点 */
void removeVertex(GraphAdjList *graph, Vertex *vet) {
    AdjListNode *node = findNode(graph, vet);
    assert(node != NULL);
    // 在邻接表中删除顶点 vet 对应的链表
    AdjListNode *cur = node, *pre = NULL;
    while (cur) {
        pre = cur;
        cur = cur->next;
        free(pre);
    }
    // 遍历其他顶点的链表，删除所有包含 vet 的边
    for (int i = 0; i < graph->size; i++) {
        cur = graph->heads[i];
        pre = NULL;
    // 修改的部分：在进入while循环遍历链表之前，添加条件语句确保不要遍历到先前已被释放的顶点所在的链表
        if (cur != node) {
            // 在符合if条件后，进入对某一合法链表的遍历
            while (cur) {
                pre = cur;
                cur = cur->next;
                if (cur && cur->vertex == vet) {
                    pre->next = cur->next;
                    free(cur);
                    break;
                }
            }
        }
    }
    // 将该顶点之后的顶点向前移动，以填补空缺
    ...
}

[ztkuaikuai]

9.2.2 JS和TS代码片段中的删除边函数好像少了个判断条件

如果传入的两个顶点不为邻接点，那么在adjList两顶点对应的value中会删除最后一个顶点即splice(-1, 1)

如果没错的话是否可以改成这样：（如果我理解错了还请指正）

removeEdge(vet1: Vertex, vet2: Vertex): void {
        if (
            !this.adjList.has(vet1) ||
            !this.adjList.has(vet2) ||
            vet1 === vet2 ||
            this.adjList.get(vet1).indexOf(vet2) !== -1 // 判断这两个顶点是否邻接(无向图)
        ) {
            throw new Error('Illegal Argument Exception');
        }
        // 删除边 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);
    }

[ztkuaikuai]

修改下判断条件，应该是全等
this.adjList.get(vet1).indexOf(vet2) === -1

[mingliangio]

邻接矩阵：初始化矩阵时怎么推算的？就是每个格子里的 0 或 1

[yuanlongdong]

有边1，无·边0，自己与自己每边也就是主对角线

[yuanlongdong]

#include
#include
using namespace std;

class AmGraph
{
vector vexs;
vector<vector> arcs;

public:

AmGraph(const vector& vex1, const vector<vector>& arc1)
{
vexs = vex1;
// arcs.resize(n, vector(n, 0));
arcs = arc1;

}

int sumDu(char val)
{
int index = locatevex(val); // 获取顶点的位置索引
if (index == -1) {
cout << "顶点 " << val << " 不存在。" << endl;
return -1; // 如果顶点不存在，返回 -1 表示错误
}

int count = 0;
// 遍历该顶点对应的邻接矩阵行，计算度
for (int i = 0; i < arcs[index].size(); i++)
{
    if (arcs[index][i] != 0)
    {
        count++;
    }
}

return count;

}

//获取顶点数
int vexnum()
{
return vexs.size();
}

//添加顶点
void addvex(char val)
{
int n = vexnum();
vexs.push_back(val);

arcs.emplace_back(vector<int>(n, 0));
for (vector<int>& num : arcs)
{
    num.push_back(0);
}

}

// 删除顶点
void removeVex(char val)
{
int index = locatevex(val); // 获取顶点的位置索引
if (index == -1) {
cout << "顶点 " << val << " 不存在。" << endl;
return;
}

// 从顶点列表中删除顶点
vexs.erase(vexs.begin() + index);

// 从邻接矩阵中删除对应的行
arcs.erase(arcs.begin() + index);

// 从邻接矩阵的每一行中删除对应的列
for (auto& row : arcs) {
    row.erase(row.begin() + index);
}

}

//获取顶点位置
int locatevex(const char& val)
{
for (int i = 0;i < vexs.size();i++)
{
if (vexs[i] == val)
{
return i;
}
}
return -1;
}

//添加边
void addarc(char v1, char v2)
{
int i = locatevex(v1);
int j = locatevex(v2);
if (i != -1 && j != -1)
{
arcs[i][j] = 1;
arcs[j][i] = 1;
}
}

//删除边
void removeArc(char v1,char v2)
{
int i = locatevex(v1);
int j = locatevex(v2);
if (i != -1 && j != -1)
{
arcs[i][j] = 0;
arcs[j][i] = 0;
}
}

void printvex()
{
for (const char& num : vexs)
{
cout << num << " ";
}
cout << endl;
}
//遍历
void printGraph()
{
for (const vector& vec : arcs)
{
for (const int& num : vec)
{
cout << num << " ";
}
cout << endl;
}
cout << endl;
}
};

int main()
{

vector<char> vec = { 'a','b','c','d' };
vector<vector<int>> adjacencyMatrix = {
  {0, 1, 0, 1},
  {1, 0, 1, 0},
  {0, 1, 0, 1},
  {1, 0, 1, 0}
};

AmGraph G(vec,adjacencyMatrix);  

G.printvex();
G.printGraph();

G.addvex('f');
G.printvex();
G.printGraph();

G.addvex('g');
G.printvex();
G.printGraph();
cout << "a的度:" << G.sumDu('a') << endl;

G.removeVex('f');
G.removeVex('g');
G.printvex();
G.printGraph();

G.removeArc('b', 'a');
G.removeArc('d', 'a');
G.printGraph();

return 0;

}

[yuanlongdong]

c++初始化直接调用拷贝构造即可
AmGraph(const vector& vex1, const vector& arc1)
{
vexs = vex1;
arcs = arc1;
}

[xiaozhabb]

请问为什么利用邻接表(哈希表)实现时删除边的时间复杂度是1呢? 找到对应的边确定key需要1, 在这个顶点的链表(动态数组)中找到这条边为什么也是1呢?

[ltysvip]

我也觉得这里错了，如果把ArrayList改为HashSet就可以做到

[wsy20041027]

C环境下基于邻接表的实现的代码中，那个自定义Vertex类型具体是什么组成呢？代码里没有具体说明。

[xienumfirst]

同问

[akababocai]

typedef struct Vertex {
int data; // 顶点数据
} Vertex;

[uncleyuan001]

def add_vertex(self, val: int):
    """添加顶点"""
    n = self.size()
    # 向顶点列表中添加新顶点的值
    self.vertices.append(val)
    # 在邻接矩阵中添加一行
    new_row = [0] * n
    self.adj_mat.append(new_row)
    # 在邻接矩阵中添加一列
    for row in self.adj_mat:
        row.append(0)

是否在最后一行末尾多添加了一个0呢？添加行的时候最后一行已有n个0了

[uncleyuan001]

9.2.1 的python代码

[wnnce]

最后一行初始化时长度是矩阵没有 append 之前的，应该也是需要添加的

n = self.size()

[Zsf111]

假设有一个4行4列的矩阵，完成add_vertex操作后这个矩阵会变成5行5列。

• n = 4
• 更新vertices列表
• new_row = [0, 0, 0, 0]
• 把new_row添加至adj_mat，这时矩阵变为5行4列
• 循环在每一行末尾添加一个0，这时矩阵变为5行5列

[HyperionChiu]

看了半天才知道这里的list是hashSet，所以判断顶点是否邻接的效率是O（1）

[HyperionChiu]

不对，人家构造list用是arraylist，但是不是链表是数组实现所以差不多，都是O（1）

[HyperionChiu]

不对呀，arraylist查找特定元素的是O（n），他写错了吧？

[benlinzi]

在邻接矩阵的删除顶点中，还有种方法就是将该顶点对应的行和列都置为0，然后增加一个变量用来表示这个顶点是不是为空即可，可以降低时间复杂度

[Ares-bit]

这样没法按照size遍历了

[Zyh20000923]

邻接矩阵和邻接表操作图示tab切换好像会互相影响

[Marbluec]

有点看不懂了，┭┮﹏┭┮

[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]