目录
一 .图的概念
在数据结构中，图（Graph）是由一组有限的顶点（Vertex）和连接这些顶点的边（Edge）组成。图是一种非常灵活且广泛使用的数据结构，它可以表示各种复杂的关系和结构。
图可以分为有向图和无向图。在有向图中，边是有方向的，表示从一个顶点指向另一个顶点的关系。而在无向图中，边是没有方向的，表示顶点之间的关系是双向的。
图中的顶点和边通常会包含一些附加的信息。例如，顶点可能包含一个标签或值，边可能包含一个权重或标签。这些附加的信息可以用来描述顶点和边之间的关系或属性。
二 .图的存储以及基本操作
图的存储可以使用多种数据结构来实现，常见的存储方式包括邻接矩阵，邻接表，十字链表和邻接多重表。
1.邻接矩阵
邻接矩阵使用一个二维数组来存储图的信息。对于一个有 n个顶点的图，我们创建一个 n \times n 的数组。如果顶点 i 和顶点 j 之间存在一条边，则将数组中对应位置的值设置为 1 或 true；否则，设置为 0或 false。如果图是有向图，则数组中的元素表示从 i 到 j 是否存在一条边；如果图是无向图，则表示 i 和 j 是否直接相连。
使用邻接矩阵表示图的优点是可以直观地表示顶点之间的连接关系，并且可以在 O(1) 的时间内判断两个顶点之间是否存在边。然而，当图的边数较少时，邻接矩阵会浪费大量的空间，因为大部分元素都是 0。
实现代码：
#include <iostream>
const int MAX_VERTICES = 10;
bool adjMatrix[MAX_VERTICES][MAX_VERTICES];
void addEdge(int u, int v) {
adjMatrix[u][v] = true;
adjMatrix[v][u] = true; // 对于无向图
}
void printGraph() {
for (int i = 0; i < MAX_VERTICES; i++) {
for (int j = 0; j < MAX_VERTICES; j++) {
std::cout << adjMatrix[i][j] << " ";
}
std::cout << std::endl;
}
}
int main() {
addEdge(0, 1);
addEdge(0, 4);
addEdge(1, 2);
addEdge(1, 3);
addEdge(1, 4);
addEdge(2, 3);
addEdge(3, 4);
printGraph();
return 0;
}
在上面的代码中，我们定义了一个 10 个顶点的无向图。addEdge 函数用于添加边，将对应位置的值设置为 true。printGraph 函数用于打印邻接矩阵
2.邻接表
邻接表使用链表或数组来存储每个顶点的相邻顶点。对于每个顶点，我们维护一个列表，包含所有与该顶点直接相连的顶点。对于有向图，我们可以使用两个列表分别表示入边和出边。
在邻接表中，每个顶点对应一个链表，链表中的节点存储了与该顶点相邻的其他顶点。如果是有向图，则可以为每个顶点维护两个链表，一个链表存储该顶点的出边，另一个链表存储该顶点的入边。
使用邻接表表示图的优点是节省了空间，尤其适用于稀疏图，因为只需要存储实际存在的边，不会浪费空间。此外，邻接表使得查找某个顶点的相邻顶点更加高效，因为只需要遍历链表即可。
实现代码：
#include <iostream>
#include <vector>
#include <list>
const int MAX_VERTICES = 10;
std::vector<std::list<int>> adjList(MAX_VERTICES);
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u); // 对于无向图
}
void printGraph() {
for (int i = 0; i < MAX_VERTICES; i++) {
std::cout << "Vertex " << i << ": ";
for (int neighbor : adjList[i]) {
std::cout << neighbor << " ";
}
std::cout << std::endl;
}
}
int main() {
addEdge(0, 1);
addEdge(0, 4);
addEdge(1, 2);
addEdge(1, 3);
addEdge(1, 4);
addEdge(2, 3);
addEdge(3, 4);
printGraph();
return 0;
}
在上面的代码中，我们使用 std::list 来存储每个顶点的相邻顶点。addEdge 函数用于向邻接表中添加边。printGraph 函数用于打印邻接表。
3.十字链表
十字链表是一种用于存储图的高级数据结构，它结合了邻接表和边表的优点，可以高效地存储和操作图中的顶点和边。在十字链表中，每个顶点和边都使用一个单独的链表节点来表示。
在十字链表中，我们维护两个链表：顶点链表和边链表。顶点链表中的每个节点表示一个顶点，并包含指向该顶点的所有出边链表节点的指针。边链表中的每个节点表示一条边，并包含指向这条边所连接的两个顶点的指针。
以下是十字链表的示意图：
+---------+
| Vertex1 |
+---------+
| next_vertex | first_edge
+---------+ |
| Vertex2 |------+---------------------> NULL
+---------+ |
| next_vertex | first_edge |
+---------+ |
| Vertex3 |------+---------------------> NULL
+---------+ |
| next_vertex | first_edge |
+---------+ |
| Vertex4 |------+---------------------> NULL
+---------+
在这个示意图中，我们有四个顶点（Vertex1、Vertex2、Vertex3 和 Vertex4）。每个顶点都有一个 next_vertex 指针，组成顶点链表。此外，每个顶点都有一个 first_edge 指针，指向该顶点的出边链表节点。
以下是对应的边链表节点：
+---------+
| Edge1 |
+---------+
| source | destination | next_out | next_in
+---------+ | |
| Vertex1 | Vertex2 | NULL | NULL
+---------+ | |
| Edge2 |------+---------------------> NULL
+---------+ |
| source | destination | next_out | next_in
+---------+ | |
| Vertex1 | Vertex3 | NULL | NULL
+---------+ |
| Edge3 |------+---------------------> NULL
+---------+ |
| source | destination | next_out | next_in
+---------+ | |
| Vertex1 | Vertex4 | NULL | NULL
+---------+ |
| Edge4 |------+---------------------> NULL
+---------+
在这个示意图中，我们有四个边（Edge1、Edge2、Edge3 和 Edge4）。每个边都有 source 和 destination 指针，分别指向边的起始顶点和目的顶点。此外，每个边都有 next_out 和 next_in 指针，用于组成出边链表和入边链表。
以下是实现十字链表存储图的代码
#include <iostream>
class EdgeNode;
class VertexNode {
public:
int vertex_id;
VertexNode* next_vertex;
EdgeNode* first_edge;
VertexNode(int id) : vertex_id(id), next_vertex(nullptr), first_edge(nullptr) {}
};
class EdgeNode {
public:
int source, destination;
EdgeNode* next_out, *next_in;
EdgeNode(int src, int dest) : source(src), destination(dest), next_out(nullptr), next_in(nullptr) {}
};
class Graph {
private:
VertexNode* head_vertex;
public:
Graph() : head_vertex(nullptr) {}
// 添加顶点
VertexNode* addVertex(int id) {
VertexNode* newVertex = new VertexNode(id);
if (head_vertex == nullptr) {
head_vertex = newVertex;
} else {
VertexNode* current = head_vertex;
while (current->next_vertex != nullptr) {
current = current->next_vertex;
}
current->next_vertex = newVertex;
}
return newVertex;
}
// 添加边
void addEdge(int source, int destination) {
VertexNode* sourceVertex = findVertex(source);
VertexNode* destinationVertex = findVertex(destination);
if (sourceVertex == nullptr || destinationVertex == nullptr) {
std::cout << "Source or destination vertex does not exist." << std::endl;
return;
}
EdgeNode* newEdge = new EdgeNode(source, destination);
newEdge->next_out = sourceVertex->first_edge;
sourceVertex->first_edge = newEdge;
newEdge->next_in = destinationVertex->first_edge;
destinationVertex->first_edge = newEdge;
}
// 查找顶点
VertexNode* findVertex(int id) {
VertexNode* current = head_vertex;
while (current != nullptr && current->vertex_id != id) {
current = current->next_vertex;
}
return current;
}
// 打印图
void printGraph() {
VertexNode* currentVertex = head_vertex;
while (currentVertex != nullptr) {
std::cout << "Vertex " << currentVertex->vertex_id << ": ";
EdgeNode* currentEdge = currentVertex->first_edge;
while (currentEdge != nullptr) {
std::cout << "(" << currentEdge->source << ", " << currentEdge->destination << ") ";
currentEdge = currentEdge->next_out;
}
std::cout << std::endl;
currentVertex = currentVertex->next_vertex;
}
}
};
int main() {
Graph graph;
// 添加顶点
VertexNode* vertex1 = graph.addVertex(1);
VertexNode* vertex2 = graph.addVertex(2);
VertexNode* vertex3 = graph.addVertex(3);
VertexNode* vertex4 = graph.addVertex(4);
// 添加边
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 4);
// 打印图
graph.printGraph();
return 0;
}
4.邻接多重表
邻接多重表是另一种用于存储图的高级数据结构，它结合了邻接表和十字链表的优点，可以高效地存储和操作稠密图。在邻接多重表中，我们使用一个二维数组来存储图的信息，其中每个元素表示一条边。
以下是邻接多重表的关键组成部分：
- 顶点数组：一个一维数组，用于存储图中的所有顶点。每个元素表示一个顶点，并包含一个标识符或值。
- 边数组：一个二维数组，用于存储图中的所有边。对于每个顶点，我们维护一个单独的一维数组，包含该顶点的所有出边。
- 顶点指针数组：一个一维数组，用于存储指向顶点数组中每个顶点的指针。
- 边指针数组：一个二维数组，用于存储指向边数组中每个边的指针。
以下是邻接多重表的示意图：
+---------+
| Vertex1 |
+---------+
| Vertex2 |
+---------+
| Vertex3 |
+---------+
| Vertex4 |
+---------+
+---------+
| Edge1 |
+---------+
| Edge2 |
+---------+
| Edge3 |
+---------+
| Edge4 |
+---------+
+---------+
| Vertex1 |
+---------+
| Vertex2 |
+---------+
| Vertex3 |
+---------+
| Vertex4 |
+---------+
+---------+---------+---------+---------+
| NULL | Edge1 | Edge2 | NULL |
+---------+---------+---------+---------+
| NULL | NULL | Edge3 | Edge4 |
+---------+---------+---------+---------+
| Vertex1 | Vertex2 | Vertex3 | Vertex4 |
+---------+---------+---------+---------+
在这个示意图中，我们有四个顶点（Vertex1、Vertex2、Vertex3 和 Vertex4），存储在顶点数组中。此外，我们有四个边（Edge1、Edge2、Edge3 和 Edge4），存储在边数组中。
每个顶点都有一个对应的边数组，包含该顶点的所有出边。例如，Vertex1 的边数组包含 Edge1 和 Edge2，表示从 Vertex1 出发的两条边。
邻接多重表的主要优点在于它的紧凑性和高效性。通过使用二维数组，我们可以紧凑地存储稠密图的信息，并快速地访问和操作图中的顶点和边。此外，邻接多重表还允许我们在常数时间内添加或删除边，这使得它非常适合处理稠密图的存储和操作。
实现邻接多重表存储图的代码
#include <iostream>
#include <vector>
class Graph {
private:
std::vector<int> vertex_array;
std::vector<std::vector<int>> edge_array;
std::vector<int*> vertex_pointers;
std::vector<std::vector<int*>> edge_pointers;
public:
Graph(int numVertices) : vertex_array(numVertices), edge_array(numVertices, std::vector<int>(numVertices, 0)),
vertex_pointers(numVertices, nullptr), edge_pointers(numVertices, std::vector<int*>(numVertices, nullptr)) {}
// 初始化顶点指针
void initVertexPointers() {
for (int i = 0; i < vertex_array.size(); i++) {
vertex_pointers[i] = &vertex_array[i];
}
}
// 初始化边指针
void initEdgePointers() {
for (int i = 0; i < vertex_array.size(); i++) {
for (int j = 0; j < vertex_array.size(); j++) {
edge_pointers[i][j] = &edge_array[i][j];
}
}
}
// 添加边
void addEdge(int source, int destination) {
edge_array[source][destination] = 1;
}
// 打印图
void printGraph() {
for (int i = 0; i < vertex_array.size(); i++) {
std::cout << "Vertex " << i << ": ";
for (int j = 0; j < vertex_array.size(); j++) {
if (edge_array[i][j] == 1) {
std::cout << "(" << i << ", " << j << ") ";
}
}
std::cout << std::endl;
}
}
};
int main() {
int numVertices = 4;
Graph graph(numVertices);
// 初始化顶点指针和边指针
graph.initVertexPointers();
graph.initEdgePointers();
// 添加边
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
// 打印图
graph.printGraph();
return 0;
}
5.图的基本操作
在数据结构中，图的基本操作包括添加顶点、添加边、删除顶点、删除边、查找顶点、查找边等。以下是使用邻接表存储图的基本操作的代码实现：
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
// 定义图类
class Graph {
private:
unordered_map<int, vector<int>> adjList; // 邻接表存储图的结构
public:
// 添加顶点
void addVertex(int v) {
if (adjList.find(v) == adjList.end()) {
adjList[v] = vector<int>();
}
}
// 添加边
void addEdge(int u, int v) {
addVertex(u);
addVertex(v);
adjList[u].push_back(v);
adjList[v].push_back(u); // 如果是有向图，则删除该行
}
// 删除顶点
void removeVertex(int v) {
if (adjList.find(v) != adjList.end()) {
adjList.erase(v);
// 删除所有与顶点v相关的边
for (auto& pair : adjList) {
auto& edges = pair.second;
edges.erase(remove(edges.begin(), edges.end(), v), edges.end());
}
}
}
// 删除边
void removeEdge(int u, int v) {
if (adjList.find(u) != adjList.end() && adjList.find(v) != adjList.end()) {
adjList[u].erase(remove(adjList[u].begin(), adjList[u].end(), v), adjList[u].end());
adjList[v].erase(remove(adjList[v].begin(), adjList[v].end(), u), adjList[v].end()); // 如果是有向图，则删除该行
}
}
// 查找顶点
bool hasVertex(int v) {
return adjList.find(v) != adjList.end();
}
// 查找边
bool hasEdge(int u, int v) {
if (adjList.find(u) != adjList.end() && adjList.find(v) != adjList.end()) {
return find(adjList[u].begin(), adjList[u].end(), v) != adjList[u].end();
}
return false;
}
};
int main() {
Graph g;
// 添加顶点
g.addVertex(1);
g.addVertex(2);
g.addVertex(3);
g.addVertex(4);
// 添加边
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.addEdge(3, 4);
// 删除顶点和边
g.removeVertex(3);
g.removeEdge(1, 2);
// 查找顶点和边
cout << "Vertex 2 exists: " << (g.hasVertex(2) ? "true" : "false") << endl;
cout << "Edge (2, 3) exists: " << (g.hasEdge(2, 3) ? "true" : "false") << endl;
return 0;
}
三 .图的遍历
图的遍历是指按照一定的顺序访问图中的所有顶点和边。常见的图遍历算法包括广度优先搜索（BFS）和深度优先搜索（DFS）。
1.广度优先搜索（BFS）
广度优先搜索（BFS）是一种从根节点开始，按照层次顺序遍历图的算法。它使用一个队列来存储待访问的顶点。在每一步，算法从队列中取出一个顶点，并访问该顶点的相邻顶点。
BFS的实现步骤如下：
- 将根节点放入队列中，并标记为已访问。
- 从队列中取出一个顶点，并访问该顶点。
- 遍历该顶点的所有未访问过的相邻顶点，并将它们放入队列中，并标记为已访问。
- 重复步骤2和步骤3，直到队列为空。
BFS遍历的顺序是按照层次逐层遍历的，即先访问根节点，然后依次访问与根节点直接相连的顶点，再访问与这些顶点直接相连的顶点，依次类推，直到遍历完整个图。
#include <iostream>
#include <vector>
#include <queue>
const int MAX_VERTICES = 10;
std::vector<std::vector<int>> adjMatrix(MAX_VERTICES, std::vector<int>(MAX_VERTICES, 0));
void bfs(int startVertex) {
std::queue<int> q;
std::vector<bool> visited(MAX_VERTICES, false);
q.push(startVertex);
visited[startVertex] = true;
while (!q.empty()) {
int currentVertex = q.front();
q.pop();
std::cout << currentVertex << " ";
for (int i = 0; i < MAX_VERTICES; i++) {
if (adjMatrix[currentVertex][i] == 1 && !visited[i]) {
q.push(i);
visited[i] = true;
}
}
}
}
int main() {
adjMatrix[0][1] = adjMatrix[0][4] = adjMatrix[1][2] = adjMatrix[1][3] = adjMatrix[1][4] = adjMatrix[2][3] = adjMatrix[3][4] = 1;
bfs(0);
return 0;
}
2.深度优先搜索（DFS）
深度优先搜索（DFS）是一种从根节点开始，尽可能深地遍历图的算法。它使用一个栈来存储待访问的顶点。在每一步，算法从栈中取出一个顶点，并访问该顶点的相邻顶点。
DFS的实现步骤如下：
- 将根节点压入栈中，并标记为已访问。
- 从栈中取出一个顶点，并访问该顶点。
- 遍历该顶点的所有未访问过的相邻顶点，将它们压入栈中，并标记为已访问。
- 重复步骤2和步骤3，直到栈为空。
DFS遍历的顺序是先沿着一条路径尽可能深地访问，直到到达最深的顶点，然后回溯到上一个节点，再选择另一条路径继续深度遍历。
#include <iostream>
#include <vector>
#include <stack>
const int MAX_VERTICES = 10;
std::vector<std::vector<int>> adjMatrix(MAX_VERTICES, std::vector<int>(MAX_VERTICES, 0));
void dfs(int currentVertex, std::vector<bool>& visited) {
visited[currentVertex] = true;
std::cout << currentVertex << " ";
for (int i = 0; i < MAX_VERTICES; i++) {
if (adjMatrix[currentVertex][i] == 1 && !visited[i]) {
dfs(i, visited);
}
}
}
int main() {
adjMatrix[0][1] = adjMatrix[0][4] = adjMatrix[1][2] = adjMatrix[1][3] = adjMatrix[1][4] = adjMatrix[2][3] = adjMatrix[3][4] = 1;
std::vector<bool> visited(MAX_VERTICES, false);
dfs(0, visited);
return 0;
}
四 .图的运用
图的数据结构在很多领域都有广泛的应用，例如：
- 最小生成树： 最小生成树在网络设计、电力传输、通信网络等领域有广泛的应用。例如，在城市道路规划中，最小生成树可以用来确定连接所有城市的最短路径网络，以最小化建设成本。在电力传输中，最小生成树可以用来设计输电线路网络，以最小化能量损耗。
- 最短路径： 最短路径算法被广泛应用于导航系统、路由算法、交通规划等领域。例如，在导航系统中，最短路径算法可以帮助用户找到从起点到终点的最短驾驶路线。在通信网络中，路由算法使用最短路径算法确定数据包的传输路径，以最小化延迟和网络拥塞。
- 有向无环图描述表达式： 有向无环图可以用于描述复杂的计算表达式和编程语言中的控制流程。在编译器中，有向无环图用于表示代码的依赖关系和控制流图，以便进行代码优化和静态分析。在数学建模中，有向无环图可以用于描述数据流程和计算过程，例如在流程图中描述算法和流程。
- 拓扑排序： 拓扑排序在任务调度、依赖关系分析、编译顺序等领域有重要应用。例如，在项目管理中，拓扑排序可以帮助确定任务的执行顺序，以最小化项目完成时间。在编译器中，拓扑排序用于确定代码中变量和函数的依赖关系，以便正确地进行编译和链接。
- 关键路径： 关键路径在项目管理和生产调度中起着重要作用。在项目管理中，关键路径可以帮助项目经理确定项目中关键任务和关键路径，以便及时调整资源和安排任务，确保项目按时完成。在生产调度中，关键路径可以用于确定生产流程中的瓶颈和关键步骤，以最大化生产效率和资源利用率。
五 .总结
图的数据结构还经常用于解决各种算法问题，例如最短路径、最小生成树、最大流等。一些常见的算法包括 Dijkstra 算法、Prim 算法、Kruskal 算法、Ford-Fulkerson 算法等。
总之，图的数据结构是一种强大的工具，可以用来表示和解决各种复杂的问题和关系。通过使用图的存储、遍历和应用，我们可以有效地分析和处理现实世界中的复杂数据和关系。