圖（Graph）是一種非常重要的非線性數據結構，由頂點（Vertex）和邊（Edge）組成。在C語言中實現圖結構并進行數據處理，是解決諸多實際問題的關鍵，如社交網絡分析、路徑規劃、網絡拓撲等。
一、 圖的基本概念與表示方法
圖G可以形式化地表示為G=(V, E)，其中V是頂點的有窮非空集合，E是邊的集合。邊表示頂點之間的關系，可以是無向的（無向圖），也可以是有向的（有向圖）。邊可以帶有權值（加權圖），表示距離、成本等。
在C語言中，常用的表示方法有兩種：
- 鄰接矩陣：使用一個二維數組（如
int matrix[MAX<em>V][MAX</em>V]）表示。對于無向圖，矩陣通常對稱；對于加權圖，矩陣元素存儲權值（無邊可用無窮大或特定值表示）。其優點是直觀、訪問任意邊速度快（O(1)）；缺點是空間復雜度高（O(V2)），適合稠密圖。 - 鄰接表：為每個頂點維護一個鏈表，存儲與其相鄰的頂點。通常用結構體數組實現，每個元素包含頂點信息和指向鄰接鏈表的指針。空間復雜度為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;
}`
三、 基于圖的關鍵數據處理算法
圖的數據處理核心在于遍歷和算法應用。
- 圖的遍歷
- 深度優先搜索（DFS）：遞歸或棧實現，沿著路徑深入探索，常用于檢測環、拓撲排序等。
- 廣度優先搜索（BFS）：隊列實現，層層推進，常用于求最短路徑（無權圖）、連通分量等。
- 最短路徑問題
- Dijkstra算法：求解單源最短路徑（邊權非負），使用優先隊列（最小堆）優化可達O((V+E)logV)。
- Floyd-Warshall算法：動態規劃求解所有頂點對之間的最短路徑，時間復雜度O(V3)，代碼簡潔。
- 最小生成樹（MST）
- Prim算法：從任意頂點開始，逐步添加權值最小的邊，適合稠密圖。
- Kruskal算法：按權值從小到大選擇邊，并利用并查集檢測環，適合稀疏圖。
- 拓撲排序
- 針對有向無環圖（DAG），將頂點排成線性序列，使得對每條邊(u,v)，u都出現在v之前。常用DFS或BFS（計算入度）實現。
四、 數據處理應用實例：城市交通路徑查詢
假設用圖表示城市交通網，頂點是交叉口，邊是道路（權值為距離或時間）。數據處理任務可能包括：
- 連通性檢查：使用DFS/BFS判斷兩個區域是否連通。
- 最短路徑規劃：使用Dijkstra算法為用戶提供A地到B地的最快路線。
- 關鍵樞紐分析：通過計算頂點的度（鄰接邊數）或 betweenness centrality（需要更復雜算法）找出交通要道。
五、 與注意事項
在C語言中進行圖的數據處理時，需注意：
- 內存管理：動態分配的內存（如鄰接表節點）要及時釋放，防止內存泄漏。
- 算法選擇：根據圖的特點（大小、稠密性、權值特征）選擇最合適的存儲結構和算法。
- 效率與優化：對于大規模圖，需關注時間與空間復雜度，必要時使用堆、并查集等數據結構優化。
- 數據完整性：在處理過程中，如文件讀取構建圖時，需校驗數據格式，防止無效邊（如不存在的頂點編號）。
圖結構及其算法是C語言數據處理的強大工具。掌握其核心實現與典型應用，能夠高效解決許多復雜的現實世界問題。通過結合具體場景（如社交網絡、路由協議、任務調度）進行實踐，可以深化對圖數據結構的理解與應用能力。
