C 语言图基础
介绍
图(Graph)是一种非常重要的数据结构,用于表示对象之间的关系。图由**顶点(Vertex)和边(Edge)**组成,顶点表示对象,边表示对象之间的关系。图广泛应用于社交网络、路径规划、网络拓扑等领域。
在C语言中,图可以通过多种方式表示,最常见的是邻接矩阵和邻接表。本文将逐步讲解图的基本概念、表示方法以及实际应用。
图的基本概念
顶点和边
- 顶点(Vertex):图中的节点,表示一个对象。
- 边(Edge):连接两个顶点的线,表示两个对象之间的关系。边可以是有向的(Directed)或无向的(Undirected)。
图的类型
- 无向图(Undirected Graph):边没有方向,表示双向关系。
- 有向图(Directed Graph):边有方向,表示单向关系。
- 加权图(Weighted Graph):边带有权重,表示关系的强度或成本。
图的表示方法
1. 邻接矩阵
邻接矩阵是一个二维数组,用于表示图中顶点之间的连接关系。如果图有 n
个顶点,则邻接矩阵是一个 n x n
的矩阵。
- 如果顶点
i
和顶点j
之间有边,则matrix[i][j] = 1
(对于无向图,matrix[j][i] = 1
)。 - 如果顶点
i
和顶点j
之间没有边,则matrix[i][j] = 0
。
c
#include <stdio.h>
#define V 4 // 顶点数量
// 初始化邻接矩阵
void initGraph(int graph[V][V]) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
graph[i][j] = 0;
}
}
}
// 添加边
void addEdge(int graph[V][V], int src, int dest) {
graph[src][dest] = 1;
graph[dest][src] = 1; // 无向图需要双向设置
}
// 打印邻接矩阵
void printGraph(int graph[V][V]) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
printf("%d ", graph[i][j]);
}
printf("\n");
}
}
int main() {
int graph[V][V];
initGraph(graph);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
printGraph(graph);
return 0;
}
输出:
0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0
提示
邻接矩阵适合表示稠密图(边数接近顶点数的平方),但对于稀疏图(边数远少于顶点数的平方),会浪费大量空间。
2. 邻接表
邻接表使用链表或动态数组来存储每个顶点的邻居。对于稀疏图,邻接表更节省空间。
c
#include <stdio.h>
#include <stdlib.h>
// 邻接表节点
struct Node {
int dest;
struct Node* next;
};
// 图的邻接表表示
struct Graph {
int V;
struct Node** array;
};
// 创建新节点
struct Node* createNode(int dest) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// 创建图
struct Graph* createGraph(int V) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->array = (struct Node**)malloc(V * sizeof(struct Node*));
for (int i = 0; i < V; i++) {
graph->array[i] = NULL;
}
return graph;
}
// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
struct Node* newNode = createNode(dest);
newNode->next = graph->array[src];
graph->array[src] = newNode;
// 无向图需要双向设置
newNode = createNode(src);
newNode->next = graph->array[dest];
graph->array[dest] = newNode;
}
// 打印邻接表
void printGraph(struct Graph* graph) {
for (int i = 0; i < graph->V; i++) {
struct Node* temp = graph->array[i];
printf("顶点 %d 的邻居: ", i);
while (temp) {
printf("%d -> ", temp->dest);
temp = temp->next;
}
printf("NULL\n");
}
}
int main() {
int V = 4;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
printGraph(graph);
return 0;
}
输出:
顶点 0 的邻居: 2 -> 1 -> NULL
顶点 1 的邻居: 2 -> 0 -> NULL
顶点 2 的邻居: 3 -> 1 -> 0 -> NULL
顶点 3 的邻居: 2 -> NULL
备注
邻接表适合表示稀疏图,因为它只存储实际存在的边,节省空间。
实际应用场景
1. 社交网络
在社交网络中,用户是顶点,好友关系是边。通过图可以分析用户之间的关系、推荐好友或发现社区。
2. 路径规划
在地图应用中,地点是顶点,道路是边。通过图算法(如Dijkstra算法)可以找到两点之间的最短路径。
3. 网络拓扑
在计算机网络中,设备是顶点,连接是边。通过图可以分析网络的连通性和性能。
总结
图是一种强大的数据结构,用于表示对象之间的关系。本文介绍了图的基本概念、邻接矩阵和邻接表的表示方法,并展示了实际应用场景。掌握图的基础知识是学习更复杂算法(如深度优先搜索、广度优先搜索、最短路径算法等)的关键。
附加资源与练习
- 练习:尝试实现一个有向图的邻接表表示,并添加权重功能。
- 深入学习:研究图的遍历算法(DFS和BFS)以及最短路径算法(Dijkstra和Floyd-Warshall)。
- 参考书籍:《算法导论》中的图论章节。
警告
在学习图的过程中,务必动手实践代码,理解每种表示方法的优缺点。