C语言数据结构图及其数据处理应用详解产品大全北京金博智慧教育科技有限公司深圳分公司

图（Graph）是一种非常重要的非线性数据结构，由顶点（Vertex）和边（Edge）组成。在C语言中实现图结构并进行数据处理，是解决诸多实际问题的关键，如社交网络分析、路径规划、网络拓扑等。

一、图的基本概念与表示方法

图G可以形式化地表示为G=(V, E)，其中V是顶点的有穷非空集合，E是边的集合。边表示顶点之间的关系，可以是无向的（无向图），也可以是有向的（有向图）。边可以带有权值（加权图），表示距离、成本等。

在C语言中，常用的表示方法有两种：

邻接矩阵：使用一个二维数组（如int matrix[MAX<em>V][MAX</em>V]）表示。对于无向图，矩阵通常对称；对于加权图，矩阵元素存储权值（无边可用无穷大或特定值表示）。其优点是直观、访问任意边速度快（O(1)）；缺点是空间复杂度高（O(V²)），适合稠密图。
邻接表：为每个顶点维护一个链表，存储与其相邻的顶点。通常用结构体数组实现，每个元素包含顶点信息和指向邻接链表的指针。空间复杂度为O(V+E)，适合稀疏图，但查询某条边是否存在效率较低（O(度)）。

二、 C语言图的存储结构实现示例

以下是一个使用邻接表表示无向加权图的简化代码框架：

`c #include

#include

#define MAX_V 100

// 邻接表节点结构
typedef struct AdjListNode {
int dest; // 目标顶点编号
int weight; // 边权值
struct AdjListNode* next;
} AdjListNode;

// 邻接表结构
typedef struct AdjList {
AdjListNode* head; // 指向链表头
} AdjList;

// 图结构
typedef struct Graph {
int numVertices; // 顶点数
AdjList* array; // 邻接表数组
} Graph;

// 创建新节点
AdjListNode createNode(int dest, int weight) {
AdjListNode newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
newNode->dest = dest;
newNode->weight = weight;
newNode->next = NULL;
return newNode;
}

// 创建图
Graph createGraph(int vertices) {
Graph graph = (Graph)malloc(sizeof(Graph));
graph->numVertices = vertices;
graph->array = (AdjList)malloc(vertices * sizeof(AdjList));
for (int i = 0; i < vertices; ++i)
graph->array[i].head = NULL;
return graph;
}

// 添加边（无向图）
void addEdge(Graph graph, int src, int dest, int weight) {
// 从src到dest
AdjListNode newNode = createNode(dest, weight);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
// 从dest到src
newNode = createNode(src, weight);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
`