数据结构——图

一、引言

在计算机科学中，图是一种非常强大的数据结构，它能够表示复杂的对象关系。从社交网络到交通网络，从计算机网络到项目任务调度，图的应用无处不在。理解图的基本概念、表示方法以及常见算法，对于解决实际问题具有重要意义。本文将详细介绍图的基本概念、存储结构、基本操作以及一些常见的图算法，帮助大家更好地掌握这一数据结构。

二、图的基本概念

（一）定义

图（Graph）是由顶点（Vertex）集合和边（Edge）集合组成的数据结构，通常表示为 G=(V,E)，其中 V 是顶点集合，E 是边集合。图可以分为以下几种类型：

1. 无向图（Undirected Graph）：图中的边没有方向，即边 (u,v) 和 (v,u) 是相同的。

2. 有向图（Directed Graph）：图中的边有方向，即边 (u,v) 和 (v,u) 是不同的。

3. 加权图（Weighted Graph）：图中的每条边都有一个权重（Weight），用于表示边的代价或距离。

（二）基本术语

1. 顶点（Vertex）：图中的一个节点，表示一个实体。

2. 边（Edge）：连接两个顶点的线，表示两个实体之间的关系。

3. 度（Degree）：

   • 在无向图中，一个顶点的度是指与该顶点相连的边的数量。

   • 在有向图中，一个顶点的度分为入度（In - Degree）和出度（Out - Degree）。入度是指指向该顶点的边的数量，出度是指从该顶点出发的边的数量。

4. 路径（Path）：从一个顶点到另一个顶点的边的序列。

5. 简单路径（Simple Path）：路径中不包含重复的顶点。

6. 环（Cycle）：起点和终点相同的路径。

7. 连通图（Connected Graph）：在无向图中，任意两个顶点之间都存在路径。

8. 定义：使用一个二维数组来表示图的顶点之间的关系。对于无向图，如果顶点 u 和顶点 v 之间有边，则 matrix[u][v]=1（或权重值），否则为 0。对于有向图，矩阵的行表示出发顶点，列表示到达顶点。

   • 强连通图（Strongly Connected Graph）：在有向图中，任意两个顶点之间都存在双向路径。

   • 子图（Subgraph）：由原图的一部分顶点和边组成的图。

   • 生成树（Spanning Tree）：一个连通图的生成树是一个包含图中所有顶点的无环连通子图。

三、图的存储结构

（一）邻接矩阵（Adjacency Matrix）

1. 定义：使用一个二维数组来表示图的顶点之间的关系。对于无向图，如果顶点 u 和顶点 v 之间有边，则 matrix[u][v]=1（或权重值），否则为 0。对于有向图，矩阵的行表示出发顶点，列表示到达顶点。

2. 优点：

   • 简单直观，容易实现。

   • 适合稠密图（边数较多的图）。

3. 缺点：

   • 空间复杂度高，对于稀疏图（边数较少的图）非常浪费空间。

   • 遍历邻接点时效率较低。

二）邻接表（Adjacency List）

1. 定义：使用一个数组存储所有顶点，每个顶点对应一个链表，链表中存储与该顶点相邻的顶点。

2. 优点：

   • 空间复杂度低，适合稀疏图。

   • 遍历邻接点时效率较高。

3. 缺点：

   • 实现相对复杂，需要管理链表。

（三）边表（Edge List）

1. 定义：使用一个数组或链表存储图中的所有边。每条边包含两个顶点（对于无向图）或两个顶点和方向（对于有向图）。

2. 优点：

   • 实现简单，适合边的操作。

3. 缺点：

   • 遍历邻接点时效率较低，需要遍历整个边表。

四、图的基本操作

（一）创建图

以下是使用邻接表创建图的C语言代码示例：

#include <stdio.h>
#include <stdlib.h>// 定义图的顶点结构
typedef struct Vertex {int id;                   // 顶点编号struct Edge* edges;       // 指向边的链表
} Vertex;// 定义图的边结构
typedef struct Edge {int target;               // 边的目标顶点编号struct Edge* next;        // 指向下一个边
} Edge;// 定义图结构
typedef struct Graph {int num_vertices;         // 顶点数量Vertex* vertices;         // 顶点数组
} Graph;// 创建图
Graph* create_graph(int num_vertices) {Graph* graph = (Graph*)malloc(sizeof(Graph));graph->num_vertices = num_vertices;graph->vertices = (Vertex*)malloc(num_vertices * sizeof(Vertex));for (int i = 0; i < num_vertices; i++) {graph->vertices[i].id = i;graph->vertices[i].edges = NULL;}return graph;
}// 添加边（无向图）
void add_edge(Graph* graph, int src, int dest) {// 添加从 src 到 dest 的边Edge* edge1 = (Edge*)malloc(sizeof(Edge));edge1->target = dest;edge1->next = graph->vertices[src].edges;graph->vertices[src].edges = edge1;// 添加从 dest 到 src 的边（无向图）Edge* edge2 = (Edge*)malloc(sizeof(Edge));edge2->target = src;edge2->next = graph->vertices[dest].edges;graph->vertices[dest].edges = edge2;
}// 释放图的内存
void free_graph(Graph* graph) {for (int i = 0; i < graph->num_vertices; i++) {Edge* edge = graph->vertices[i].edges;while (edge != NULL) {Edge* temp = edge;edge = edge->next;free(temp);}}free(graph->vertices);free(graph);
}

（二）遍历图

1. 深度优先搜索（DFS）：

void dfs(Graph* graph, int vertex, int visited[]) {visited[vertex] = 1;printf("%d ", vertex);Edge* edge = graph->vertices[vertex].edges;while (edge != NULL) {if (!visited[edge->target]) {dfs(graph, edge->target, visited);}edge = edge->next;}
}void dfs_traversal(Graph* graph) {int visited[graph->num_vertices] = {0};for (int i = 0; i < graph->num_vertices; i++) {if (!visited[i]) {dfs(graph, i, visited);}}
}

 广度优先搜索（BFS）：

#include <queue.h> // 假设有一个简单的队列库void bfs(Graph* graph, int start) {int visited[graph->num_vertices] = {0};Queue* queue = create_queue();enqueue(queue, start);visited[start] = 1;while (!is_queue_empty(queue)) {int vertex = dequeue(queue);printf("%d ", vertex);Edge* edge = graph->vertices[vertex].edges;while (edge != NULL) {if (!visited[edge->target]) {enqueue(queue, edge->target);visited[edge->target] = 1;}edge = edge->next;}}free_queue(queue);
}

五、常见的图算法

（一）最短路径算法

1. Dijkstra算法：用于计算单源最短路径，适用于加权图且边的权重为非负数。

void floyd(Graph* graph) {int dist[graph->num_vertices][graph->num_vertices];for (int i = 0; i < graph->num_vertices; i++) {for (int j = 0; j < graph->num_vertices; j++) {if (i == j) {dist[i][j] = 0;} else {dist[i][j] = INT_MAX;}}}for (int i = 0; i < graph->num_vertices; i++) {Edge* edge = graph->vertices[i].edges;while (edge != NULL) {dist[i][edge->target] = 1;edge = edge->next;}}for (int k = 0; k < graph->num_vertices; k++) {for (int i = 0; i < graph->num_vertices; i++) {for (int j = 0; j < graph->num_vertices; j++) {if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];}}}}for (int i = 0; i < graph->num_vertices; i++) {for (int j = 0; j < graph->num_vertices; j++) {if (dist[i][j] == INT_MAX) {printf("从 %d 到 %d 没有路径\n", i, j);} else {printf("从 %d 到 %d 的最短距离是 %d\n", i, j, dist[i][j]);}}}
}

Floyd算法：用于计算所有顶点对之间的最短路径，适用于加权图。

 

void floyd(Graph* graph) {int dist[graph->num_vertices][graph->num_vertices];for (int i = 0; i < graph->num_vertices; i++) {for (int j = 0; j < graph->num_vertices; j++) {if (i == j) {dist[i][j] = 0;} else {dist[i][j] = INT_MAX;}}}for (int i = 0; i < graph->num_vertices; i++) {Edge* edge = graph->vertices[i].edges;while (edge != NULL) {dist[i][edge->target] = 1;edge = edge->next;}}for (int k = 0; k < graph->num_vertices; k++) {for (int i = 0; i < graph->num_vertices; i++) {for (int j = 0; j < graph->num_vertices; j++) {if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];}}}}for (int i = 0; i < graph->num_vertices; i++) {for (int j = 0; j < graph->num_vertices; j++) {if (dist[i][j] == INT_MAX) {printf("从 %d 到 %d 没有路径\n", i, j);} else {printf("从 %d 到 %d 的最短距离是 %d\n", i, j, dist[i][j]);}}}
}

六、总结

图是一种非常强大的数据结构，它能够表示复杂的对象关系。本文介绍了图的基本概念、存储结构、基本操作以及一些常见的图算法，如深度优先搜索、广度优先搜索、最短路径算法和最小生成树算法。通过这些内容，读者可以对图有一个初步的了解，并能够在实际编程中应用这些知识。希望本文能够帮助大家更好地掌握图这一数据结构。

---

以上内容为图的介绍和实现代码，希望对大家有所帮助。欢迎随时留言讨论！