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_MAX

void 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]);
    }
}