图

• 1: 定义和操作
• 2: 算法和应用

# 图

## 图的基本概念

## 图的存储结构及基本操作

- 邻接矩阵
- 邻接表
- 邻接多重表、十字链表

## 图的遍历

- 深度优先搜索
- 广度优先搜索

## 图的基本应用

- 最小生成树
- 最短路径
- 拓扑排序
- 关键路径

1 - 定义和操作

图的定义

图是由顶点和边组成的非线性数据结构。顶点有时也被称为节点，而边是连接图中任意两个节点的线或弧。更正式地说，图是由一组顶点(V)和一组边(E)组成的。图用G(E, V)表示。

• 有向图（directed graph）：边是有方向的，从一个定点指向另一个定点
• 无向图（undirected graph）：边是没有方向的

• 连通图（Connected Graph）：图中的每一对不同顶点都可以通过一条或多条边相互连接，也就是说，从图中的任意一个顶点出发，都可以到达图中的任意其他顶点。
• 非连通图（Disconnected Graph）：图中存在两个或多个互不相连的子图，也就是说，其中至少存在一个顶点集合，无法通过边连接到图中的其他顶点集合。
• 完全图（Complete Graph）：完全图是一种特殊的图，其中每一对不同的顶点都直接相连，也就是说，完全图中的任意两个顶点之间都存在一条边。如果一个完全图有n个顶点，那么它将有 $C(n, 2) = n(n-1)/2$ 条边，其中 $C(n, 2)$ 表示从n个顶点中选择2个顶点的组合数。

• 连通分量（Connected Components）：连通分量（Connected Components），也称为连通子图，是一个无向图中的一个重要概念。一个连通分量是指在无向图中，如果从其中一个顶点出发，可以通过边的路径到达该连通分量内的任何其他顶点，而无法通过图中的边到达其他连通分量内的顶点。
• 顶点的度（Degree）：顶点的度是指与该顶点相邻的边的数量，也就是与该顶点直接相连的其他顶点的个数。对于有向图和无向图都适用。
  • 在无向图中，顶点的度就是与该顶点相邻的边的数量。
  • 在有向图中，顶点的度分为入度和出度，分别表示指向该顶点的边的数量和从该顶点出发的边的数量的总和。
• 入度（In-Degree）：入度是指在有向图中指向某个顶点的边的数量，也就是与该顶点关联的边中以该顶点为终点的边的数量。
• 出度（Out-Degree）：出度是指在有向图中从某个顶点出发的边的数量，也就是与该顶点关联的边中以该顶点为起点的边的数量。

邻接矩阵

定义

图的邻接矩阵（Adjacency Matrix）是一种常用的图表示方法，特别适用于稠密图，它以矩阵的形式表示图的连接关系。

在邻接矩阵中，行和列分别代表图的顶点，矩阵的元素表示顶点之间是否相邻或者边的权重。

1. 对于无向图：
   • 如果顶点 $i$ 和顶点 $j$ 之间存在边，则邻接矩阵中 $(i, j)$ 和 $(j, i)$ 位置的元素都被标记为 $1$ （或者表示边的权重）。
   • 如果顶点 $i$ 和顶点 $j$ 之间不存在边，则邻接矩阵中 $(i, j)$ 和 $(j, i)$ 位置的元素都被标记为 $0$ 。
2. 对于有向图：
   • 如果有一条从顶点 $i$ 到顶点 $j$ 的有向边，则邻接矩阵中 $(i, j)$ 位置的元素被标记为 $1$ （或者表示边的权重）。
   • 如果没有从顶点 $i$ 到顶点 $j$ 的有向边，则邻接矩阵中 $(i, j)$ 位置的元素被标记为 $0$ 。

实现

我们可以用一个二维数组来表示邻接矩阵，邻接矩阵的行数和列数与图中的顶点数量相同。

• 邻接矩阵定义
• 添加边

#define MAX_VERTICES 100

int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵

// 初始化邻接矩阵
void initializeMatrix(int vertices) {
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            adjMatrix[i][j] = 0; // 初始化所有元素为0
        }
    }
}

// 在邻接矩阵中添加一条边
void addEdge(int start, int end) {
    adjMatrix[start][end] = 1; // 添加边，将对应位置的元素设为1
    adjMatrix[end][start] = 1; // 无向图需要将对称位置的元素也设为1
}

入度出度

如果需要计算邻接矩阵中某个顶点的 出度 的话，假设顶点编号为 i，我们统计邻接矩阵中的 第 i 行 有多少元素不为 0 即可（该顶点指向哪些顶点）。

如果需要计算邻接矩阵中某个顶点的 出度 的话，假设顶点编号为 i，我们统计邻接矩阵中的 第 i 列 有多少元素不为 0 即可（哪些顶点指向该顶点）。

邻接表

定义

图的邻接表（Adjacency List）是一种常见的图表示方法，特别适用于稀疏图，它使用链表或数组的形式来表示图的连接关系。每个顶点都对应一个链表，链表中存储与该顶点相邻的其他顶点。

邻接表的主要思想是为每个顶点创建一个链表，链表中的每个节点表示与该顶点相邻的另一个顶点。对于无向图，通常需要为每一条边创建两个链表节点，分别表示两个相邻的顶点。

实现

// 邻接表节点结构
struct Node {
    int data;
    struct Node* next;
};

// 图的结构
struct Graph {
    int vertices;
    struct Node** adjacencyList;
};

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 创建图
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->vertices = vertices;
    graph->adjacencyList = (struct Node**)malloc(vertices * sizeof(struct Node*));
    for (int i = 0; i < vertices; i++) {
        graph->adjacencyList[i] = NULL;
    }
    return graph;
}

// 添加边
void addEdge(struct Graph* graph, int start, int end) {
    // 添加边到起始顶点的链表
    struct Node* newNode = createNode(end);
    newNode->next = graph->adjacencyList[start];
    graph->adjacencyList[start] = newNode;

    // 对于无向图，需要添加一条反向边
    newNode = createNode(start);
    newNode->next = graph->adjacencyList[end];
    graph->adjacencyList[end] = newNode;
}

邻接多重表

邻接多重表（Adjacency Multi-list）是一种用于表示无向图的数据结构，主要用于避免在邻接表存储方式中重复存储无向边，提高存储效率，同时便于图的操作（如边的删除）。

邻接多重表中顶点种类分为两种：

• 顶点结点（Vertex Node）：
  • 每个顶点有一个头结点，存储该顶点的信息，以及指向其所有关联边的指针。
• 边结点（Edge Node）：
  • 每条边有一个结点，存储该边的两个顶点及其相关信息。
  • 该结点包含两个指针，分别指向该边所连接的两个顶点的邻接边链表的下一条边，使得图的存储更加紧凑。

还是举个实际例子说明，在上述的邻接多重表中，总共需要存储 5 条边，每条边只需要存储一次，所以总共有 5 个边结点，每个边结点中存储的数据如下表所示：

总结一下，相比于邻接表，邻接多重表最大的不同在于如下两点：

• 节省存储空间：对于无向图，每条边只存储一次。
• 方便进行边的操作：例如，删除一条边时，只需要修改相关顶点的链表中的指针，而不需要像邻接表那样在两个顶点的邻接表中都进行操作。

2 - 算法和应用

DFS

深度优先搜索（Depth-First Search，简称 DFS）是一种用于图的遍历和搜索的算法，它从图中的一个起始顶点开始，尽可能深地访问顶点，直到无法继续前进，然后回溯到之前的顶点，继续深入其他分支。DFS 通常用递归或栈来实现，确保在深度方向上优先遍历。

以下是 DFS 算法的一般步骤：

1. 从起始顶点开始，将其标记为已访问。
2. 遍历与当前顶点相邻的未访问顶点，选择其中一个未访问顶点作为下一个深度遍历的目标，然后递归地进行 DFS。
3. 如果无法继续深度遍历（即当前顶点没有未访问的邻居），则回溯到上一个顶点，继续遍历其他未访问的邻居。
4. 重复步骤 2 和步骤 3，直到所有顶点都被访问。

邻接矩阵

在邻接矩阵中，我们定义一个递归函数 dfs，函数从 start 顶点出发， 输出当前结点，然后递归地去访问所有与其相邻的顶点。

注意递归前需要保证下一个顶点未被访问过，这样可以避免重复访问结点以及死循环。

// 全局变量，标记顶点是否被访问过
int visited[MAX_VERTICES];

// 递归函数，从 start 顶点出发
void dfs(int start) {
    visited[start] = 1;
    printf("%d ", start);

    // 依次访问 start 的邻接顶点
    for (int i = 0; i < MAX_VERTICES; i++) {
        // 递归的两个条件：
        // 1. 顶点 (start, i) 之间存在边
        // 2. 顶点 i 未被访问过
        if (adjMatrix[start][i] == 1 && !visited[i]) {
            // 递归调用
            dfs(i);
        }
    }
}

邻接表

邻接表的递归思路与邻接矩阵一致， 唯一的区别就是访问邻接顶点方式的不同。

在邻接矩阵中，通过遍历矩阵中的一行来访问相邻顶点。 在邻接表中，通过遍历链表来访问相邻顶点。

// 全局变量，标记顶点是否被访问过
int visited[MAX_VERTICES];

// 递归函数，从 start 顶点出发
void dfs(struct Graph* graph, int start) {
    visited[start] = 1;
    printf("%d ", start);

    // 依次访问 start 的邻接顶点
    struct Node* temp = graph->adjacencyList[start];
    while (temp) {
        int adjVertex = temp->data;
        // 递归条件：顶点 i 未被访问过
        if (!visited[adjVertex]) {
            dfs(graph, adjVertex);
        }
        temp = temp->next;
    }
}

BFS

广度优先搜索（Breadth-First Search，简称 BFS）是一种用于图的遍历和搜索的算法，它从图中的一个起始顶点开始，逐层地访问与该顶点相邻的顶点，然后再访问这些相邻顶点的邻居，以此类推。BFS 通常用队列来实现，确保按照广度优先的顺序访问顶点。

以下是 BFS 算法的一般步骤：

1. 将起始顶点放入队列中，标记为已访问。
2. 从队列中弹出一个顶点并访问它。
3. 遍历该顶点的所有未被访问的邻居，将它们放入队列中，并标记为已访问。
4. 重复步骤 2 和步骤 3，直到队列为空。

邻接矩阵

实现 bfs 时，首先添加起始顶点进入队列中，然后不断从队列中取出顶点，并添加该顶点的未访问相邻顶点进入队列。 重复直到队列为空。

在 dfs 中，visited 数组是各个递归函数都需要访问的数据结构，为了方便起见，可以定义为全局变量。 在 bfs 中，由于算法实现是基于迭代而非递归，所以 visited 和 队列 可以定义为局部变量。

// 从 start 开始遍历图
void bfs(int start, int vertices) {
    // 队列 q
    queue q;
    // 标记顶点是否被访问过
    int visited[MAX_VERTICES];
    // 添加初始顶点
    q.enqueue(start);
    visited[start] = 1;

    // 一直遍历到队列为空
    while (q.size() > 0) {
        // 从队列头部取出结点作为当前结点
        int currentVertex = q.dequeue();
        // 输出当前结点
        printf("%d ", currentVertex);
        // 将当前结点的所有 相邻的未访问顶点 添加到队列中
        for (int i = 0; i < vertices; i++) {
            if (adjMatrix[currentVertex][i] == 1 && !visited[i]) {
                q.enqueue(i);
                visited[i] = 1;
            }
        }
    }
}

邻接表

实现思路与邻接矩阵方式一致，不同点在与访问相邻顶点的方式不同。

void bfs(struct Graph* graph, int start) {
    // 队列 q
    queue q;
    // 标记顶点是否被访问过
    int visited[MAX_VERTICES];
    // 添加初始顶点
    q.enqueue(start);
    visited[start] = 1;

    // 一直遍历到队列为空
    while (front != rear) {
        // 从队列头部取出结点作为当前结点
        int currentVertex = q.dequeue();
        // 输出当前结点
        printf("%d ", currentVertex);
        // 将当前结点的所有 相邻的未访问顶点 添加到队列中
        struct Node* temp = graph->adjacencyList[currentVertex];
        while (temp) {
            int adjVertex = temp->data;
            if (!visited[adjVertex]) {
                q.enqueue(adjVertex);
                visited[adjVertex] = 1;
            }
            temp = temp->next;
        }
    }
}

最小生成树

最小生成树（Minimum Spanning Tree，MST）是在一个连接所有顶点的无向图中，通过选择一部分边而形成的树，使得树的总权重（或成本）最小。

准确的最小生成树定义如下：在无向图 $G = (V, E)$ 中，$(u, v)$ 代表连接顶点 $u$ 和顶点 $v$ 的边，而 $w(u, v)$ 代表此边的权重，若存在 $T$ 为 $E$ 的子集且 $(V, E)$ 为树，使得 $w(T) = \sum_{(u, v) \in T} w(u, v)$ 最小，则此 $T$ 为 $G$ 的最小生成树。

最小生成树满足以下特点：

• 包含图中的所有顶点。
• 通过选择一些边而形成一个树结构，没有环路。
• 边的总权重最小。

prim 算法

Prim 算法的主要思想是从一个初始顶点开始，逐步扩展生成树，每次选择与当前生成树相邻且权重最小的边所连接的顶点，并将该顶点加入生成树。算法的运行过程可以概括为以下步骤：

1. 选择一个起始顶点作为生成树的根节点。
2. 初始化一个空的生成树，包含初始顶点。
3. 将与生成树中的顶点相邻且权重最小的边的另一端顶点加入生成树，即选择一条最小权重边。
4. 重复步骤 3，直到生成树包含了所有的顶点。
5. 最终生成树即为原图的最小生成树。