数据结构-C语言版本（六）图

数据结构中的图：概念、操作与实战

第一部分 图分类及常见形式

图是由顶点(Vertex)和边(Edge)组成的非线性数据结构。以下是图的常见分类：

1. 图的存储表示

邻接矩阵表示法

#define MAX_VERTICES 100typedef struct {int vertices[MAX_VERTICES][MAX_VERTICES];int vertexCount;
} GraphMatrix;

邻接表表示法

typedef struct AdjListNode {int dest;struct AdjListNode* next;
} AdjListNode;typedef struct {AdjListNode* head;
} AdjList;typedef struct {AdjList* array;int vertexCount;
} GraphList;

2. 图的分类

无向图

边没有方向的图

// 使用邻接矩阵表示的无向图
void addUndirectedEdge(GraphMatrix* graph, int src, int dest) {graph->vertices[src][dest] = 1;graph->vertices[dest][src] = 1;
}

有向图

边有方向的图

// 使用邻接表表示的有向图
void addDirectedEdge(GraphList* graph, int src, int dest) {AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));newNode->dest = dest;newNode->next = graph->array[src].head;graph->array[src].head = newNode;
}

加权图

边带有权值的图

typedef struct WeightedNode {int dest;int weight;struct WeightedNode* next;
} WeightedNode;typedef struct {WeightedNode* head;
} WeightedList;typedef struct {WeightedList* array;int vertexCount;
} WeightedGraph;

有向无环图(DAG)

没有环路的有向图

第二部分 图常见操作

1. 图的初始化

// 初始化邻接矩阵图
void initGraphMatrix(GraphMatrix* graph, int vertexCount) {graph->vertexCount = vertexCount;for(int i = 0; i < vertexCount; i++) {for(int j = 0; j < vertexCount; j++) {graph->vertices[i][j] = 0;}}
}// 初始化邻接表图
GraphList* createGraphList(int vertexCount) {GraphList* graph = (GraphList*)malloc(sizeof(GraphList));graph->vertexCount = vertexCount;graph->array = (AdjList*)malloc(vertexCount * sizeof(AdjList));for(int i = 0; i < vertexCount; i++) {graph->array[i].head = NULL;}return graph;
}

2. 图的遍历

深度优先搜索(DFS)

// 邻接矩阵DFS
void DFSMatrix(GraphMatrix* graph, int vertex, int visited[]) {visited[vertex] = 1;printf("%d ", vertex);for(int i = 0; i < graph->vertexCount; i++) {if(graph->vertices[vertex][i] && !visited[i]) {DFSMatrix(graph, i, visited);}}
}// 邻接表DFS
void DFSList(GraphList* graph, int vertex, int visited[]) {visited[vertex] = 1;printf("%d ", vertex);AdjListNode* node = graph->array[vertex].head;while(node) {if(!visited[node->dest]) {DFSList(graph, node->dest, visited);}node = node->next;}
}

广度优先搜索(BFS)

// 邻接矩阵BFS
void BFSMatrix(GraphMatrix* graph, int start) {int visited[MAX_VERTICES] = {0};int queue[MAX_VERTICES];int front = 0, rear = 0;visited[start] = 1;queue[rear++] = start;while(front < rear) {int vertex = queue[front++];printf("%d ", vertex);for(int i = 0; i < graph->vertexCount; i++) {if(graph->vertices[vertex][i] && !visited[i]) {visited[i] = 1;queue[rear++] = i;}}}
}

3. 拓扑排序（针对DAG）

// 邻接表拓扑排序
void topologicalSort(GraphList* graph) {int inDegree[MAX_VERTICES] = {0};int queue[MAX_VERTICES];int front = 0, rear = 0;int counter = 0;// 计算入度for(int i = 0; i < graph->vertexCount; i++) {AdjListNode* node = graph->array[i].head;while(node) {inDegree[node->dest]++;node = node->next;}}// 入度为0的顶点入��for(int i = 0; i < graph->vertexCount; i++) {if(inDegree[i] == 0) {queue[rear++] = i;}}while(front < rear) {int vertex = queue[front++];printf("%d ", vertex);counter++;// 减少相邻顶点的入度AdjListNode* node = graph->array[vertex].head;while(node) {if(--inDegree[node->dest] == 0) {queue[rear++] = node->dest;}node = node->next;}}if(counter != graph->vertexCount) {printf("\n图中存在环!\n");}
}

4. 最短路径算法

Dijkstra算法（加权图单源最短路径）

// 邻接表Dijkstra算法
void dijkstra(WeightedGraph* graph, int src) {int dist[MAX_VERTICES];int visited[MAX_VERTICES] = {0};for(int i = 0; i < graph->vertexCount; i++) {dist[i] = INT_MAX;}dist[src] = 0;for(int count = 0; count < graph->vertexCount-1; count++) {int u = -1;for(int i = 0; i < graph->vertexCount; i++) {if(!visited[i] && (u == -1 || dist[i] < dist[u])) {u = i;}}if(dist[u] == INT_MAX) break;visited[u] = 1;WeightedNode* node = graph->array[u].head;while(node) {int v = node->dest;if(!visited[v] && dist[u] + node->weight < dist[v]) {dist[v] = dist[u] + node->weight;}node = node->next;}}// 打印最短路径printf("顶点\t距离源点的距离\n");for(int i = 0; i < graph->vertexCount; i++) {printf("%d\t%d\n", i, dist[i]);}
}

5. 最小生成树算法

Prim算法

// 邻接矩阵Prim算法
void primMST(GraphMatrix* graph) {int parent[MAX_VERTICES];int key[MAX_VERTICES];int mstSet[MAX_VERTICES] = {0};for(int i = 0; i < graph->vertexCount; i++) {key[i] = INT_MAX;}key[0] = 0;parent[0] = -1;for(int count = 0; count < graph->vertexCount-1; count++) {int u = -1;for(int i = 0; i < graph->vertexCount; i++) {if(!mstSet[i] && (u == -1 || key[i] < key[u])) {u = i;}}mstSet[u] = 1;for(int v = 0; v < graph->vertexCount; v++) {if(graph->vertices[u][v] && !mstSet[v] && graph->vertices[u][v] < key[v]) {parent[v] = u;key[v] = graph->vertices[u][v];}}}// 打印最小生成树printf("边\t权值\n");for(int i = 1; i < graph->vertexCount; i++) {printf("%d - %d\t%d\n", parent[i], i, graph->vertices[i][parent[i]]);}
}

第三部分 图编程题例子

1. 克隆图

typedef struct Node {int val;int numNeighbors;struct Node** neighbors;
} Node;Node* cloneGraph(Node* node) {if(node == NULL) return NULL;Node* clones[101] = {NULL}; // 假设节点值在0-100之间Node* queue[101];int front = 0, rear = 0;// 克隆第一个节点Node* clone = (Node*)malloc(sizeof(Node));clone->val = node->val;clone->numNeighbors = node->numNeighbors;clone->neighbors = (Node**)malloc(clone->numNeighbors * sizeof(Node*));clones[node->val] = clone;queue[rear++] = node;while(front < rear) {Node* current = queue[front++];for(int i = 0; i < current->numNeighbors; i++) {Node* neighbor = current->neighbors[i];if(clones[neighbor->val] == NULL) {// 克隆邻居节点Node* neighborClone = (Node*)malloc(sizeof(Node));neighborClone->val = neighbor->val;neighborClone->numNeighbors = neighbor->numNeighbors;neighborClone->neighbors = (Node**)malloc(neighborClone->numNeighbors * sizeof(Node*));clones[neighbor->val] = neighborClone;queue[rear++] = neighbor;}// 添加邻居关系clones[current->val]->neighbors[i] = clones[neighbor->val];}}return clone;
}

2. 课程表（拓扑排序应用）

int canFinish(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize) {int inDegree[numCourses];memset(inDegree, 0, sizeof(inDegree));// 构建邻接表并计算入度AdjList* graph = createGraphList(numCourses);for(int i = 0; i < prerequisitesSize; i++) {int dest = prerequisites[i][0];int src = prerequisites[i][1];addDirectedEdge(graph, src, dest);inDegree[dest]++;}// 拓扑排序int queue[numCourses];int front = 0, rear = 0;int count = 0;for(int i = 0; i < numCourses; i++) {if(inDegree[i] == 0) {queue[rear++] = i;}}while(front < rear) {int course = queue[front++];count++;AdjListNode* node = graph->array[course].head;while(node) {if(--inDegree[node->dest] == 0) {queue[rear++] = node->dest;}node = node->next;}}return count == numCourses;
}

3. 岛屿数量（DFS/BFS应用）

void dfs(char** grid, int gridSize, int* gridColSize, int i, int j) {if(i < 0 || i >= gridSize || j < 0 || j >= gridColSize[0] || grid[i][j] != '1') {return;}grid[i][j] = '0'; // 标记为已访问dfs(grid, gridSize, gridColSize, i+1, j);dfs(grid, gridSize, gridColSize, i-1, j);dfs(grid, gridSize, gridColSize, i, j+1);dfs(grid, gridSize, gridColSize, i, j-1);
}int numIslands(char** grid, int gridSize, int* gridColSize) {int count = 0;for(int i = 0; i < gridSize; i++) {for(int j = 0; j < gridColSize[0]; j++) {if(grid[i][j] == '1') {dfs(grid, gridSize, gridColSize, i, j);count++;}}}return count;
}

4. 网络延迟时间（Dijkstra算法应用）

int networkDelayTime(int** times, int timesSize, int* timesColSize, int n, int k) {// 构建邻接表WeightedGraph* graph = (WeightedGraph*)malloc(sizeof(WeightedGraph));graph->vertexCount = n;graph->array = (WeightedList*)malloc(n * sizeof(WeightedList));for(int i = 0; i < n; i++) {graph->array[i].head = NULL;}for(int i = 0; i < timesSize; i++) {int u = times[i][0] - 1;int v = times[i][1] - 1;int w = times[i][2];WeightedNode* node = (WeightedNode*)malloc(sizeof(WeightedNode));node->dest = v;node->weight = w;node->next = graph->array[u].head;graph->array[u].head = node;}// Dijkstra算法int dist[n];for(int i = 0; i < n; i++) {dist[i] = INT_MAX;}dist[k-1] = 0;int visited[n];memset(visited, 0, sizeof(visited));for(int count = 0; count < n; count++) {int u = -1;for(int i = 0; i < n; i++) {if(!visited[i] && (u == -1 || dist[i] < dist[u])) {u = i;}}if(u == -1 || dist[u] == INT_MAX) break;visited[u] = 1;WeightedNode* node = graph->array[u].head;while(node) {int v = node->dest;if(!visited[v] && dist[u] + node->weight < dist[v]) {dist[v] = dist[u] + node->weight;}node = node->next;}}// 找出最大距离int maxTime = 0;for(int i = 0; i < n; i++) {if(dist[i] == INT_MAX) return -1;if(dist[i] > maxTime) maxTime = dist[i];}return maxTime;
}

5. 连接所有点的最小费用（Prim算法应用）

int minCostConnectPoints(int** points, int pointsSize, int* pointsColSize) {if(pointsSize <= 1) return 0;int n = pointsSize;int graph[n][n];// 构建完全图的邻接矩阵for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {graph[i][j] = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);}}// Prim算法int key[n];int mstSet[n];for(int i = 0; i < n; i++) {key[i] = INT_MAX;mstSet[i] = 0;}key[0] = 0;int totalCost = 0;for(int count = 0; count < n; count++) {int u = -1;for(int i = 0; i < n; i++) {if(!mstSet[i] && (u == -1 || key[i] < key[u])) {u = i;}}mstSet[u] = 1;totalCost += key[u];for(int v = 0; v < n; v++) {if(!mstSet[v] && graph[u][v] < key[v]) {key[v] = graph[u][v];}}}return totalCost;
}

6. 单词接龙（BFS应用）

int ladderLength(char * beginWord, char * endWord, char ** wordList, int wordListSize) {// 将单词列表转换为哈希集合以便快速查找char* wordSet[wordListSize];int wordSetSize = 0;int endWordExists = 0;for(int i = 0; i < wordListSize; i++) {if(strcmp(wordList[i], endWord) == 0) {endWordExists = 1;}wordSet[wordSetSize++] = wordList[i];}if(!endWordExists) return 0;// BFS队列char* queue[wordListSize + 1];int front = 0, rear = 0;queue[rear++] = beginWord;int level = 1;while(front < rear) {int size = rear - front;for(int i = 0; i < size; i++) {char* word = queue[front++];if(strcmp(word, endWord) == 0) {return level;}// 生成所有可能的变换for(int j = 0; j < strlen(word); j++) {char original = word[j];for(char c = 'a'; c <= 'z'; c++) {if(c == original) continue;word[j] = c;// 检查是否在单词列表中for(int k = 0; k < wordSetSize; k++) {if(wordSet[k] != NULL && strcmp(word, wordSet[k]) == 0) {queue[rear++] = wordSet[k];wordSet[k] = NULL; // 标记为已访问break;}}}word[j] = original;}}level++;}return 0;
}

图是计算机科学中最强大和灵活的数据结构之一，广泛应用于社交网络、路由算法、推荐系统、路径规划等领域。掌握图的表示方法和基本算法，对于解决复杂问题至关重要。通过练习这些典型题目，可以深入理解图结构的特性和应用场景。