一、引言
在计算机科学中，图是一种非常强大的数据结构，它能够表示复杂的对象关系。从社交网络到交通网络，从计算机网络到项目任务调度，图的应用无处不在。理解图的基本概念、表示方法以及常见算法，对于解决实际问题具有重要意义。本文将详细介绍图的基本概念、存储结构、基本操作以及一些常见的图算法，帮助大家更好地掌握这一数据结构。
二、图的基本概念
（一）定义
图（Graph）是由顶点（Vertex）集合和边（Edge）集合组成的数据结构，通常表示为 G=(V,E)，其中 V 是顶点集合，E 是边集合。图可以分为以下几种类型：
无向图（Undirected Graph）：图中的边没有方向，即边 (u,v) 和 (v,u) 是相同的。
有向图（Directed Graph）：图中的边有方向，即边 (u,v) 和 (v,u) 是不同的。
加权图（Weighted Graph）：图中的每条边都有一个权重（Weight），用于表示边的代价或距离。
（二）基本术语
顶点（Vertex）：图中的一个节点，表示一个实体。
边（Edge）：连接两个顶点的线，表示两个实体之间的关系。
度（Degree）：
在无向图中，一个顶点的度是指与该顶点相连的边的数量。
在有向图中，一个顶点的度分为入度（In - Degree）和出度（Out - Degree）。入度是指指向该顶点的边的数量，出度是指从该顶点出发的边的数量。
路径（Path）：从一个顶点到另一个顶点的边的序列。
简单路径（Simple Path）：路径中不包含重复的顶点。
环（Cycle）：起点和终点相同的路径。
连通图（Connected Graph）：在无向图中，任意两个顶点之间都存在路径。
定义：使用一个二维数组来表示图的顶点之间的关系。对于无向图，如果顶点 u 和顶点 v 之间有边，则 matrix[u][v]=1（或权重值），否则为 0。对于有向图，矩阵的行表示出发顶点，列表示到达顶点。
强连通图（Strongly Connected Graph）：在有向图中，任意两个顶点之间都存在双向路径。
子图（Subgraph）：由原图的一部分顶点和边组成的图。
生成树（Spanning Tree）：一个连通图的生成树是一个包含图中所有顶点的无环连通子图。
三、图的存储结构
（一）邻接矩阵（Adjacency Matrix）
定义：使用一个二维数组来表示图的顶点之间的关系。对于无向图，如果顶点 u 和顶点 v 之间有边，则 matrix[u][v]=1（或权重值），否则为 0。对于有向图，矩阵的行表示出发顶点，列表示到达顶点。
优点：
简单直观，容易实现。
适合稠密图（边数较多的图）。
缺点：
空间复杂度高，对于稀疏图（边数较少的图）非常浪费空间。
遍历邻接点时效率较低。
二）邻接表（Adjacency List）
定义：使用一个数组存储所有顶点，每个顶点对应一个链表，链表中存储与该顶点相邻的顶点。
优点：
空间复杂度低，适合稀疏图。
遍历邻接点时效率较高。
缺点：
实现相对复杂，需要管理链表。
（三）边表（Edge List）
定义：使用一个数组或链表存储图中的所有边。每条边包含两个顶点（对于无向图）或两个顶点和方向（对于有向图）。
优点：
实现简单，适合边的操作。
缺点：
遍历邻接点时效率较低，需要遍历整个边表。
四、图的基本操作
（一）创建图
以下是使用邻接表创建图的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);
}（二）遍历图
深度优先搜索（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);
}五、常见的图算法
（一）最短路径算法
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]);
}
}
}
}六、总结
图是一种非常强大的数据结构，它能够表示复杂的对象关系。本文介绍了图的基本概念、存储结构、基本操作以及一些常见的图算法，如深度优先搜索、广度优先搜索、最短路径算法和最小生成树算法。通过这些内容，读者可以对图有一个初步的了解，并能够在实际编程中应用这些知识。希望本文能够帮助大家更好地掌握图这一数据结构。
以上内容为图的介绍和实现代码，希望对大家有所帮助。欢迎随时留言讨论！