C语言图结构学习笔记

1. 图的定义

图（Graph）是一种数据结构，由顶点（Vertex）和边（Edge）组成，用于表示对象及其相互关系。图可以是有向图（Directed Graph）或无向图（Undirected Graph）。

1.1 有向图

有向图的边有方向，表示顶点之间的单向关系。

A → B

1.2 无向图

无向图的边没有方向，表示顶点之间的双向关系。

A — B

2. 图的表示方法

2.1 邻接矩阵

邻接矩阵是一种二维数组，用于表示顶点之间的连接关系。

#define MAX_VERTICES 100
int adjMatrix[MAX_VERTICES][MAX_VERTICES];

2.2 邻接表

邻接表是一种链表数组，每个链表表示一个顶点及其相邻顶点。

#include <stdio.h>
#include <stdlib.h>typedef struct AdjNode {int vertex;struct AdjNode* next;
} AdjNode;typedef struct {AdjNode* head;
} AdjList;typedef struct {int numVertices;AdjList* list;
} Graph;Graph* createGraph(int vertices) {Graph* graph = (Graph*)malloc(sizeof(Graph));graph->numVertices = vertices;graph->list = (AdjList*)malloc(vertices * sizeof(AdjList));for (int i = 0; i < vertices; i++) {graph->list[i].head = NULL;}return graph;
}void addEdge(Graph* graph, int src, int dest) {AdjNode* newNode = (AdjNode*)malloc(sizeof(AdjNode));newNode->vertex = dest;newNode->next = graph->list[src].head;graph->list[src].head = newNode;newNode = (AdjNode*)malloc(sizeof(AdjNode));newNode->vertex = src;newNode->next = graph->list[dest].head;graph->list[dest].head = newNode;
}

3. 图的遍历

3.1 深度优先搜索（DFS）

深度优先搜索是一种图遍历算法，从一个顶点出发，沿着边尽可能深入地访问顶点，直到不能再深入为止，然后回溯到上一个顶点继续访问。

void DFS(Graph* graph, int vertex, int* visited) {visited[vertex] = 1;printf("%d ", vertex);AdjNode* adjList = graph->list[vertex].head;while (adjList != NULL) {int connectedVertex = adjList->vertex;if (!visited[connectedVertex]) {DFS(graph, connectedVertex, visited);}adjList = adjList->next;}
}

3.2 广度优先搜索（BFS）

广度优先搜索是一种图遍历算法，从一个顶点出发，先访问所有相邻顶点，然后再访问这些相邻顶点的相邻顶点，依次类推。

#include <stdbool.h>
#include <limits.h>void BFS(Graph* graph, int startVertex) {int visited[MAX_VERTICES];for (int i = 0; i < graph->numVertices; i++) {visited[i] = 0;}int queue[MAX_VERTICES];int front = 0, rear = 0;visited[startVertex] = 1;queue[rear++] = startVertex;while (front < rear) {int currentVertex = queue[front++];printf("%d ", currentVertex);AdjNode* adjList = graph->list[currentVertex].head;while (adjList != NULL) {int connectedVertex = adjList->vertex;if (!visited[connectedVertex]) {visited[connectedVertex] = 1;queue[rear++] = connectedVertex;}adjList = adjList->next;}}
}

4. 最短路径算法

4.1 Dijkstra算法

Dijkstra算法用于计算从单个源顶点到所有其他顶点的最短路径。

#include <stdio.h>#define INF INT_MAXvoid dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int n, int startVertex) {int distance[MAX_VERTICES], visited[MAX_VERTICES];for (int i = 0; i < n; i++) {distance[i] = INF;visited[i] = 0;}distance[startVertex] = 0;for (int i = 0; i < n - 1; i++) {int minDistance = INF, minIndex;for (int j = 0; j < n; j++) {if (!visited[j] && distance[j] <= minDistance) {minDistance = distance[j];minIndex = j;}}visited[minIndex] = 1;for (int j = 0; j < n; j++) {if (!visited[j] && graph[minIndex][j] && distance[minIndex] != INF && distance[minIndex] + graph[minIndex][j] < distance[j]) {distance[j] = distance[minIndex] + graph[minIndex][j];}}}for (int i = 0; i < n; i++) {printf("Distance from %d to %d: %d\n", startVertex, i, distance[i]);}
}

5. 最小生成树算法

5.1 Prim算法

Prim算法用于找到一个加权无向图的最小生成树。

void prim(int graph[MAX_VERTICES][MAX_VERTICES], int n) {int parent[MAX_VERTICES], key[MAX_VERTICES], mstSet[MAX_VERTICES];for (int i = 0; i < n; i++) {key[i] = INF;mstSet[i] = 0;}key[0] = 0;parent[0] = -1;for (int count = 0; count < n - 1; count++) {int minKey = INF, minIndex;for (int v = 0; v < n; v++) {if (!mstSet[v] && key[v] < minKey) {minKey = key[v];minIndex = v;}}mstSet[minIndex] = 1;for (int v = 0; v < n; v++) {if (graph[minIndex][v] && !mstSet[v] && graph[minIndex][v] < key[v]) {parent[v] = minIndex;key[v] = graph[minIndex][v];}}}for (int i = 1; i < n; i++) {printf("Edge: %d - %d, Weight: %d\n", parent[i], i, graph[i][parent[i]]);}
}

5.2 Kruskal算法

Kruskal算法用于找到一个加权无向图的最小生成树。

typedef struct {int u, v, weight;
} Edge;int find(int parent[], int i) {if (parent[i] == i) {return i;}return find(parent, parent[i]);
}void unionSets(int parent[], int rank[], int x, int y) {int xroot = find(parent, x);int yroot = find(parent, y);if (rank[xroot] < rank[yroot]) {parent[xroot] = yroot;} else if (rank[xroot] > rank[yroot]) {parent[yroot] = xroot;} else {parent[yroot] = xroot;rank[xroot]++;}
}void kruskal(Edge edges[], int n, int e) {int parent[MAX_VERTICES], rank[MAX_VERTICES];for (int i = 0; i < n; i++) {parent[i] = i;rank[i] = 0;}qsort(edges, e, sizeof(edges[0]), compare);int result[MAX_VERTICES][2], resultIndex = 0;for (int i = 0; i < e; i++) {int u = edges[i].u;int v = edges[i].v;int setU = find(parent, u);int setV = find(parent, v);if (setU != setV) {result[resultIndex][0] = u;result[resultIndex][1] = v;resultIndex++;unionSets(parent, rank, setU, setV);}}for (int i = 0; i < resultIndex; i++) {printf("Edge: %d - %d\n", result[i][0], result[i][1]);}
}