1. Introduction

图形由顶点/节点和连接这些顶点的边/线组成。
图可以是无向的(意味着在与每个双向边相关联的两个顶点之间没有区别)或者可以指向图(意味着其边缘从一个顶点指向另一个顶点但不一定在另一个方向上)。
可以对图形进行加权(通过向每个边缘分配权重,其表示与该连接相关联的数值)或者图形可以是未加权的(所有边缘具有单位权重1或者所有边缘具有相同的恒定权重)。

1-1. 简单图形

我们在VisuAlgo中讨论的大多数图形问题都涉及简单图

在一个简单图中,没有(自 - )环边(连接顶点与自身的边),没有多边/平行边(同一对顶点之间的边)。换句话说:在一对不同的顶点之间最多只能有一条边。

简单图中的边E的数量范围仅为0到O(V2)。

简单图上的图算法比非简单图上的算法更容易。

1-2. 术语,第1部分

无向边e:(u,v)被认为是以其两个端点顶点入射:u和v。如果两个顶点与公共边缘一起入射,则它们被称为相邻(或邻居)。例如,边(0,2)入射到顶点0 + 2并且顶点0 + 2是相邻的。

如果两个边缘与公共顶点一起入射,则它们被称为相邻边缘。例如,边(0,2)和(2,4)是相邻的。

无向图中的顶点v的度数是与v一起入射的边的数量。度为0的顶点被称为孤立顶点。例如,顶点0/2/6分别具有2/3/1的度数。

图G的子图G'是包含G的顶点和边的子集的(较小的)图。例如,三角形{0,1,2}是当前显示的图的子图。

1-3. 术语,第2部分

(无向)图G中(长度为n)的路径是顶点序列{v0,v1,...,vn-1,vn},使得在vivi+1∀i∈[0..n-1]之间存在边缘。
如果路径上没有重复的顶点,我们称这样的路径为简单路径。
例如,{0,1,2,4,5}是当前显示的图形中的一个简单路径。

1-4. 术语,第3部分

如果在G的每对不同顶点之间存在路径,则能将无向图G称为连接图。例如,当前显示的图不是连接图。

如果要把无向图C称为无向图G的连通分量,它必须符合以下的条件。 1)CG的子图; 2) C是个连接图; 3)没有G的连通子图将C作为子图并且包含不在C中的顶点或边(即C是满足其他两个标准的最大子图)。

例如,当前显示的图形具有{0,1,2,3,4}和{5,6}作为其两个连接分量。

1-5. 术语,第4部分

在有向图中,前面提到的一些术语有小的调整。

如果我们有一个有向边e:(u→v),我们说v与u相邻但不一定在另一个方向上。例如,1在当前显示的有向图中与0相邻但0与1不相邻。

在有向图中,我们必须进一步将顶点v的度数区分为度数和度数。度数/出度是分别从v进入/离开的边数。例如,顶点1的入度/出度分别为2/1。

在有向图中,我们定义了强连通分量(SCC)的概念。在当前显示的有向图中,我们将{0},{1,2,3}和{4,5,6,7}作为其三个SCC。

1-6. 术语,第5部分

循环是以相同顶点开始和结束的路径。

非循环图是不包含循环的图。

在无向图中,每个无向边都会导致一个微不足道的循环,尽管我们通常不会将其归类为循环。

非循环的有向图具有特殊名称:有向无环图(DAG),如上所示。

我们可以在非循环图上执行有趣的算法,这些算法将在此可视化页面和VisuAlgo中的其他图形可视化页面中进行探索。

1-7. 特殊图形

具有涉及其顶点和/或边结构的特定属性的图可以使用其特定名称来调用,如树(如当前所示),完整图,二分图,有向无环图(DAG),以及使用频率较低的图:平面图,线图,星图,轮图等

在此可视化中,我们将在稍后突出显示前四个特殊图表。

2. 图是普遍的

图表在现实生活中经常以各种形式出现。因此,解决图形问题的最重要部分是图形建模部分,即将手中的问题简化为图形术语:顶点,边,权重等。

2-1. 示例 - 更容易看到,1

社交网络:顶点可以代表人,边缘代表人与人之间的联系(通常是无向和未加权)。
例如,请参阅当前显示的无向图。此图显示了它们之间的7个顶点(人)和8个边(连接/关系)。也许我们可以提出这样的问题:
  1. 谁是0号的朋友?
  2. 谁拥有最多的朋友?
  3. 有没有孤立的人(那些没有朋友的人)?
  4. 两个陌生人之间是否有共同的朋友:3号人和5号人?
  5. 等等...

2-2. 示例 - 更容易看到,2

运输网络:顶点可以表示站点,边缘表示站点之间的连接(通常是加权的)。

例如,请参阅当前显示的有向加权图。该图显示了5个顶点(站点/位置)和6个边缘(站点之间的连接/道路,具有正的权重行进时间,如图所示)。假设我们正在开车。我们或许可以问一下从0号站到4号站的路径是什么,以便我们用最少的时间到达4号站?

讨论:想想其他一些可以建模为图形的现实生活场景。

2-3. 示例 - 更难看到

[This is a hidden slide]

3. 模式

要在图形绘制模式之间切换,请选择相应的标题。 我们有:

  1. U/U = 无向/不加权,
  2. U/W = 无向/加权,
  3. D/U = 有向/不加权, and
  4. D/W = 有向/加权.

我们根据所选模式限制您可以绘制的图形类型。

4. 可视化

您可以单击任何一个示例图形并可视化上图。

您还可以直接在可视化区域中绘制图形:

  1. 点击空白区域添加顶点,
  2. 单击顶点,按住,将绘制的边缘拖动到另一个顶点,然后将其放在那里以添加边缘(PS:此操作不适用于移动用户;您需要鼠标),
  3. 选择顶点/边缘并按“删除”键删除该顶点/边,
  4. 选择边缘并按“Enter”以更改该边缘的权重[0..99],
  5. 按住“Ctrl”,然后您可以单击并拖动顶点。

4-1. 可视化约束

我们将VisuAlgo中讨论的图形限制为简单图形。请参阅本幻灯片中的讨论。

我们还将可以在屏幕上绘制的顶点数限制为最多10个顶点,范围从顶点0到顶点9.这与上面的简单图形约束一起,将无向/有向边的数量限制为45 /分别为90。

5. 图形的示例

所有示例图都可以在这里找到。
目前,我们为每个类别提供七个示例图表(U / U,U / W,D / U,D / W)。
请注意,在加载其中一个示例图表后,您可以进一步修改当前显示的图表以满足您的需要。

6. 特殊图形

Tree,Complete,Bipartite,Directed Acyclic Graph(DAG)是特殊图的属性。在上面的可视化/绘图区域中修改图形时,会立即检查和更新这些属性。

还有其他不太常用的特殊图形:平面图,线图,星图,轮图等,但在绘制它们时,它们当前在此可视化中不会被自动检测到。

6-1. 特殊图形 - 树,第1部分

树是具有V顶点和E = V-1边的连通图,非循环,并且在任何顶点对之间具有一条唯一路径。通常,树在无向图上定义。

无向树(见上文)实际上包含琐碎的循环(由其双向边缘引起),但它不包含非平凡循环。有针对性的树显然是非循环的。

由于树只有V-1边,因此它通常被认为是稀疏图。

我们目前显示我们的U / U:Tree示例。您可以进入“探索模式”并绘制自己的树木。

6-2. 特殊图形 - 树,第2部分

并非所有树都具有相同的图形绘制布局,其顶部具有特殊根顶点,底部具有叶顶点(顶点为1)。上面显示的(星)图也是树,因为它满足树的属性。

将其顶点之一指定为根顶点的树称为有根树。

我们总是可以通过将特定顶点(通常是顶点0)指定为根来将任何树转换为根树,并从根运行DFS或BFS算法。

6-3. 特殊图形 - 树,第3部分

在有根树中,我们有层次结构(父,子,祖先,后代),子树,级别和高度的概念。我们将通过示例说明这些概念,因为它们的含义与现实生活中的对应物一样:
  1. 0/1/7/9/4的父级分别为none / 0 / 1 / 8 / 3,
  2. 0/1/7的子女分别为{1,8} / {2,3,6,7} / none,
  3. 4/8的祖先分别为{3,1,0} / {0},
  4. 1/8的后代分别是{2,3,4,5,6,7} / {9},
  5. 以1为根的子树包括1,其后代和所有相关边,
  6. 0/1/2/3级成员分别为{0} / {1,8} / {2,3,6,7,9} / {4,5},
  7. 这个有根树的高度是它的最高级别= 3。

6-4. 特殊图形 - 树,第4部分

对于有根树,我们还可以定义其他属性:
二叉树是一个有根树,其中一个顶点最多有两个孩子,它们被恰当地命名为:left和right child(左子节点和右子节点)。在讨论二叉搜索树二叉堆时,我们经常会看到这种形式。
满二叉树是一个其中每个非叶(也称为内部)顶点恰好有两个子节点的二叉树。上面显示的二叉树符合此标准。
一个完全二叉树的每个级别都被完全填充,除了最后一级可能尽可能地填充。我们经常会在讨论二叉堆时看到这种形式。

6-5. 特殊图表 - 完整

完整图是具有V个顶点和 E = V*(V-1)/2 个边(或E = O(V2)的图,即在任何顶点对之间存在边。通常,完整图表用KV表示。
完整图是最密集的简单图。
我们目前展示了我们的U/W: K5示例。您可以进入“探索模式”并绘制自己的完整图形(虽然对于较大的V来说有点单调乏味)。

6-6. 特殊图表 - 二分法

二分图是具有V个顶点的无向图,其可以被划分为大小为mn的两个不相交的顶点集,其中V = m + n。同一组的成员之间没有边缘。二分图也没有奇数长度的圈(cycle)。
我们目前展示了我们的U / U:Bipartite示例。您可以进入“探索模式”并绘制自己的二分图。
二分图也可以是完整的,即来自一个不相交集的所有m个顶点都连接到来自另一个不相交集的所有n个顶点。当m = n = V / 2时,这样的完全二分图也具有E = O(V2

6-7. 特殊图表 - DAG

Directed Acyclic Graph (DAG) is a directed graph that has no cycle, which is very relevant for Dynamic Programming (DP) techniques.


Each DAG has at least one Topological Sort/Order which can be found with a simple tweak to DFS/BFS Graph Traversal algorithm. DAG will be revisited again in DP technique for SSSP on DAG.


We currently show our D/W: Four 0→4 Paths example. You can go to 'Exploration Mode' and draw your own DAGs.

7. 三个图形数据结构

有许多方法可以将图形信息存储到图形数据结构中。在此可视化中,我们显示了三个图形数据结构:邻接矩阵,邻接列表和边缘列表 - 每个都有自己的优点和缺点。

7-1. 邻接矩阵(AM)

邻接矩阵(AM)是一个方阵,其中条目AM [i] [j]示出从顶点i到顶点j的边缘权重。对于未加权的图形,我们可以为所有边缘权重设置单位权重= 1。 'x'表示该顶点不存在(已删除)。

我们简单地使用大小为VxV的C ++/Python/Java原生2D数组来实现这种数据结构。

7-2. AM-继续

空间复杂度分析:不幸的是,AM需要O(V2)的大空间复杂度,即使图形实际上是稀疏的(边缘不多)。

讨论:了解AM的大空间复杂性,何时使用它是有益的?或者AM总是一个劣质的图形数据结构,永远不该使用?

7-3. 答案

[This is a hidden slide]

7-4. 邻接列表(AL)

邻接列表(AL)是有V个列表的数组,每个顶点一个(通常以递增的顶点数排序),其中对于每个顶点i,AL [i]存储i的邻居列表。对于加权图,我们可以存储(邻居顶点,此边的权重)对。
我们使用一个嵌套的Vector对(用于加权图)来实现此数据结构。在C++中:vector<vector<pair<int, int>>> AL; Python: AL = [[] for _ in range(N)] Java: Vector<Vector<IntegerPair>> AL; // Java 中的IntegerPair 类似于 C++中的pair<int, int>

7-5. Class IntegerPair (in Java)

class IntegerPair implements Comparable<IntegerPair> {
Integer _f, _s;
public IntegerPair(Integer f, Integer s) { _f = f; _s = s; }
public int compareTo(IntegerPair o) {
if (!this.first().equals(o.first())) // this.first() != o.first()
return this.first() - o.first(); // is wrong as we want to
else // compare their values,
return this.second() - o.second(); // not their references
}
Integer first() { return _f; }
Integer second() { return _s; }
}
// IntegerTriple is similar to IntegerPair, just that it has 3 fields

7-6. 为什么用Vector对的Vector?

我们使用对,因为我们需要存储每条边的信息对:(邻居顶点,边权重),其中对于未加权图,权重可以设置为0或未使用。
由于Vector的自动调整大小功能,我们使用Vector来存储对。如果我们有一个顶点的k个邻居,我们只需将k个邻居添加到该顶点的最初为空的Vector对象(此Vector可以用Linked List替换)。

我们在外面再用一层Vector来储存Vector对,即如果我们想枚举顶点u的邻居,我们使用AL [u](C ++/Python)或AL.get(u)(Java)来访问正确的Vector。

7-7. AL-继续

空间复杂度分析:AL具有O(V + E)的空间复杂度,比AM效率高得多,并且通常是大多数图形算法中的默认图形数据结构。
讨论:AL是最常用的图形数据结构,但讨论AL哪种情况实际上不是最佳的图形数据结构?

7-8. 答案

[This is a hidden slide]

7-9. 边缘列表(EL)

边缘列表(EL)是具有连接顶点及其权重的边的集合。通常,这些边是按权重增加来排序的,例如, Kruskal's algorithm的一部分用于最小生成树(MST)的问题。但是,在此可视化中,我们通过增加第一个顶点数来对边进行排序,如果是连接,则通过增加第二个顶点数来对边进行排序请注意,无向/有向图中的双向边分别列出一次/两次。
我们使用三元组Vector来实现这种数据结构。C++:vector<tuple<int, int, int>> EL; Python: EL = [] Java: Vector<IntegerTriple> EL; // Java中的IntegerTriple类似于C++中的tuple<int, int, int>

7-10. EL-继续

空间复杂度分析:EL具有O(E)的空间复杂度,其比AM更有效并且与AL一样有效。

讨论:除了Kruskal的最小生成树(MST)算法之外,详细说明EL的潜在用法!

7-11. 答案

[This is a hidden slide]

8. 简单应用

将图形信息存储到图形数据结构后,我们可以回答几个简单的问题。

  1. 计数 V,
  2. 计数 E,
  3. 枚举顶点u的邻居,
  4. 检查边缘(u,v)的存在等。

8-1. 将V计数

在AM和AL中,V只是数据结构的行数,可以在O(V中或甚至在O(1中获得 - 取决于实际实现。
讨论:如果图存储在EL中,如何计算V
PS:有时这个数字是存储/维护在一个单独的变量中,这样我们就不必每次都重新计算它 - 特别是如果图形在创建之后永远/很少改变,因此我们有O(1)性能,例如:对于上面显示的示例图,我们可以存储(在我们的AM / AL / EL数据结构中)有7个顶点。

8-2. 答案

[This is a hidden slide]

8-3. 将 E 计数

在边表(EL)中,E只是行数,可以用O(E)计数。请注意,根据需要,我们可以在EL中存储一次双向边,但在其他情况下,我们将两个有向边存储在EL内。
在邻接表(AL)中,可以通过将所有V列表的长度相加来找到 E,并将最终答案除以2(对于无向图)。这需要O(V+E计算时间,因为每个顶点和每个边缘仅被处理一次。
讨论:如果图表存储在邻接矩阵(AM)中,如何计算E
PS:为了提高效率,有时将这个数字存储/维护在一个单独的变量中,例如:对于上面显示的示例图,我们可以记住(在我们的AM / AL / EL数据结构中)有8个无向边。

8-4. 答案

[This is a hidden slide]

8-5. 枚举顶点的邻居u

在AM中,如果AM [u],我们需要遍历AM [u] [j]∀j∈[0..V-1]的所有列并报告(j,AM [u] [j])是否[j]是零。这是 O(V) - 慢。
在AL中,我们只需要遍历AL [u]。如果顶点u只有k个邻居,那么我们只需要O(k来枚举它们 - 这被称为输出敏感时间复杂度,已经是最好的了。
我们通常按顶点数量递增的方式列出邻居。例如,上面的示例图中的顶点1的邻居是{0,2,3},按增加的顶点数顺序。
讨论:如果图形存储在EL中,如何执行此操作?

8-6. 答案

[This is a hidden slide]

8-7. 检查边缘(u,v)的存在

在AM中,我们可以简单地检查AM [u] [v]是否为非零。这是O(1) - 最快的。
在AL中,我们必须检查AL [u]是否包含顶点v。这是O(k) - 更慢。
例如,上面的示例图中存在边(2,4),但边不存在边(2,6)。
请注意,如果我们找到了edge(u,v),我们也可以访问和/或更新其权重。
讨论:如果图形存储在EL中,如何执行此操作?

8-8. 答案

[This is a hidden slide]

8-9. 讨论

Quiz: So, what is the best graph data structure?

Adjacency List
It Depends
Adjacency Matrix
Edge List

讨论: 为什么?

8-10. 答案

[This is a hidden slide]

9. 附加功能

你已经完成了这个相对简单的图形数据结构的基本内容,我们鼓励你在探索模式中通过绘制你自己的图形进一步探索。
然而,我们仍然有一些更有趣的图形数据结构的挑战,在本节中概述。
请注意,图形数据结构通常只是解决较难的图形问题(如MST, SSSP, MF, Matching, MVC, ST, or TSP)的必要部分,而不是充分部分。

9-1. 在线测验

有关此数据结构的一些有趣问题,请练习Graph Data Structures培训模块(无需登录)。

9-2. 实现细节

请查看 C++/Python/Java/OCaml 对于此课中讲到的这三种图结构的实现:邻接矩阵(Adjacency Matrix),邻接表(Adjacency List),边表(Edge List):graph_ds.cpp | py | java | ml.

9-3. 在线测评练习

尝试解决两个基本的编程问题,这些问题需要使用图形数据结构,而不需要任何花哨的图形算法:

  1. UVa 10895 - Matrix Transpose and,
  2. Kattis - flyingsafely.

9-4. 讨论

[This is a hidden slide]