数据结构--图

图的定义和基本术语

图的基本概念

图（Graph）是由顶点（或称为节点）和连接这些顶点的边所组成的数学结构。它是离散数学中的一个核心概念，也是计算机科学中用于表示对象之间关系的重要数据结构。

有向图（Directed Graph）

有向图是一种特殊的图，其中每条边都有一个明确的方向。在有向图中，边通常表示为箭头，指示从一个顶点指向另一个顶点。这意味着，如果图中存在一条从顶点A到顶点B的边，那么可以说从A到B有一个有向的连接，但并不意味着从B到A也有连接。有向图常用于表示具有方向性的关系，如流程、依赖关系、网络中的数据传输等。

无向图（Undirected Graph）

与有向图相反，无向图中的边没有方向。在无向图中，边只是简单地连接两个顶点，而不指示任何特定的方向。因此，如果图中存在一条连接顶点A和顶点B的边，那么可以说A和B是相邻的，且这条边可以被看作是从A到B和从B到A都是可行的（尽管实际上并没有明确的“从...到...”的概念，因为边是无向的）。无向图常用于表示对称关系，如朋友关系、邻居关系等。

总结

• 有向图：边有方向的图，通常表示为箭头，指示从一个顶点指向另一个顶点。
• 无向图：边没有方向的图，边只是简单地连接两个顶点，不指示任何特定的方向。

图的基本术语

1. 顶点（Vertex）：图中的基本元素，通常表示为节点。在图中，顶点可以代表任何事物，比如人、地点、概念等。

2. 边（Edge）：连接两个顶点的线或路径。在无向图中，边没有方向；在有向图中，边有方向，通常表示为箭头。

3. 无向图（Undirected Graph）：边没有方向的图。如果顶点A和顶点B之间有一条边，那么A和B是相邻的，且这条边可以被看作是从A到B和从B到A都是可行的。

4. 有向图（Directed Graph）：边有方向的图。边从起点指向终点，表示一种单向的关系。

5. 加权图（Weighted Graph）：每条边都有一个权重（或称为成本）的图。权重可以表示距离、时间、费用等，具体取决于图的应用场景。

6. 邻接（Adjacency）：如果两个顶点之间有边相连，则称这两个顶点是邻接的。

7. 度（Degree）：

   • 在无向图中，一个顶点的度是与该顶点相连的边的数量。
   • 在有向图中，一个顶点的出度是从该顶点出发的边的数量，入度是进入该顶点的边的数量。

8. 路径（Path）：顶点序列，其中每对相邻顶点之间都有边相连。路径可以是有向的（在有向图中）或无向的（在无向图中）。

9. 环（Cycle）：起点和终点相同的路径。在简单环中，除了起点和终点外，路径中的其他顶点都不重复。

10. 连通性（Connectivity）：

    • 在无向图中，如果图中任意两个顶点之间都存在路径，则称该图是连通的。
    • 在有向图中，如果对于任意顶点u和v，都存在从u到v的路径（或反之），则称该图是有向连通的。

11. 连通分量（Connected Component）：图的最大连通子图。在无向图中，连通分量是使得子图内任意两顶点连通、且子图外不存在与该子图内顶点连通的最大顶点集合。

12. 强连通分量（Strongly Connected Component, SCC）：在有向图中，最大的强连通子图。强连通子图是指子图中任意两个顶点之间都存在双向路径。

13. 图的表示：

    • 邻接矩阵：使用二维数组表示图，元素值表示顶点之间是否存在边（以及边的权重，如果图是有权重的）。
    • 邻接表：使用链表或数组列表表示每个顶点及其相邻顶点。

14. 图的遍历：

    • 深度优先搜索（DFS）：尽可能深地搜索图的分支。
    • 广度优先搜索（BFS）：按层次逐层搜索图的节点。

图的存储结构

邻接矩阵（Adjacency Matrix）

邻接矩阵是一种方阵，其中行和列都代表图中的顶点。矩阵中的元素表示顶点之间是否存在边以及边的权重（如果图是有权重的）。

• 无向图：如果顶点i和顶点j之间存在一条边，则矩阵元素[i][j]和[j][i]都为1（或表示边的权重的值）。对于无权图，通常用0表示不存在边，用1表示存在边。

• 有向图：如果顶点i到顶点j有一条有向边，则矩阵元素[i][j]为1（或边的权重），而[j][i]为0（或无定义，取决于具体实现）。

优点：

• 易于实现和查询任意两个顶点之间是否有边（以及边的权重）。
• 矩阵运算可以方便地用于实现图的某些算法。

缺点：

• 空间复杂度为O(V^2)，其中V是顶点的数量。对于稠密图（边较多的图），这种表示方法是有效的，但对于稀疏图（边较少的图），会浪费大量空间。

邻接表（Adjacency List）

邻接表是一种链表数组，其中每个元素是一个链表，链表中的节点表示与该顶点相邻的顶点。

• 顶点表：通常用一个数组来存储图的顶点，每个顶点有一个对应的链表。
• 链表：链表中的每个节点表示一个与当前顶点相邻的顶点，通常包含邻接顶点的信息（如索引或值）和指向下一个节点的指针。

 

优点：

• 空间效率较高，特别适用于稀疏图。
• 易于添加和删除边。

缺点：

• 查询两个顶点之间是否有边可能需要遍历链表。
• 对于某些图算法（如矩阵运算），实现可能不如邻接矩阵方便。

十字链表（Cross Linked List）

十字链表是有向图的另一种链表表示法，它结合了邻接表和逆邻接表的概念。

• 顶点表：与邻接表类似，每个顶点有一个对应的链表。
• 链表：链表中的每个节点包含两个指针，一个指向该顶点的下一个邻接顶点（与邻接表相同），另一个指向以当前顶点为尾的弧的下一个顶点（即逆邻接顶点）。

优点：

• 易于找到以某顶点为头或为尾的弧。
• 易于求得顶点的出度和入度。

缺点：

• 实现相对复杂。
• 空间开销可能较大，特别是当图中的边较多时。

邻接多重表（Adjacency Multilist）

邻接多重表是无向图的另一种有效存储结构，它改进了邻接表的边表结构。

• 顶点表：与邻接表类似，但每个顶点对应的链表包含的是与该顶点相关联的边（而不是邻接顶点）。
• 边表：每条边在边表中有一个对应的节点，节点包含两个指向该边所连接的两个顶点的指针以及指向下一条边的指针（用于遍历所有边）。

优点：

• 易于求得顶点和边的各种信息。
• 适用于对边进行操作的场景，如遍历、删除边等。

缺点：

• 实现相对复杂。
• 空间开销可能较大，特别是当图中的边较多且顶点较少时。

边集数组（Edge Set Array）

边集数组是一种简单的表示法，它用两个数组分别存储顶点和边的信息。

• 顶点数组：存储图中所有顶点的信息。
• 边数组：存储图中所有边的信息，每条边由一对顶点（或顶点的索引）表示。

优点：

• 实现简单。
• 适用于边较少且顶点较多的图。

缺点：

• 查询两个顶点之间是否有边需要遍历边数组，效率较低。
• 不适用于对边进行频繁操作的场景。

图的遍历

1. 深度优先搜索（Depth-First Search, DFS）：
   • 尽可能深地搜索图的分支。
   • 可以使用递归或栈来实现。
   • 常用于路径查找、连通性检测等。
2. 广度优先搜索（Breadth-First Search, BFS）：
   • 按层次逐层搜索图的节点。
   • 使用队列来实现。
   • 常用于最短路径查找（在无权图中）、连通性检测等。

深度优先搜索（DFS）示例

假设有一个无向图，顶点集合为V={A, B, C, D, E, F, G, H, I}，边的集合为E={(A,B), (A,F), (B,C), (B,D), (B,F), (C,D), (D,E), (D,G), (E,H), (F,G), (G,I)}。现在从顶点A开始进行深度优先搜索。

1. 访问顶点A，并将其标记为已访问。
2. 从顶点A出发，访问其邻接点B（因为B是A的邻接点且尚未被访问），并将B标记为已访问。
3. 从顶点B出发，访问其邻接点C（因为C是B的邻接点且尚未被访问），并将C标记为已访问。
4. 从顶点C出发，访问其邻接点D（因为D是C的邻接点且尚未被访问），并将D标记为已访问。
5. 从顶点D出发，依次访问其邻接点E、G（因为E、G是D的邻接点且尚未被访问），并将E、G标记为已访问。
6. 在访问G时，发现G的邻接点F已经被访问过（在访问B时已经访问过F），因此不再访问F。接着访问G的另一个邻接点I，并将I标记为已访问。
7. 此时，从顶点I出发没有新的邻接点可以访问，因此回溯到顶点G，再回溯到顶点D，然后回溯到顶点B。
8. 从顶点B出发，访问其尚未访问的邻接点F（因为F在之前的访问中已经被访问过B的邻接点，但在访问D的邻接点时并未被访问为B的后续邻接点，此处为示例中的简化描述，实际在DFS实现中会有明确的访问记录），并将F标记为已访问（注意：在严格的DFS实现中，F在访问B时就应该被标记为已访问，此步骤仅为描述方便）。
9. 此时，图中所有顶点均已被访问完毕。

深度优先搜索的遍历顺序可能因实现方式（如递归或迭代）和邻接点的访问顺序（如先访问第一个邻接点还是最后一个邻接点）而有所不同，但上述过程展示了DFS的基本思想。

广度优先搜索（BFS）示例

仍然使用上述无向图，从顶点A开始进行广度优先搜索。

1. 访问顶点A，并将其放入队列中，同时标记为已访问。
2. 从队列中取出顶点A，访问其邻接点B和F（因为B和F是A的邻接点且尚未被访问），并将B和F放入队列中，同时标记为已访问。
3. 从队列中取出顶点B，访问其邻接点C、D（因为C和D是B的邻接点且尚未被访问），并将C和D放入队列中，同时标记为已访问。注意：此时F仍在队列中等待被访问。
4. 从队列中取出顶点F（或C，取决于队列的实现方式，如FIFO或LIFO），访问其尚未被访问的邻接点（在这个例子中，F的邻接点B已经被访问过，因此不再访问B；如果先取出C，则C的邻接点D已经被访问过，也不再访问D）。但在这个例子中，F没有新的邻接点可以访问（因为G在访问D时会被访问到）。如果先取出C，则接下来会访问C的其他邻接点（如果有的话）。然而，在这个特定的图中，我们可以继续按照队列中的顺序访问。
5. 依次从队列中取出顶点D、C（如果C之前未被取出的话）、E、G、H、I，并访问它们的邻接点（如果尚未被访问过）。在这个过程中，会发现有些邻接点已经被访问过（如B、F在访问A、B、D时已经被访问过），因此不再重复访问。
6. 最终，当队列为空时，图中所有顶点均已被访问完毕。

图的算法

最短路径算法

1. Dijkstra算法（迪杰斯特拉算法）：
   • 用于计算单源最短路径。
   • 适用于加权无向图且权重非负的情况。
2. Bellman-Ford算法（贝尔曼-福特算法）：
   • 可以处理带有负权重的图。
   • 能检测是否存在负权重环。
3. Floyd-Warshall算法（弗洛伊德-沃沙尔算法）：
   • 用于计算所有顶点对之间的最短路径。

最小生成树算法

1. Prim算法（普里姆算法）：
   • 用于在加权无向图中找到最小生成树（MST）。
2. Kruskal算法（克鲁斯卡尔算法）：
   • 也是用于找到MST的另一种方法。
   • 通过排序和并查集实现。

拓扑排序

• 拓扑排序（Topological Sorting）：
  • 用于有向无环图（DAG）的顶点排序。
  • 使得对于每一条有向边(u, v)，顶点u在顶点v之前被排序。

强连通分量

• 强连通分量（Strongly Connected Components, SCCs）：
  • 用于有向图中，找到最大的强连通子图。
  • 子图中任意两个顶点之间都有路径可达。

	邻接矩阵	邻接表
定义	使用二维数组表示图的顶点之间的连接关系	使用链表或数组表示每个顶点的邻接顶点
适用场景	稠密图（边数接近顶点数的平方）	稀疏图（边数远小于顶点数的平方）
空间复杂度	O(V^2)，V为顶点数	O(V+E)，V为顶点数，E为边数
查询效率	判断两点是否相邻：O(1)	判断两点是否相邻：O(d(v))，d(v)为顶点v的度
遍历效率	遍历顶点的邻接点：O(V)	遍历邻接点：O(d(v))
特点	直观易懂，方便进行矩阵运算	空间效率高，节省大量空间
表示形式	二维数组	链表或数组与链表结合
对称性	无向图的邻接矩阵是对称的	无向图使用邻接表时，数据可能冗余
操作复杂度	插入和删除边：通常较高	插入和删除边：较低，涉及链表操作

 

原文地址：https://blog.csdn.net/weixin_51933701/article/details/144362256

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！