C语言实现图：从基础到实践

简介

在计算机科学中，图是一种用于表示对象之间关系的数据结构。图由节点（vertices）和边（edges）组成，这种结构能够模拟许多现实世界的问题，如社交网络、交通网络、任务调度等。C语言作为一门强大且高效的编程语言，提供了丰富的机制来实现图数据结构。本文将深入探讨如何使用C语言实现图，涵盖基础概念、使用方法、常见实践以及最佳实践，帮助读者掌握这一重要的数据结构及其应用。

目录

1. 图的基础概念
   • 什么是图
   • 图的类型
   • 图的表示方法
2. C语言实现图的使用方法
   • 邻接矩阵实现
   • 邻接表实现
3. 常见实践
   • 图的遍历
     • 深度优先搜索（DFS）
     • 广度优先搜索（BFS）
   • 最短路径算法
     • Dijkstra算法
     • Bellman - Ford算法
4. 最佳实践
   • 内存管理
   • 代码优化
   • 错误处理
5. 小结
6. 参考资料

图的基础概念

什么是图

图是由一组顶点（节点）和连接这些顶点的边组成的数据结构。顶点表示对象，边表示对象之间的关系。例如，在社交网络中，顶点可以表示用户，边可以表示用户之间的好友关系。

图的类型

1. 无向图：边没有方向，即如果存在从顶点A到顶点B的边，那么也存在从顶点B到顶点A的边。
2. 有向图：边有方向，从顶点A到顶点B的边并不意味着存在从顶点B到顶点A的边。
3. 加权图：每条边都有一个权重值，这个值可以表示距离、成本等。

图的表示方法

1. 邻接矩阵：使用一个二维数组来表示图，数组的行和列分别对应顶点。如果顶点i和顶点j之间有边，则adj[i][j]为1（对于无向图，adj[j][i]也为1）；对于加权图，adj[i][j]存储边的权重值，没有边则为0或一个特殊的无穷大值。
2. 邻接表：为每个顶点维护一个链表，链表中存储与该顶点相邻的顶点。对于加权图，链表节点还需要存储边的权重。

C语言实现图的使用方法

邻接矩阵实现

#include <stdio.h>
#include <stdlib.h>

#define V 5 // 顶点数

// 创建邻接矩阵
int** createAdjMatrix() {
    int** adj = (int**)malloc(V * sizeof(int*));
    for (int i = 0; i < V; i++) {
        adj[i] = (int*)malloc(V * sizeof(int));
        for (int j = 0; j < V; j++) {
            adj[i][j] = 0;
        }
    }
    return adj;
}

// 添加边
void addEdge(int** adj, int src, int dest) {
    adj[src][dest] = 1;
    adj[dest][src] = 1; // 对于无向图
}

// 打印邻接矩阵
void printAdjMatrix(int** adj) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            printf("%d ", adj[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int** adj = createAdjMatrix();
    addEdge(adj, 0, 1);
    addEdge(adj, 0, 2);
    addEdge(adj, 1, 2);
    addEdge(adj, 2, 3);
    addEdge(adj, 3, 4);

    printf("邻接矩阵:\n");
    printAdjMatrix(adj);

    // 释放内存
    for (int i = 0; i < V; i++) {
        free(adj[i]);
    }
    free(adj);

    return 0;
}

邻接表实现

#include <stdio.h>
#include <stdlib.h>

// 定义邻接表节点
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// 定义邻接表
typedef struct AdjList {
    AdjListNode* head;
} AdjList;

// 定义图
typedef struct Graph {
    int V;
    AdjList* array;
} Graph;

// 创建邻接表节点
AdjListNode* createAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建图
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->array = (AdjList*)malloc(V * sizeof(AdjList));

    for (int i = 0; i < V; i++) {
        graph->array[i].head = NULL;
    }
    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    AdjListNode* newNode = createAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // 对于无向图，添加反向边
    newNode = createAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// 打印邻接表
void printGraph(Graph* graph) {
    for (int v = 0; v < graph->V; v++) {
        AdjListNode* pCrawl = graph->array[v].head;
        printf("\n 顶点 %d 的邻接表:", v);
        while (pCrawl) {
            printf(" -> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

int main() {
    int V = 5;
    Graph* graph = createGraph(V);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printf("邻接表:\n");
    printGraph(graph);

    // 释放内存
    for (int i = 0; i < graph->V; i++) {
        AdjListNode* pCrawl = graph->array[i].head;
        while (pCrawl) {
            AdjListNode* temp = pCrawl;
            pCrawl = pCrawl->next;
            free(temp);
        }
    }
    free(graph->array);
    free(graph);

    return 0;
}

常见实践

图的遍历

深度优先搜索（DFS）

深度优先搜索从起始顶点开始，沿着一条路径尽可能深地探索，直到无法继续，然后回溯到上一个顶点，继续探索其他路径。

#include <stdio.h>
#include <stdlib.h>

// 定义邻接表节点
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// 定义邻接表
typedef struct AdjList {
    AdjListNode* head;
} AdjList;

// 定义图
typedef struct Graph {
    int V;
    AdjList* array;
} Graph;

// 创建邻接表节点
AdjListNode* createAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建图
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->array = (AdjList*)malloc(V * sizeof(AdjList));

    for (int i = 0; i < V; i++) {
        graph->array[i].head = NULL;
    }
    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    AdjListNode* newNode = createAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // 对于无向图，添加反向边
    newNode = createAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// DFS 辅助函数
void DFSUtil(Graph* graph, int v, int* visited) {
    visited[v] = 1;
    printf("%d ", v);

    AdjListNode* pCrawl = graph->array[v].head;
    while (pCrawl) {
        int adjVertex = pCrawl->dest;
        if (!visited[adjVertex]) {
            DFSUtil(graph, adjVertex, visited);
        }
        pCrawl = pCrawl->next;
    }
}

// DFS 函数
void DFS(Graph* graph, int start) {
    int* visited = (int*)malloc(graph->V * sizeof(int));
    for (int i = 0; i < graph->V; i++) {
        visited[i] = 0;
    }

    DFSUtil(graph, start, visited);

    free(visited);
}

int main() {
    int V = 5;
    Graph* graph = createGraph(V);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printf("从顶点 0 开始的 DFS 遍历:\n");
    DFS(graph, 0);

    return 0;
}

广度优先搜索（BFS）

广度优先搜索从起始顶点开始，逐层地访问其相邻顶点，直到所有顶点都被访问。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 定义邻接表节点
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// 定义邻接表
typedef struct AdjList {
    AdjListNode* head;
} AdjList;

// 定义图
typedef struct Graph {
    int V;
    AdjList* array;
} Graph;

// 创建邻接表节点
AdjListNode* createAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建图
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->array = (AdjList*)malloc(V * sizeof(AdjList));

    for (int i = 0; i < V; i++) {
        graph->array[i].head = NULL;
    }
    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    AdjListNode* newNode = createAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // 对于无向图，添加反向边
    newNode = createAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// BFS 函数
void BFS(Graph* graph, int start) {
    bool* visited = (bool*)malloc(graph->V * sizeof(bool));
    for (int i = 0; i < graph->V; i++) {
        visited[i] = false;
    }

    int* queue = (int*)malloc(graph->V * sizeof(int));
    int front = 0, rear = 0;

    visited[start] = true;
    queue[rear++] = start;

    while (front < rear) {
        int currentVertex = queue[front++];
        printf("%d ", currentVertex);

        AdjListNode* pCrawl = graph->array[currentVertex].head;
        while (pCrawl) {
            int adjVertex = pCrawl->dest;
            if (!visited[adjVertex]) {
                visited[adjVertex] = true;
                queue[rear++] = adjVertex;
            }
            pCrawl = pCrawl->next;
        }
    }

    free(visited);
    free(queue);
}

int main() {
    int V = 5;
    Graph* graph = createGraph(V);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printf("从顶点 0 开始的 BFS 遍历:\n");
    BFS(graph, 0);

    return 0;
}

最短路径算法

Dijkstra算法

Dijkstra算法用于在加权图中找到从一个源顶点到其他所有顶点的最短路径。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define V 5

// 找到距离最小的顶点
int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, minIndex;

    for (int v = 0; v < V; v++) {
        if (!sptSet[v] && dist[v] <= min) {
            min = dist[v];
            minIndex = v;
        }
    }
    return minIndex;
}

// 打印路径
void printPath(int parent[], int j) {
    if (parent[j] == -1) {
        printf("%d ", j);
        return;
    }
    printPath(parent, parent[j]);
    printf("%d ", j);
}

// 打印结果
void printSolution(int dist[], int parent[], int src) {
    printf("顶点\t 距离\t 路径\n");
    for (int i = 0; i < V; i++) {
        printf("%d -> %d\t %d\t\t %d ", src, i, dist[i], src);
        printPath(parent, i);
        printf("\n");
    }
}

// Dijkstra算法
void dijkstra(int graph[V][V], int src) {
    int dist[V];
    int parent[V];
    bool sptSet[V];

    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        parent[i] = -1;
        sptSet[i] = false;
    }

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;

        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u]!= INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                parent[v] = u;
            }
        }
    }

    printSolution(dist, parent, src);
}

int main() {
    int graph[V][V] = {
        {0, 10, 0, 30, 100},
        {10, 0, 50, 0, 0},
        {0, 50, 0, 20, 10},
        {30, 0, 20, 0, 60},
        {100, 0, 10, 60, 0}
    };

    dijkstra(graph, 0);

    return 0;
}

Bellman - Ford算法

Bellman - Ford算法也用于在加权图中找到从一个源顶点到其他所有顶点的最短路径，并且可以处理负权边。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define V 5
#define E 8

// 定义边
typedef struct Edge {
    int src,