图（Graph）作为一种非线性数据结构，在计算机科学中用于表示实体间的复杂关系，广泛应用于社交网络、路径规划、网络拓扑等领域。在C语言中实现图的数据处理，关键在于选择合适的存储结构并实现高效的操作算法。

一、图的存储结构

1. 邻接矩阵
邻接矩阵使用二维数组存储图中顶点间的连接关系。对于包含n个顶点的图，定义一个n×n的矩阵adjMatrix，若顶点i到j存在边，则adjMatrix[i][j]为1（或边的权值），否则为0（或无穷大）。
优点：实现简单，判断顶点间连接关系的时间复杂度为O(1)。
缺点：空间复杂度为O(n²)，适合稠密图。

2. 邻接表
邻接表为每个顶点建立一个链表，存储与其相邻的顶点信息。通常使用结构体数组，每个元素包含顶点数据和指向邻接链表的指针。
优点：空间复杂度为O(n+e)，适合稀疏图。
缺点：判断两顶点是否相邻需要遍历链表，时间复杂度较高。

二、图的数据处理基本操作

1. 图的创建与初始化
根据选择的存储结构，动态分配内存并初始化。对于邻接矩阵，需初始化所有元素为0；对于邻接表，需初始化所有链表头指针为空。

1. 顶点与边的操作

• 添加顶点：在顶点数组中添加新元素，并更新顶点计数。

• 添加边：根据存储结构，在矩阵或链表中记录连接关系。对于无向图，需对称处理。

• 删除边：将对应矩阵位置置0，或从链表中删除节点。

• 查询邻接顶点：遍历矩阵行或链表，输出所有相邻顶点。

1. 图的遍历算法

• 深度优先搜索（DFS）：使用递归或栈实现，沿着路径深入探索，直到回溯。适用于连通性检测、拓扑排序等。

• 广度优先搜索（BFS）：使用队列实现，按层次遍历顶点。适用于最短路径（无权图）、社交网络好友推荐等。

1. 常用数据处理算法

• 最小生成树：Prim算法和Kruskal算法，用于网络设计、电路布线等场景。

• 最短路径：Dijkstra算法（单源、非负权）和Floyd算法（多源），应用于导航系统、路由协议。

• 拓扑排序：针对有向无环图（DAG），用于任务调度、课程安排。

三、C语言实现示例（邻接矩阵）

以下为简化代码框架：
`c
#include

#include

#define MAX_VERTICES 100

typedef struct {
int adjMatrix[MAXVERTICES][MAXVERTICES];
int vertexCount;
int edgeCount;
} Graph;

void initGraph(Graph *g, int n) {
g->vertexCount = n;
g->edgeCount = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
g->adjMatrix[i][j] = 0;
}

void addEdge(Graph *g, int u, int v) {
if (u >= 0 && u < g->vertexCount && v >= 0 && v < g->vertexCount) {
g->adjMatrix[u][v] = 1;
g->adjMatrix[v][u] = 1; // 无向图需对称
g->edgeCount++;
}
}

void DFS(Graph *g, int v, int visited[]) {
visited[v] = 1;
printf("%d ", v);
for (int i = 0; i < g->vertexCount; i++) {
if (g->adjMatrix[v][i] && !visited[i]) {
DFS(g, i, visited);
}
}
}
`

四、数据处理注意事项

1. 内存管理：动态分配内存时需及时释放，防止内存泄漏。
2. 效率优化：根据图的特点选择存储结构，稠密图用矩阵，稀疏图用邻接表。
3. 算法选择：针对具体问题（如最短路径、连通分量）选用合适算法。
4. 扩展性：可结合文件操作实现图的持久化存储，或通过参数化支持带权图。

在C语言中处理图数据需要扎实掌握存储结构特性与经典算法原理，通过模块化编程实现创建、遍历、查询等核心功能，为复杂应用奠定基础。