图

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}，使得在vi和vi+1∀i∈[0..n-1]之间存在边缘。
如果路径上没有重复的顶点，我们称这样的路径为简单路径。
例如，{0,1,2,4,5}是当前显示的图形中的一个简单路径。

1-4. 术语，第3部分

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

如果要把无向图C称为无向图G的连通分量，它必须符合以下的条件。 1）C是G的子图; 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个顶点的无向图，其可以被划分为大小为m和n的两个不相交的顶点集，其中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]