圖是一種重要的非線性數據結構，廣泛應用于社交網絡、路徑規劃、網絡拓撲等領域。在C語言中，圖的數據處理涉及圖的表示、遍歷、最短路徑、最小生成樹等核心算法。本文將介紹C語言中圖的基本表示方法及常見數據處理技術。

一、圖的表示方法
在C語言中，圖通常有兩種表示方法：鄰接矩陣和鄰接表。

1. 鄰接矩陣
鄰接矩陣使用二維數組表示圖中頂點之間的邊關系。對于具有n個頂點的圖，可以定義一個n×n的矩陣。如果頂點i到頂點j有邊，則矩陣元素a[i][j]為1（無權圖）或邊的權重（有權圖）；否則為0或無窮大。

`c #define MAX_VERTICES 100

#define INF 99999

typedef struct {
int vertices;
int matrix[MAXVERTICES][MAXVERTICES];
} Graph;
`

2. 鄰接表
鄰接表使用鏈表數組表示圖，每個頂點對應一個鏈表，鏈表中存儲與該頂點相鄰的頂點信息。鄰接表適用于稀疏圖，節省存儲空間。

`c typedef struct AdjListNode { int dest; int weight; struct AdjListNode* next; } AdjListNode;

typedef struct {
AdjListNode* heads[MAX_VERTICES];
int vertices;
} GraphList;
`

二、圖的遍歷算法
圖的遍歷是許多圖算法的基礎，主要包括深度優先搜索（DFS）和廣度優先搜索（BFS）。

1. 深度優先搜索（DFS）
DFS采用遞歸或棧實現，沿著圖的深度方向遍歷頂點。

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

2. 廣度優先搜索（BFS）
BFS使用隊列實現，按層次遍歷圖的頂點。

void BFS(Graph* g, int start, int visited[]) {
int queue[MAX_VERTICES], front = 0, rear = 0;
visited[start] = 1;
queue[rear++] = start;
while (front < rear) {
int current = queue[front++];
printf("%d ", current);
for (int i = 0; i < g->vertices; i++) {
if (g->matrix[current][i] && !visited[i]) {
visited[i] = 1;
queue[rear++] = i;
}
}
}
}

三、最短路徑算法
最短路徑算法用于尋找圖中兩個頂點之間的最短路徑，常見算法有Dijkstra算法和Floyd-Warshall算法。

1. Dijkstra算法
Dijkstra算法適用于有權圖（權重非負），使用貪心策略求解單源最短路徑。

void Dijkstra(Graph* g, int src, int dist[]) {
int visited[MAX_VERTICES] = {0};
for (int i = 0; i < g->vertices; i++) {
dist[i] = INF;
}
dist[src] = 0;
for (int count = 0; count < g->vertices - 1; count++) {
int u = -1;
for (int i = 0; i < g->vertices; i++) {
if (!visited[i] && (u == -1 || dist[i] < dist[u])) {
u = i;
}
}
visited[u] = 1;
for (int v = 0; v < g->vertices; v++) {
if (!visited[v] && g->matrix[u][v] && dist[u] + g->matrix[u][v] < dist[v]) {
dist[v] = dist[u] + g->matrix[u][v];
}
}
}
}

四、最小生成樹算法
最小生成樹用于在連通加權圖中找到權值和最小的樹，常見算法有Prim算法和Kruskal算法。

1. Prim算法
Prim算法從任意頂點開始，逐步添加最小權重的邊，直到包含所有頂點。

void Prim(Graph* g, int parent[]) {
int key[MAXVERTICES], visited[MAXVERTICES] = {0};
for (int i = 0; i < g->vertices; i++) {
key[i] = INF;
}
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < g->vertices - 1; count++) {
int u = -1;
for (int i = 0; i < g->vertices; i++) {
if (!visited[i] && (u == -1 || key[i] < key[u])) {
u = i;
}
}
visited[u] = 1;
for (int v = 0; v < g->vertices; v++) {
if (g->matrix[u][v] && !visited[v] && g->matrix[u][v] < key[v]) {
key[v] = g->matrix[u][v];
parent[v] = u;
}
}
}
}

五、數據處理應用實例
圖的數據處理在實際應用中非常廣泛。例如，在社交網絡分析中，可以使用BFS查找用戶之間的最短關系鏈；在交通網絡中，Dijkstra算法可以計算最短行車路線；在通信網絡設計中，Prim算法可用于構建成本最低的網絡連接。

六、
在C語言中處理圖數據需要熟練掌握圖的表示方法及基本算法。鄰接矩陣和鄰接表各有優劣，應根據具體應用場景選擇。遍歷、最短路徑和最小生成樹算法是圖數據處理的核心，理解這些算法的原理和實現對于解決實際問題至關重要。通過合理的數據結構和算法設計，可以高效地處理復雜的圖數據，滿足各類應用需求。

參考文獻
[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
[2] Weiss, M. A. (2013). Data Structures and Algorithm Analysis in C. Pearson.