数据结构与算法（7）

小鹤2024-11-192024-11-19

图的定义

图(Graph)是由顶点的有穷非空集合 ( V(G) ) 和顶点之间边的集合 ( E(G) ) 组成，通常表示为: ( G = (V, E) )，其中，( G ) 表示一个图，( V ) 是图 ( G ) 中顶点的集合，( E ) 是图 ( G ) 中边的集合。若 ( V = {v_1, v_2, …, v_n} )，则用 ( |V| ) 表示图 ( G ) 中顶点的个数，也称图 ( G ) 的阶，( E = {(u, v) | u \in V, v \in V} )，用 ( |E| ) 表示图 ( G ) 中边的条数。

图的基本概念

1. 有向图

有向图的表示

【】

图(a)所示的有向图 ( G_1 ) 可表示为 [ G_1 = (V_1, E_1) ] 其中， [ V_1 = {1, 2, 3} ] [ E_1 = {<1, 2>, <2, 1>, <2, 3>} ]

2、无向图若E是无向边(简称边)的有限集合时，则图G为无向图。边是顶点的无序对，记为(v, w)或(w,v),因为(v,w)=(w,v), 其中v,w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w)依附于顶点w和v，或者说边(v, w)和顶点v, w相关联。【】

无向图的表示

图(b)所示的无向图 ( G_2 ) 可表示为 [ G_2 = (V_2, E_2) ] 其中， [ V_2 = {1, 2, 3, 4} ] [ E_2 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)} ]

简单图

一个图 ( G ) 若满足以下条件：

不存在重复边；
不存在顶点到自身的边，

则称图 ( G ) 为简单图。上图中的 ( G_1 ) 和 ( G_2 ) 均为简单图。数据结构中仅讨论简单图。

多重图

若图 ( G ) 中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则 ( G ) 为多重图。多重图的定义和简单图是相对的。

完全图（也称简单完全图）

对于无向图，( |E| ) 的取值范围是 0 到 ( \frac{n(n-1)}{2} )。有 ( \frac{n(n-1)}{2} ) 条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。
对于有向图，( |E| ) 的取值范围是 0 到 ( n(n-1) )。有 ( n(n-1) ) 条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。

上图中的 ( G_2 ) 为无向完全图，而 ( G_3 ) 为有向完全图。

子图

设有两个图 ( G = (V, E) ) 和 ( G’ = (V’, E’) )，若 ( V’ ) 是 ( V ) 的子集，且 ( E’ ) 是 ( E ) 的子集，则称 ( G’ ) 是 ( G ) 的子图。若有满足 ( V(G’) = V(G) ) 的子图 ( G’ )，则称其为 ( G ) 的生成子图。上图中的 ( G_3 ) 为 ( G_1 ) 的子图。

注意: 并非 ( V ) 和 ( E ) 的任何子集都能构成 ( G ) 的子图，因为这样的子集可能不是图，即 ( E ) 的子集中的某些边关联的顶点可能不在这个 ( V ) 的子集中。

连通、连通图和连通分量

在无向图中，若从顶点 ( v ) 到顶点 ( w ) 有路径存在，则称 ( v ) 和 ( w ) 是连通的。若图 ( G ) 中任意两个顶点都是连通的，则称图 ( G ) 为连通图，否则称为非连通图。无向图中的极大连通子图称为连通分量。若一个图有 ( n ) 个顶点，并且边数小于 ( n - 1 )，则此图必是非连通图。如下图(a)所示，图 ( G_4 ) 有3个连通分量，如图（b）所示。

注意: 弄清连通、连通图、连通分量的概念非常重要。首先要区分极大连通子图和极小连通子图，极大连通子图是无向图的连通分量，极大即要求该连通子图包含其所有的边；极小连通子图是既要保持图连通又要使得边数最少的子图。

强连通图、强连通分量

在有向图中，若从顶点 ( v ) 到顶点 ( w ) 和从顶点 ( w ) 到顶点 ( v ) 之间都有路径，则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量，图 ( G_1 ) 的强连通分量如下图所示。

注意: 强连通图、强连通分量只是针对有向图而言的。一般在无向图中讨论连通性，在有向图中考虑强连通性。

生成树、生成森林

连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 ( n )，则它的生成树含有 ( n - 1 ) 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。图 ( G_2 ) 的一个生成树如下图所示。

注意: 包含无向图中全部顶点的极小连通子图，只有生成树满足条件，因为砍去生成树的任一条边，图将不再连通。

顶点的度、入度和出度

图中每个顶点的度定义为以该顶点为一个端点的边的数目。

对于无向图，顶点 ( v ) 的度是指依附于该顶点的边的条数，记为 ( TD(v) )。
在具有 ( n ) 个顶点、( e ) 条边的无向图中，(\sum_^{n} TD(v_i) = 2e)，即无向图的全部顶点的度的和等于边数的2倍，因为每条边和两个顶点相关联。
对于有向图，顶点 ( v ) 的度分为入度和出度，入度是以顶点 ( v ) 为终点的有向边的数目，记为 ( ID(v) )；而出度是以顶点 ( v ) 为起点的有向边的数目，记为 ( OD(v) )。顶点 ( v ) 的度等于其入度和出度之和，即 ( TD(v) = ID(v) + OD(v) )。
在具有 ( n ) 个顶点、( e ) 条边的有向图中，(\sum_^{{n} ID(v_i) = \sum_}{n} OD(v_i) = e)，即有向图的全部顶点的入度之和与出度之和相等，并且等于边数。这是因为每条有向边都有一个起点和终点。

边的权和网

在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。

稠密图、稀疏图

边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图 ( G ) 满足 ( |E| < |V| \log |V| ) 时，可以将 ( G ) 视为稀疏图。

路径、路径长度和回路

顶点 ( v_p ) 到顶点 ( v_q ) 之间的一条路径是指顶点序列 ( v_p, v_{i_1}, v_{i_2}, …, v_{i_m}, v_q )，当然关联的边也可以理解为路径的构成要素。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有 ( n ) 个顶点，并且有大于 ( n - 1 ) 条边，则此图一定有环。

简单路径、简单回路

在路径序列中，顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

距离

从顶点 ( u ) 出发到顶点 ( v ) 的最短路径若存在，则此路径的长度称为从 ( u ) 到 ( v ) 的距离。若从 ( u ) 到 ( v ) 根本不存在路径，则记该距离为无穷 ( (\infty) )。

有向树

一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树。

1. 图的存储结构

图的存储结构

邻接矩阵
- 定义：使用一个二维数组来表示图中节点之间的连接关系。
- 特点：适合稠密图，即边数接近于节点数的平方。
- 实现：
  1
  2
  3
  4
  5
  6
  const adjacencyMatrix = [
  [0, 1, 0, 1],
  [1, 0, 1, 0],
  [0, 1, 0, 1],
  [1, 0, 1, 0]
  ];
- 优缺点：
  - 优点：实现简单，判断两点是否相连的时间复杂度为 O(1)。
  - 缺点：空间复杂度高，不适合稀疏图。
邻接表
- 定义：使用链表或数组加指针的方式存储每个节点的邻居节点。
- 特点：适合稀疏图，即边数远小于节点数的平方。
- 实现：
  1
  2
  3
  4
  5
  6
  const adjacencyList = {
  0: [1, 3],
  1: [0, 2],
  2: [1, 3],
  3: [0, 2]
  };
- 优缺点：
  - 优点：空间复杂度低，适合稀疏图。
  - 缺点：判断两点是否相连的时间复杂度为 O(d)，d 是节点的度。
边集数组
- 定义：使用一个数组来存储图中的所有边。
- 特点：适用于边数较少的情况。
- 实现：
  1
  2
  3
  4
  5
  6
  const edgeList = [
  [0, 1],
  [1, 2],
  [2, 3],
  [3, 0]
  ];
- 优缺点：
  - 优点：实现简单，适合边数较少的图。
  - 缺点：查找节点的邻居节点效率较低。

总结

邻接矩阵适合稠密图，实现简单，但空间复杂度高。
邻接表适合稀疏图，空间复杂度低，但查找邻居节点的时间复杂度较高。
边集数组适用于边数较少的图，实现简单，但查找节点的邻居节点效率较低。

图的遍历算法

1. 深度优先搜索 (DFS)

基本思想：从某个节点开始，沿着某条路径一直搜索下去，直到无法继续为止，然后回溯到上一个节点，继续搜索其他路径。
应用场景：检测图的连通性、寻找路径、拓扑排序等。

C 语言实现

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

int visited[MAX_VERTICES];
int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];

void dfs(int v, int n) {
    visited[v] = 1;
    printf("Visited vertex %d\n", v);

    for (int i = 0; i < n; i++) {
        if (adjacencyMatrix[v][i] == 1 && !visited[i]) {
            dfs(i, n);
        }
    }
}

int main() {
    int n = 5; // 假设有 5 个顶点
    int edges[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 4}};
    int numEdges = sizeof(edges) / sizeof(edges[0]);

    // 初始化邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            adjacencyMatrix[i][j] = 0;
        }
    }

    // 添加边
    for (int i = 0; i < numEdges; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        adjacencyMatrix[u][v] = 1;
        adjacencyMatrix[v][u] = 1; // 如果是有向图，去掉这一行
    }

    // 初始化访问数组
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
    }

    // 从顶点 0 开始进行 DFS
    dfs(0, n);

    return 0;
}

2. 广度优先搜索 (BFS)

基本思想：从某个节点开始，先访问其所有邻居节点，再依次访问这些邻居节点的邻居，逐层扩展。
应用场景：最短路径问题、图的连通性检测等。

C 语言实现

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

int visited[MAX_VERTICES];
int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];

void bfs(int start, int n) {
    int queue[MAX_VERTICES];
    int front = 0, rear = 0;

    visited[start] = 1;
    queue[rear++] = start;

    while (front != rear) {
        int v = queue[front++];
        printf("Visited vertex %d\n", v);

        for (int i = 0; i < n; i++) {
            if (adjacencyMatrix[v][i] == 1 && !visited[i]) {
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

int main() {
    int n = 5; // 假设有 5 个顶点
    int edges[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 4}};
    int numEdges = sizeof(edges) / sizeof(edges[0]);

    // 初始化邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            adjacencyMatrix[i][j] = 0;
        }
    }

    // 添加边
    for (int i = 0; i < numEdges; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        adjacencyMatrix[u][v] = 1;
        adjacencyMatrix[v][u] = 1; // 如果是有向图，去掉这一行
    }

    // 初始化访问数组
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
    }

    // 从顶点 0 开始进行 BFS
    bfs(0, n);

    return 0;
}

总结

深度优先搜索 (DFS)：适用于检测图的连通性、寻找路径、拓扑排序等。
广度优先搜索 (BFS)：适用于最短路径问题、图的连通性检测等。

希望这些介绍和代码示例对您有所帮助！如果有更多具体问题或需要进一步的解释，请随时提问。

3. 图的连通分量

无向图的连通分量：图中的一组顶点，其中任意两个顶点之间都存在路径。
有向图的强连通分量：图中的一组顶点，其中任意两个顶点之间都存在双向路径。

4. 图的深度优先搜索

基本思想：从某个节点开始，沿着某条路径一直搜索下去，直到无法继续为止，然后回溯到上一个节点，继续搜索其他路径。
应用：检测图的连通性、寻找路径、拓扑排序等。

5. 图的广度优先搜索

基本思想：从某个节点开始，先访问其所有邻居节点，再依次访问这些邻居节点的邻居，逐层扩展。
应用：最短路径问题、图的连通性检测等。

6. 图的拓扑排序

定义：对于一个有向无环图 (DAG)，将图中的所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v，若边 (u, v) 存在，则 u 在线性序列中出现在 v 的前面。
算法：Kahn 算法和基于 DFS 的算法。

7. 最小生成树

定义：对于一个带权的无向图，生成树是指包含图中所有顶点的一个无环子图。最小生成树是指生成树中所有边的权重之和最小的生成树。
算法：Prim 算法和 Kruskal 算法。

8. 最短路径问题

单源最短路径：从某个起点出发，找到到其他所有顶点的最短路径。常用算法有 Dijkstra 算法和 Bellman-Ford 算法。
所有顶点对的最短路径：求解图中任意两个顶点之间的最短路径。常用算法有 Floyd-Warshall 算法。

9. 欧拉回路

定义：欧拉回路是指通过图中每条边恰好一次且仅一次，并能回到出发点的路径。
条件：对于无向图，每个顶点的度数必须为偶数；对于有向图，每个顶点的入度和出度必须相等。

希望这些扩写内容对您有所帮助！如果您有更多具体问题或需要进一步的解释，请随时提问。