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