数据结构图论实战：邻接矩阵与邻接表C语言实现，6种算法完整代码解析

1. 图的存储结构设计与实现

在计算机科学中，图是一种非常重要的非线性数据结构，它由顶点集合和边集合组成。图的存储结构直接影响算法的效率和实现复杂度，邻接矩阵和邻接表是两种最常用的存储方式。

1.1 邻接矩阵实现

邻接矩阵使用二维数组来表示图中顶点之间的连接关系。对于有n个顶点的图，邻接矩阵是一个n×n的方阵。

#define MAX_VERTEX 100  // 最大顶点数
typedef char VertexType; // 顶点数据类型
typedef int EdgeType;    // 边权值类型

typedef struct {
    VertexType vexs[MAX_VERTEX];   // 顶点集合
    EdgeType edges[MAX_VERTEX][MAX_VERTEX]; // 边集合
    int vertexNum, edgeNum;        // 顶点数和边数
    int graphType;                 // 0-无向图 1-有向图
} MGraph;

邻接矩阵的初始化函数如下：

void InitMGraph(MGraph *G, int type) {
    G->vertexNum = 0;
    G->edgeNum = 0;
    G->graphType = type;
    for(int i=0; i<MAX_VERTEX; i++) {
        for(int j=0; j<MAX_VERTEX; j++) {
            if(i == j) 
                G->edges[i][j] = 0;  // 对角线设为0
            else
                G->edges[i][j] = INT_MAX; // 初始化为无穷大
        }
    }
}

邻接矩阵的特点：

• 空间复杂度 ：O(V²)，V为顶点数
• 适用场景 ：稠密图，边数接近顶点数平方
• 优势 ：
  • 快速判断两顶点间是否有边（O(1)）
  • 方便计算顶点的度（无向图）或出度（有向图）

1.2 邻接表实现

邻接表使用数组加链表的方式存储图，数组部分存储顶点信息，链表存储邻接顶点。

typedef struct EdgeNode { // 边表结点
    int adjvex;           // 邻接点索引
    EdgeType weight;      // 边权值
    struct EdgeNode *next; // 指向下一个邻接点
} EdgeNode;

typedef struct VertexNode { // 顶点表结点
    VertexType data;        // 顶点数据
    EdgeNode *firstEdge;    // 边表头指针
    int inDegree;           // 顶点入度（拓扑排序用）
} VertexNode;

typedef struct {
    VertexNode adjList[MAX_VERTEX];
    int vertexNum, edgeNum;
    int graphType;
} ALGraph;

邻接表的初始化函数：

void InitALGraph(ALGraph *G, int type) {
    G->vertexNum = 0;
    G->edgeNum = 0;
    G->graphType = type;
    for(int i=0; i<MAX_VERTEX; i++) {
        G->adjList[i].firstEdge = NULL;
        G->adjList[i].inDegree = 0;
    }
}

邻接表的特点：

• 空间复杂度 ：O(V+E)，V为顶点数，E为边数
• 适用场景 ：稀疏图，边数远小于顶点数平方
• 优势 ：
  • 节省存储空间
  • 方便找到任一顶点的所有邻接点

1.3 存储结构对比

特性	邻接矩阵	邻接表
空间复杂度	O(V²)	O(V+E)
查询边是否存在	O(1)	O(degree(V))
遍历所有邻接点	O(V)	O(degree(V))
添加边	O(1)	O(1)或O(logV)
删除边	O(1)	O(degree(V))
适用场景	稠密图	稀疏图

提示：在实际应用中，应根据图的特点和算法需求选择合适的存储结构。稠密图或需要频繁查询边存在性的场景适合邻接矩阵，而稀疏图或需要频繁遍历邻接点的场景适合邻接表。

2. 图的遍历算法实现

图的遍历是图算法的基础，深度优先搜索(DFS)和广度优先搜索(BFS)是两种最基本的遍历方法。

2.1 深度优先搜索(DFS)

DFS采用递归或栈的方式实现，尽可能深地搜索图的分支。

邻接矩阵DFS实现：

int visited[MAX_VERTEX] = {0}; // 访问标记数组

void DFS_M(MGraph G, int v) {
    visited[v] = 1;
    printf("%c ", G.vexs[v]);
    
    for(int i=0; i<G.vertexNum; i++) {
        if(G.edges[v][i] != 0 && G.edges[v][i] != INT_MAX && !visited[i]) {
            DFS_M(G, i);
        }
    }
}

邻接表DFS实现：

void DFS_AL(ALGraph G, int v) {
    visited[v] = 1;
    printf("%c ", G.adjList[v].data);
    
    EdgeNode *p = G.adjList[v].firstEdge;
    while(p != NULL) {
        if(!visited[p->adjvex]) {
            DFS_AL(G, p->adjvex);
        }
        p = p->next;
    }
}

2.2 广度优先搜索(BFS)

BFS采用队列的方式实现，逐层遍历图的顶点。

邻接矩阵BFS实现：

void BFS_M(MGraph G, int v) {
    int queue[MAX_VERTEX], front=0, rear=0;
    printf("%c ", G.vexs[v]);
    visited[v] = 1;
    queue[rear++] = v;
    
    while(front != rear) {
        int w = queue[front++];
        for(int i=0; i<G.vertexNum; i++) {
            if(G.edges[w][i] != 0 && G.edges[w][i] != INT_MAX && !visited[i]) {
                printf("%c ", G.vexs[i]);
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

邻接表BFS实现：

void BFS_AL(ALGraph G, int v) {
    int queue[MAX_VERTEX], front=0, rear=0;
    printf("%c ", G.adjList[v].data);
    visited[v] = 1;
    queue[rear++] = v;
    
    while(front != rear) {
        int w = queue[front++];
        EdgeNode *p = G.adjList[w].firstEdge;
        while(p != NULL) {
            if(!visited[p->adjvex]) {
                printf("%c ", G.adjList[p->adjvex].data);
                visited[p->adjvex] = 1;
                queue[rear++] = p->adjvex;
            }
            p = p->next;
        }
    }
}

2.3 遍历算法对比

特性	DFS	BFS
数据结构	栈（递归）	队列
空间复杂度	O(h) h为树高	O(w) w为树宽
适用场景	寻找所有解、拓扑排序	最短路径、连通分量
邻接点访问顺序	深度优先	广度优先

注意：对于非连通图，需要检查所有顶点是否被访问过，对未访问顶点再次调用遍历函数。

3. 拓扑排序算法实现

拓扑排序是针对有向无环图(DAG)的线性排序，使得对于图中的每一条有向边(u,v)，u在排序中总是位于v的前面。

3.1 基于邻接表的拓扑排序

int TopologicalSort(ALGraph G) {
    int stack[MAX_VERTEX], top = -1;
    int count = 0; // 输出顶点计数器
    
    // 将入度为0的顶点入栈
    for(int i=0; i<G.vertexNum; i++) {
        if(G.adjList[i].inDegree == 0) {
            stack[++top] = i;
        }
    }
    
    while(top != -1) {
        int v = stack[top--];
        printf("%c ", G.adjList[v].data);
        count++;
        
        // 删除以v为起点的边
        EdgeNode *p = G.adjList[v].firstEdge;
        while(p != NULL) {
            int w = p->adjvex;
            G.adjList[w].inDegree--;
            if(G.adjList[w].inDegree == 0) {
                stack[++top] = w;
            }
            p = p->next;
        }
    }
    
    if(count < G.vertexNum) {
        printf("\n图中存在环，无法完成拓扑排序\n");
        return 0;
    }
    return 1;
}

3.2 拓扑排序的应用场景

1. 任务调度 ：确定任务的执行顺序，保证前置任务先完成
2. 课程选修 ：确定课程的学习顺序，先修课程在前
3. 依赖解析 ：如软件包安装依赖关系
4. 编译顺序 ：源文件编译的顺序依赖

提示：拓扑排序的结果不唯一，一个DAG可能有多个有效的拓扑排序序列。算法的时间复杂度为O(V+E)，其中V是顶点数，E是边数。

4. 最小生成树算法

最小生成树(Minimum Spanning Tree, MST)是在一个带权无向图中找到一棵生成树，使得所有边的权值之和最小。Prim和Kruskal是两种经典算法。

4.1 Prim算法实现

Prim算法从某个顶点开始，逐步扩展生成树，每次选择连接生成树和非生成树顶点中权值最小的边。

void Prim(MGraph G) {
    EdgeType lowcost[MAX_VERTEX]; // 生成树到各顶点的最小权值
    int adjvex[MAX_VERTEX];      // 最小权值对应的顶点
    int min, j, k;
    
    // 初始化，从顶点0开始
    for(int i=1; i<G.vertexNum; i++) {
        lowcost[i] = G.edges[0][i];
        adjvex[i] = 0;
    }
    lowcost[0] = 0; // 表示顶点0已加入生成树
    
    for(int i=1; i<G.vertexNum; i++) {
        min = INT_MAX;
        j = 1; k = 0;
        
        // 找出当前lowcost中的最小值
        while(j < G.vertexNum) {
            if(lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
            j++;
        }
        
        printf("(%c,%c) ", G.vexs[adjvex[k]], G.vexs[k]);
        lowcost[k] = 0; // 标记顶点k已加入生成树
        
        // 更新lowcost数组
        for(j=1; j<G.vertexNum; j++) {
            if(lowcost[j] != 0 && G.edges[k][j] < lowcost[j]) {
                lowcost[j] = G.edges[k][j];
                adjvex[j] = k;
            }
        }
    }
}

4.2 Kruskal算法实现

Kruskal算法按权值从小到大选择边，如果该边不会形成环，则加入生成树。

typedef struct {
    int begin;
    int end;
    EdgeType weight;
} Edge; // 边结构体

int Find(int *parent, int f) {
    while(parent[f] > 0) {
        f = parent[f];
    }
    return f;
}

void Kruskal(MGraph G) {
    Edge edges[MAX_VERTEX*MAX_VERTEX];
    int parent[MAX_VERTEX];
    int k = 0;
    
    // 将边集存入edges数组
    for(int i=0; i<G.vertexNum; i++) {
        for(int j=i+1; j<G.vertexNum; j++) {
            if(G.edges[i][j] != INT_MAX) {
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].weight = G.edges[i][j];
                k++;
            }
        }
    }
    
    // 按权值从小到大排序
    for(int i=0; i<G.edgeNum-1; i++) {
        for(int j=i+1; j<G.edgeNum; j++) {
            if(edges[i].weight > edges[j].weight) {
                Edge temp = edges[i];
                edges[i] = edges[j];
                edges[j] = temp;
            }
        }
    }
    
    for(int i=0; i<G.vertexNum; i++) {
        parent[i] = 0;
    }
    
    for(int i=0; i<G.edgeNum; i++) {
        int n = Find(parent, edges[i].begin);
        int m = Find(parent, edges[i].end);
        
        if(n != m) { // 不构成环
            parent[n] = m;
            printf("(%c,%c) ", G.vexs[edges[i].begin], G.vexs[edges[i].end]);
        }
    }
}

4.3 最小生成树算法对比

特性	Prim算法	Kruskal算法
时间复杂度	O(V²)（邻接矩阵）	O(ElogE)（排序主导）
适用存储结构	邻接矩阵/邻接表	边集数组
适用场景	稠密图	稀疏图
算法思想	顶点扩展	边选择

注意：Prim算法适合边稠密的图，Kruskal算法适合边稀疏的图。在实际应用中，可以使用优先队列(堆)来优化Prim算法，使其时间复杂度降为O(ElogV)。

5. 最短路径算法

最短路径算法用于在带权图中找到两个顶点之间的最短路径，Dijkstra算法是解决单源最短路径问题的经典算法。

5.1 Dijkstra算法实现

Dijkstra算法采用贪心策略，逐步确定从源点到其他各顶点的最短路径。

void Dijkstra(MGraph G, int v0) {
    int dist[MAX_VERTEX];    // 最短路径长度
    int path[MAX_VERTEX];    // 前驱顶点
    int final[MAX_VERTEX] = {0}; // 是否已找到最短路径
    
    // 初始化
    for(int i=0; i<G.vertexNum; i++) {
        dist[i] = G.edges[v0][i];
        path[i] = (G.edges[v0][i] < INT_MAX) ? v0 : -1;
    }
    dist[v0] = 0;
    final[v0] = 1;
    
    for(int i=1; i<G.vertexNum; i++) {
        int min = INT_MAX;
        int k = 0;
        
        // 找出当前dist中的最小值
        for(int j=0; j<G.vertexNum; j++) {
            if(!final[j] && dist[j] < min) {
                min = dist[j];
                k = j;
            }
        }
        final[k] = 1;
        
        // 更新dist和path数组
        for(int j=0; j<G.vertexNum; j++) {
            if(!final[j] && (min + G.edges[k][j] < dist[j])) {
                dist[j] = min + G.edges[k][j];
                path[j] = k;
            }
        }
    }
    
    // 输出最短路径
    for(int i=0; i<G.vertexNum; i++) {
        if(i != v0) {
            printf("\n%c到%c的最短路径长度为：%d\n", 
                  G.vexs[v0], G.vexs[i], dist[i]);
            printf("路径为：%c", G.vexs[i]);
            int j = i;
            while(path[j] != v0) {
                printf("<-%c", G.vexs[path[j]]);
                j = path[j];
            }
            printf("<-%c", G.vexs[v0]);
        }
    }
}

5.2 最短路径算法应用场景

1. 路由选择 ：网络数据包传输路径选择
2. 交通导航 ：地图应用中寻找最短行车路线
3. 任务调度 ：确定关键路径和任务优先级
4. 网络分析 ：社交网络中分析人际关系距离

提示：Dijkstra算法不能处理带有负权边的图。对于包含负权边的图，可以使用Bellman-Ford算法。如果需要计算所有顶点对之间的最短路径，可以使用Floyd算法，其时间复杂度为O(V³)。

6. 算法性能对比与工程实践

6.1 算法时间复杂度对比

算法	邻接矩阵	邻接表
DFS/BFS	O(V²)	O(V+E)
拓扑排序	O(V²)	O(V+E)
Prim	O(V²)	O(ElogV)
Kruskal	O(ElogE)	O(ElogE)
Dijkstra	O(V²)	O(ElogV)

6.2 工程实践建议

1. 存储结构选择 ：

   • 对于稠密图或需要频繁查询边存在性的场景，优先选择邻接矩阵
   • 对于稀疏图或需要频繁遍历邻接点的场景，优先选择邻接表

2. 算法选择 ：

   • 最小生成树：稠密图用Prim，稀疏图用Kruskal
   • 最短路径：单源无负权边用Dijkstra，有负权边用Bellman-Ford，全源最短路径用Floyd

3. 性能优化 ：

   • 使用优先队列(堆)优化Prim和Dijkstra算法
   • 对于大规模图，考虑使用并行算法或分布式计算框架

4. 内存管理 ：

   • 邻接表的边节点使用内存池技术减少内存碎片
   • 对于固定大小的图，可以使用静态数组代替动态分配

5. 代码可读性 ：

   • 将图结构和算法分离，提高代码复用性
   • 使用清晰的命名和注释，特别是对于复杂的图算法

// 示例：优化的邻接表结构设计
typedef struct {
    VertexType data;
    EdgeNode *firstEdge;
    int inDegree;
    // 添加其他必要字段，如距离估计、颜色标记等
    int distance;  // 用于最短路径算法
    int color;     // 用于遍历算法标记
} AdvancedVertexNode;

在实际项目中，图算法的实现往往需要根据具体需求进行调整和优化。例如，在路由算法中，可能需要结合启发式方法；在社交网络分析中，可能需要考虑动态图的处理。理解这些基础算法的原理和实现方式，是解决更复杂图论问题的基础。