图
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个边(连接/关系)。也许我们可以提出这样的问题:谁是0号的朋友? 谁拥有最多的朋友? 有没有孤立的人(那些没有朋友的人)? 两个陌生人之间是否有共同的朋友:3号人和5号人? 等等...
2-2. 示例 - 更容易看到,2
运输网络:顶点可以表示站点,边缘表示站点之间的连接(通常是加权的)。 例如,请参阅当前显示的有向加权图。该图显示了5个顶点(站点/位置)和6个边缘(站点之间的连接/道路,具有正的权重行进时间,如图所示)。假设我们正在开车。我们或许可以问一下从0号站到4号站的路径是什么,以便我们用最少的时间到达4号站? 讨论:想想其他一些可以建模为图形的现实生活场景。
2-3. 示例 - 更难看到
[This is a hidden slide]
3. 模式
要在图形绘制模式之间切换,请选择相应的标题。 我们有:
U/U = 无向/不加权, U/W = 无向/加权, D/U = 有向/不加权, and D/W = 有向/加权. 我们根据所选模式限制您可以绘制的图形类型。
4. 可视化
您可以单击任何一个示例图形并可视化上图。
您还可以直接在可视化区域中绘制图形:
点击空白区域添加顶点, 单击顶点,按住,将绘制的边缘拖动到另一个顶点,然后将其放在那里以添加边缘(PS:此操作不适用于移动用户;您需要鼠标), 选择顶点/边缘并按“删除”键删除该顶点/边, 选择边缘并按“Enter”以更改该边缘的权重[0..99], 按住“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部分
在有根树中,我们有层次结构(父,子,祖先,后代),子树,级别和高度的概念。我们将通过示例说明这些概念,因为它们的含义与现实生活中的对应物一样:0/1/7/9/4的父级分别为none / 0 / 1 / 8 / 3, 0/1/7的子女分别为{1,8} / {2,3,6,7} / none, 4/8的祖先分别为{3,1,0} / {0}, 1/8的后代分别是{2,3,4,5,6,7} / {9}, 以1为根的子树包括1,其后代和所有相关边, 0/1/2/3级成员分别为{0} / {1,8} / {2,3,6,7,9} / {4,5}, 这个有根树的高度是它的最高级别= 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
有向无环图(DAG) 是一种无循环的有向图,与动态规划(DP) 技术非常相关。 每个DAG至少有一个拓扑排序/顺序 ,可通过对DFS / BFS图形遍历算法的简单调整找到。 我们会在DAG中使用DP技术寻找单源最短路径 中再次回顾DAG。 我们目前显示我们的D / W:四个0→4路径示例。您可以进入“探索模式”并绘制自己的DAG。
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. 简单应用
将图形信息存储到图形数据结构后,我们可以回答几个 简单的问题。
计数 V , 计数 E , 枚举顶点u 的邻居, 检查边缘(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?
Submit 讨论: 为什么?
8-10. 答案
[This is a hidden slide]
9. 附加功能
你已经完成了这个相对简单的图形数据结构的基本内容,我们鼓励你在探索模式中通过绘制你自己的图形进一步探索。 然而,我们仍然有一些更有趣的图形数据结构的挑战,在本节中概述。 请注意,图形数据结构通常只是解决较难的图形问题(如MST , SSSP , MF , Matching , MVC , ST , or TSP )的必要部分,而不是充分部分。