这是本节的多页打印视图。点击此处打印.

图

本章在选择题中考察，也有可能作为一道概念题在大题中出现，需要熟练掌握图的存储结构（代码实现），并且要求在概念上理解图的应用，要求能够手工模拟。

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）：出度是指在有向图中从某个顶点出发的边的数量，也就是与该顶点关联的边中以该顶点为起点的边的数量。

树和图的区别？
树是受限制的图类型，只是有更多的规则。每棵树都是一个图，但不是所有的图都是树。链表、树和堆都是图的特殊情况。

表示方式

邻接矩阵（Adjacent Matrix）

图的邻接矩阵（Adjacency Matrix）是一种常用的图表示方法，特别适用于稠密图，它以矩阵的形式表示图的连接关系。在邻接矩阵中，行和列分别代表图的顶点，矩阵的元素表示顶点之间是否相邻或者边的权重。

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

邻接表

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

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

代码实现

#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
}

// 邻接表节点结构
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;
}

2 - 算法和应用

需熟练掌握图对于各种问题的应用，在选择题和大题中都是考察重点。

DFS

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

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

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

int visited[MAX_VERTICES];

void dfs(int start, int vertices) {
    visited[start] = 1;
    printf("%d ", start);

    for (int i = 0; i < vertices; i++) {
        if (adjMatrix[start][i] == 1 && !visited[i]) {
            dfs(i, vertices);
        }
    }
}

void dfs(struct Graph* graph, int vertex, int* visited) {
    visited[vertex] = 1;
    printf("%d ", vertex);

    struct Node* temp = graph->adjacencyList[vertex];
    while (temp) {
        int adjVertex = temp->data;
        if (!visited[adjVertex]) {
            dfs(graph, adjVertex, visited);
        }
        temp = temp->next;
    }
}

void dfsTraversal(struct Graph* graph, int startVertex) {
    int* visited = (int*)malloc(graph->vertices * sizeof(int));
    for (int i = 0; i < graph->vertices; i++) {
        visited[i] = 0;
    }

    dfs(graph, startVertex, visited);

    free(visited);
}

BFS

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

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

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

// 从 start 开始遍历图
void bfs(int start, int vertices) {
    enqueue(start);
    visited[start] = 1;

    while (front != -1) {
        int currentVertex = dequeue();
        printf("%d ", currentVertex);

        for (int i = 0; i < vertices; i++) {
            if (adjMatrix[currentVertex][i] == 1 && !visited[i]) {
                enqueue(i);
                visited[i] = 1;
            }
        }
        printf("\n");
    }
}

void bfs(struct Graph* graph, int startVertex) {
    int* visited = (int*)malloc(graph->vertices * sizeof(int));
    for (int i = 0; i < graph->vertices; i++) {
        visited[i] = 0;
    }

    int queue[graph->vertices];
    int front = -1, rear = -1;
    queue[++rear] = startVertex;
    visited[startVertex] = 1;

    printf("BFS traversal starting from vertex %d: ", startVertex);

    while (front != rear) {
        int currentVertex = queue[++front];
        printf("%d ", currentVertex);

        struct Node* temp = graph->adjacencyList[currentVertex];
        while (temp) {
            int adjVertex = temp->data;
            if (!visited[adjVertex]) {
                queue[++rear] = adjVertex;
                visited[adjVertex] = 1;
            }
            temp = temp->next;
        }
    }

    printf("\n");

    free(visited);
}

最小生成树

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

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

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

prim 算法

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

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

kruskal 算法

Kruskal 算法是一种用于求解最小生成树（Minimum Spanning Tree，MST）的贪心算法。Kruskal 算法的基本思想是从边的权重最小的边开始，逐步构建生成树，确保不会形成环路。

以下是 Kruskal 算法的一般流程：

初始化一个空的生成树，开始时生成树中没有边。
将图中的所有边按照权重从小到大进行排序。
依次从排序后的边列表中选取边，加入生成树，但要确保添加该边不会形成环路。可以使用并查集来检查是否形成环路。
重复步骤 3，直到生成树包含了所有的顶点，即生成树中的边数等于顶点数减 1。
返回生成树作为最小生成树。

最短路径

djkstra 算法

Dijkstra 算法的基本思想是从起始顶点开始，逐步扩展已知的最短路径，直到到达所有其他顶点。算法维护一个集合，其中包含已知的最短路径，以及一个优先队列（最小堆）用于选择下一个要探索的顶点。算法的主要步骤如下：

初始化距离数组和集合：
- 创建一个距离数组，用于存储从起始顶点到每个顶点的最短距离。初始时，距离数组中的距离值设置为无穷大，除了起始顶点的距离值为 0。
- 创建一个空的集合，用于存储已知的最短路径。
将起始顶点添加到优先队列中，距离为 0。
重复以下步骤，直到优先队列为空：
- a. 从优先队列中取出距离最短的顶点，将其添加到集合中。
- b. 遍历该顶点的所有邻居，对于每个邻居顶点：
  - 如果该邻居顶点不在集合中（即尚未找到最短路径），则计算从起始顶点经过当前顶点到达邻居顶点的距离。如果这个距离小于目前已知的距离，则更新距离数组中的距离值。
  - 将邻居顶点添加到优先队列中，以备以后探索。
当优先队列为空时，Dijkstra 算法完成，距离数组中存储了从起始顶点到每个顶点的最短距离。
可以使用距离数组来重构最短路径。

Dijkstra_Animation

function Dijkstra(Graph, source):

    for each vertex v in Graph.Vertices:
        dist[v] ← INFINITY
        prev[v] ← UNDEFINED
        add v to Q
    dist[source] ← 0

    while Q is not empty:
        u ← vertex in Q with min dist[u]
        remove u from Q

        for each neighbor v of u still in Q:
            alt ← dist[u] + Graph.Edges(u, v)
            if alt < dist[v]:
                dist[v] ← alt
                prev[v] ← u

    return dist[], prev[]

floyed 算法

Floyd-Warshall 算法是一种用于求解图中所有顶点对之间最短路径的动态规划算法。它适用于有向图和带有权重的边，可以找到从一个顶点到另一个顶点的最短路径，并计算所有顶点对之间的最短路径。

以下是 Floyd-Warshall 算法的一般流程：

初始化距离矩阵：
- 创建一个二维矩阵 dist，其中 dist[i][j] 表示从顶点 i 到顶点 j 的最短路径距离。
- 初始时，将 dist[i][j] 设置为正无穷（表示无法直接从顶点 i 到顶点 j），但当 i 等于 j 时，将 dist[i][j] 设置为 0（表示从顶点 i 到自身的距离为 0）。
- 对于图中的每一条边 (u, v)，如果存在从顶点 u 到顶点 v 的直接路径，则将 dist[u][v] 设置为边的权重。
三重循环进行动态规划：
- 对于每一对顶点 (i, j)，遍历一个中间顶点 k（从 1 到顶点的数量），检查是否存在一条从顶点 i 经过顶点 k 到顶点 j 的路径距离更短。具体步骤如下：
  - 如果 dist[i][j] 大于 dist[i][k] + dist[k][j]，则更新 dist[i][j] 为 dist[i][k] + dist[k][j]。
  - 这意味着通过中间顶点 k 可以找到一条更短的路径。
最终的距离矩阵 dist 包含了所有顶点对之间的最短路径距离。
如果需要，可以使用距离矩阵 dist 来重构具体的最短路径。

拓扑排序

拓扑排序是一种用于有向图中的顶点排序的算法，它使得图中的每一条有向边都从前面的顶点指向后面的顶点。拓扑排序主要应用于有向无环图（DAG）或 AOV 网，这种图没有环路，因此可以对其进行拓扑排序。

AOV 网和 AOE 网

AOV 网（Activity on Vertex Network）：AOV 网是一种以顶点表示活动或任务的网络模型。每个顶点代表一个任务或活动，而边表示任务之间的依赖关系。在 AOV 网中，任务或活动通常表示为顶点，而依赖关系（任务的先后顺序）表示为有向边。
AOE 网（Activity on Edge Network）：AOE 网是一种以边表示活动或任务的网络模型。每条边代表一个任务或活动，而顶点通常表示事件，表示任务的开始或完成时间。在 AOE 网中，任务的持续时间通常不包含在边上，而是与边相连的事件顶点之间的时间差。

算法流程

选择一个没有前驱顶点（入度为 0）的顶点作为起始顶点，将其加入拓扑排序的结果序列中。
从图中移除该顶点以及与之相关的边（即将与之相邻的顶点的入度减 1）。
重复步骤 1 和步骤 2，直到所有的顶点都被加入到拓扑排序的结果序列中，或者发现图中存在环路。
如果所有的顶点都被成功加入结果序列，那么这个序列就是拓扑排序的结果。

拓扑排序的结果序列可能不唯一，因为有多个入度为 0 的顶点可以作为起始顶点。如果图中存在环路，那么无法进行拓扑排序，因为无法找到入度为 0 的顶点作为起始顶点。

拓扑排序的时间复杂度通常为 $O(V + E)$ ，其中 $V$ 是顶点的数量， $E$ 是边的数量。这个算法非常适合于解决任务调度和依赖关系问题，因为它可以确定任务的执行顺序或依赖关系的合理性。

关键路径

前提概念

源点：在 $AOE$ 网中仅有一个入度为 $0$ 的顶点，称为开始顶点，表示整个工程的开始。
汇点：在 $AOE$ 网中仅有一个出度为 $0$ 的顶点，称为结束结点，表示整个工程的结束。
关键路径的长度：完成整个工程的最短时间，也是 $AOE$ 网中从源点到汇点的最长路径。
关键活动：关键路径上的活动。
$ve(k)$：事件 $v_k$ 的最早可以发生时间。
$vl(k)$：事件 $v_k$ 的最晚可以发生时间。

算法步骤

概要总结：找到所有最早发生时间和最晚发生时间相同的结点，连接这些结点即可得到关键路径。

具体步骤：

从源点出发，令 $ve(start) = 0$ ，按照拓扑排序求其他顶点的最早发生时间 $ve$ 。
- 对于源点：$ve(start) = 0$。
- 对于后续结点：$ve(k) = \text{Max} \{ ve(j) + weight(v_j, v_k) \}$，$v_k$ 为 $v_j$ 的任意后继，$weight(v_j, v_k)$ 表示 $<v_j, v_k>$ 的权值。
从汇点出发，令 $vl(end) = ve(end)$，按逆拓扑有序求其余顶点的最迟发生时间 $vl$。
- 对于汇点：$vl(end) = 0$。
- 对于前继结点：$vl(k) = \text{Min} \{ vl(j) - weight(v_k, v_j) \}$，$v_k$ 为 $v_j$ 的任意前驱。
连接所有 $ve(i) = vl(i)$ 的结点 $i$，得到关键路径。下图中例子中所有 $ve$ 和 $vl$ 相同的结点为$v_1, v_3, v_4, v_6$，其对应的关键路径为 $v_1 \rightarrow v_3 \rightarrow v_4 \rightarrow v_6$ 即 $a_2, a_5, a_7$。

关键路径的特点：

关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可通过加快关键活动来缩短整个工程的工期。
AOE 网中的关键路径并不唯一，对于有几条关键路径的网，只加快一条关键路径，需要同时加快多个关键路径。

用图表达树

当表达式中存在共享的子表达式时，二叉树可能不是存储这些表达式的最有效方式，因为它会重复存储共享的子表达式。在这种情况下，可以使用有向无环图（Directed Acyclic Graph, DAG）来表示表达式，这样可以避免重复，并且更有效地表示表达式。

比如对于表达式 (x + y) * ((x + y) / x)，用二叉树和DAG的表示如下图：

图