C语言实现图存储（从零开始掌握邻接矩阵核心技术）

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

第一章：掌握邻接矩阵核心技术——C语言实现图的存储

在数据结构领域，图作为一种关键的非线性结构，被广泛应用于社交网络分析、路径规划算法以及任务调度系统等实际场景。采用C语言进行图的存储设计时，邻接矩阵是一种直观且高效的方案，尤其适用于顶点数量不多但边关系较为密集的情形。

邻接矩阵的基本思想

邻接矩阵通过一个二维数组来表达图中各顶点之间的连接状态。若图中共有 n 个顶点，则需定义一个 n×n 的整型数组 matrix，其中每个元素 matrix[i][j] 表示从第 i 个顶点到第 j 个顶点是否存在边。对于无向图而言，该矩阵呈现对称特性；而对于有向图，这种对称性则不一定成立。

n

n×n

adjMatrix

adjMatrix[i][j]

i

j

图结构体的定义与封装

在C语言中，可以使用结构体将图的相关信息整合在一起，便于管理和操作：

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

#define MAX_VERTICES 100

typedef struct {
    int vertices; // 顶点数量
    int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
} Graph;

// 初始化图
void initGraph(Graph* g, int n) {
    g->vertices = n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            g->adjMatrix[i][j] = 0; // 0 表示无边
        }
    }
}

上述代码构建了一个基本的图结构，并通过初始化函数将所有边的状态设为0，表示初始状态下任意两个顶点之间均无连接。

initGraph

添加边的操作实现

为了动态地向图中插入边，通常会编写专门的函数以支持不同类型图的需求：

• 调用 AddEdge(i, j) 可添加一条从顶点 i 到顶点 j 的边。
• 对于无向图，需要同时设置 matrix[i][j] 和 matrix[j][i] 为1，确保对称性。
• 对于有向图，仅需设置 matrix[i][j] 即可，体现方向性。

addEdge(graph, u, v)

u

v

adjMatrix[u][v]

adjMatrix[v][u]

邻接矩阵的优势与局限性分析

优点	缺点
实现逻辑清晰，易于理解与编码	空间复杂度为 O(n)，在顶点较多时占用内存大
判断两顶点间是否有边的时间复杂度为 O(1)，效率高	不适用于边数远少于顶点平方的稀疏图

graph TD A[开始] --> B[初始化邻接矩阵] B --> C[输入顶点数和边数] C --> D[添加边] D --> E[输出邻接矩阵] E --> F[结束]

第二章：深入解析邻接矩阵的原理与结构设计

2.1 图的基本概念及其邻接矩阵表示

图是描述对象之间关联关系的一种数学模型，由一组顶点（Vertex）和连接这些顶点的边（Edge）构成。根据边是否具有方向性，图可分为有向图和无向图两大类。在计算机中，图的存储方式多样，邻接矩阵作为最基础的方法之一，利用二维数组来映射顶点间的连接情况。

邻接矩阵的结构特性

对于包含 n 个顶点的图，其邻接矩阵是一个 n×n 的二维数组 matrix，其中 matrix[i][j] 的取值反映从顶点 i 到顶点 j 是否存在边。在无权图中，一般用1表示存在边，0表示无边；而在带权图中，该位置则存放相应的权重值。

# 无向图的邻接矩阵表示（5个顶点）
n = 5
adj_matrix = [[0] * n for _ in range(n)]

# 添加边 (0,1), (1,2), (2,3)
edges = [(0,1), (1,2), (2,3)]
for u, v in edges:
    adj_matrix[u][v] = 1
    adj_matrix[v][u] = 1  # 无向图对称

以上示例展示了如何构建一个简单的无向图邻接矩阵。由于无向图的边是双向的，因此每条边都会在矩阵中对称出现。这种方式使得查询任意两点是否相连变得非常高效，时间复杂度仅为 O(1)。然而，其空间开销为 O(n)，更适合用于边较密集的图结构。

邻接矩阵的适用性评估

• 优势： 边的存在性查询可在常数时间内完成。
• 劣势： 内存消耗较大，在稀疏图中资源利用率低。
• 推荐场景： 节点数量较少且连接关系密集的图。

2.2 邻接矩阵的数学建模与存储优势

邻接矩阵本质上是对图的一种数学抽象，使用一个 n×n 的方阵 A 来刻画顶点之间的邻接关系。矩阵中的每个元素 A[i][j] 明确指示了从顶点 i 到顶点 j 是否存在一条边。

数学定义与特征分析

在无向图中，由于边不具备方向性，若存在边 (i, j)，则必有 A[i][j] = A[j][i] = 1，因此整个矩阵关于主对角线对称。而在有向图中，边 i → j 并不意味着 j → i 也存在，故矩阵无需满足对称条件。对于加权图，A[i][j] 存储的是具体的权重数值，而非简单的二元标识。

	A	B	C
A		1
B	1		1
C		1

代码实现参考

// 初始化邻接矩阵
func NewGraph(n int) [][]int {
    graph := make([][]int, n)
    for i := range graph {
        graph[i] = make([]int, n)
    }
    return graph
}

// 添加边（无向图）
func AddEdge(graph [][]int, u, v int) {
    graph[u][v] = 1
    graph[v][u] = 1
}

上述 Go 语言示例展示了如何使用二维切片创建邻接矩阵，并通过 AddEdge 函数在无向图中双向赋值，体现出对称性原则。该结构特别适合处理稠密图，能够在 O(1) 时间内快速判断任意两节点之间是否存在连接。

2.3 C语言中二维数组的应用策略

在C语言编程中，二维数组常用于矩阵运算、图像处理或表格数据管理。其底层逻辑为“数组的数组”，即每个行本身也是一个数组，整体在内存中按行优先顺序连续存储。

声明与初始化方法

int matrix[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

该段代码定义了一个 3×3 的整型二维数组。在内存布局上，元素按先行后列的方式依次排列：第一行的三个元素先存放，接着是第二行，依此类推。初始化时可省略第一维长度，编译器会根据初始化列表自动推断行数。

典型应用：矩阵转置操作

• 将原矩阵的行转换为列，常见于线性代数计算中；
• 可通过嵌套循环遍历原始矩阵，并交换行列索引完成转置；
• 需注意目标数组的维度匹配，防止访问越界。

2.4 无向图与有向图在矩阵建模上的差异

在图论中，邻接矩阵是表达图结构的重要工具。无向图与有向图的核心区别体现在邻接矩阵的对称性质上。

对称性特征对比

由于无向图的边没有方向限制，若顶点 i 与 j 相连，则必然有 A[i][j] = A[j][i] = 1，从而保证矩阵对称。而有向图中，边 i → j 的存在并不蕴含反向边的存在，因此其邻接矩阵通常不对称。

构建邻接矩阵的代码示例

import numpy as np

# 有向图邻接矩阵（非对称）
directed_adj = np.array([
    [0, 1, 0],
    [0, 0, 1],
    [1, 0, 0]
])

# 无向图邻接矩阵（对称）
undirected_adj = np.array([
    [0, 1, 1],
    [1, 0, 0],
    [1, 0, 0]
])

在上述代码中：

• directed_adj

  描述了一个三节点构成的有向环，其邻接矩阵表现出明显的非对称性，体现了边的方向约束；

• undirected_adj

  中节点0分别与节点1和2相连，且互为邻居，对应的矩阵呈对称分布，反映出无向图的双向连接特性。

结构差异总结表

图类型	矩阵对称性	边的含义
无向图	是	双向连接
有向图	否	单向关系

2.5 邻接矩阵的初始化核心代码实现

初始化是构建邻接矩阵的第一步，目的是将所有边的状态重置为“未连接”状态（通常用0表示）。这一步骤确保后续添加边的操作基于干净的数据环境进行，避免残留数据干扰结果准确性。

在C语言中，可通过循环或 memset 函数批量清零整个二维数组，提升效率并增强代码可读性。

在图的表示方法中，邻接矩阵作为一种高效的存储结构，尤其适合用于稠密图。它通过一个二维数组来记录顶点之间的连接状态，能够快速判断任意两个顶点之间是否存在边。

邻接矩阵的核心初始化逻辑

创建邻接矩阵时，首先需要确定图中顶点的数量，并将所有边的初始值设为默认状态（例如0或无穷大），以表示无连接或不可达的情况。以下是一个使用C++实现的示例代码：

// 初始化n个顶点的邻接矩阵
int n = 5;
vector<vector<int>> adjMatrix(n, vector<int>(n, 0)); // 默认无边

// 添加边：u到v，权重为w
void addEdge(int u, int v, int w) {
    adjMatrix[u][v] = w;
}

该代码构建了一个5×5的二维向量，初始值全部为0，代表图中各顶点间尚未建立连接。`addEdge`函数用于添加有向边并设置对应的权重，为后续图算法提供支持。

时间与空间复杂度分析

- 空间复杂度：O(V)，其中 V 为顶点数量 - 优势：适用于频繁查询某条边是否存在的场景 - 缺点：在稀疏图中会造成较大的空间浪费

第三章：图的操作接口设计与实现

3.1 添加顶点与边的处理逻辑

构建图的基本操作包括添加顶点和边，这是形成图拓扑结构的前提。在执行插入操作时，必须确保顶点的唯一性，防止重复添加。

顶点添加机制

为了高效地进行顶点查找与去重，通常采用哈希表来存储顶点信息，从而实现 O(1) 的平均时间复杂度。

func (g *Graph) AddVertex(id string) {
    if g.vertices == nil {
        g.vertices = make(map[string]*Vertex)
    }
    if _, exists := g.vertices[id]; !exists {
        g.vertices[id] = &Vertex{ID: id, Edges: make([]*Edge, 0)}
    }
}

在上述代码中，

g.vertices

作为顶点映射表，仅当指定的顶点 ID 尚未存在时才会创建新的顶点对象。

边的建立流程

添加一条边需完成以下步骤： - 验证源顶点和目标顶点均已存在于图中； - 将目标顶点加入源顶点的邻接列表； - 若为无向图，则还需反向添加一条从目标到源的边，保持对称性。

3.2 删除边与权重更新的编程实现

删除边以及动态调整边权是图操作中的关键功能。为保证数据一致性，必须同步维护邻接结构和权重映射关系。

边的删除逻辑

当使用邻接表存储图时，删除边意味着从源节点 u 的邻居集合中移除目标节点 v。

func (g *Graph) RemoveEdge(u, v int) {
    if neighbors, exists := g.AdjList[u]; exists {
        newNeighbors := []int{}
        for _, node := range neighbors {
            if node != v {
                newNeighbors = append(newNeighbors, node)
            }
        }
        g.AdjList[u] = newNeighbors
    }
}

该函数通过对源节点 u 的邻接列表进行遍历，保留所有不等于 v 的元素，从而完成边的逻辑删除。

权重更新机制

对于带权图，需额外使用一个 map 结构来记录每条边的权重值： - 删除边 (u, v) 时，应同时从权重 map 中移除对应的键； - 更新权重时，直接修改 map 中 (u, v) 对应的值即可。

3.3 图的遍历接口与矩阵访问规范

为了提升图算法的通用性和效率，需制定统一的遍历接口和矩阵访问规则，使得不同底层存储方式（如邻接表与邻接矩阵）可以被一致调用。

核心接口设计

遍历操作应支持深度优先搜索（DFS）和广度优先搜索（BFS）两种模式，并通过统一接口对外暴露：

type Graph interface {
    // 获取顶点数量
    Vertices() int
    // 判断两顶点是否存在边
    HasEdge(u, v int) bool
    // 遍历邻居节点
    Neighbors(v int) []int
}

该抽象接口屏蔽了底层实现细节，使上层算法无需关心图的具体存储形式。

邻接矩阵的访问规则

针对基于二维数组的邻接矩阵，应遵循如下访问原则： - 采用行主序方式进行访问，以提高缓存命中率； - 对角线元素可用于表示自环边； - 对于无向图，其邻接矩阵必须是对称的。

操作	时间复杂度	说明
HasEdge(u,v)	O(1)	通过直接索引访问矩阵元素判断边的存在
Neighbors(v)	O(V)	扫描矩阵第 v 行的所有列以获取邻接点

第四章：典型应用场景与算法集成

4.1 基于邻接矩阵的深度优先搜索（DFS）

深度优先搜索是一种系统探索图中所有可达顶点的算法，利用回溯机制深入遍历每个分支。当图以邻接矩阵形式存储时，矩阵的行与列分别对应顶点，元素值表示边的存在与否。

算法核心流程

DFS从起始顶点开始，标记其为已访问，然后递归访问其所有未被访问的邻接顶点。由于邻接矩阵支持 O(1) 的边查询，因此非常适合此类遍历。

void DFS(int graph[][V], int v, bool visited[]) {
    visited[v] = true;
    cout << v << " ";

    for (int i = 0; i < V; ++i) {
        if (graph[v][i] == 1 && !visited[i]) {
            DFS(graph, i, visited);
        }
    }
}

在上述代码中，

graph

表示邻接矩阵，

visited

用于记录每个顶点的访问状态，

V

为总顶点数。程序通过循环检查第

v

行的所有列，寻找与当前顶点相邻且未被访问的节点。

时间与空间复杂度

- 时间复杂度：O(V)，因需扫描整个矩阵 - 空间复杂度：O(V)，主要用于存储访问标记数组和递归调用栈

4.2 基于邻接矩阵的广度优先搜索（BFS）

广度优先搜索按层次扩展，逐层访问与起始点距离相同的节点，常用于求解最短路径问题。使用邻接矩阵可快速判断两节点间是否有边相连。

核心实现代码

#include <queue>
#include <vector>
using namespace std;

void BFS(int start, const vector<vector<int>>& adjMatrix) {
    int n = adjMatrix.size();
    vector<bool> visited(n, false);
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";
        for (int v = 0; v < n; ++v) {
            if (adjMatrix[u][v] == 1 && !visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

在该实现中，

adjMatrix[u][v]

表示节点

u

到

v

之间是否存在边；

visited

数组用于避免重复访问；队列结构确保节点按照层次顺序被处理。

时间复杂度分析

- 邻接矩阵规模为 O(n) - 每个节点和每条边最多被访问一次 - 总体时间复杂度为 O(n)

4.3 Dijkstra最短路径算法的矩阵实现

Dijkstra算法用于解决单源最短路径问题，适用于带权的有向图或无向图。当使用邻接矩阵存储图时，可以直接基于二维数组进行距离更新和顶点选择。

算法主要步骤

1. 初始化源点到其余各顶点的距离，不可达设为无穷大（如9999）； 2. 维护一个集合，记录已确定最短路径的顶点； 3. 每次从未处理顶点中选出距离最小的一个进行扩展； 4. 利用松弛操作更新其邻接顶点的最短路径估计值。

邻接矩阵表示示例

   A  B  C  D
A     5  2  999
B  999 1  3
C  999 999 1
D  999 999 999

int dist[V]; // 存储最短距离
bool visited[V]; // 标记是否已处理
for (int i = 0; i < V; i++) {
    dist[i] = graph[src][i];
}
dist[src] = 0;

for (int i = 0; i < V - 1; i++) {
    int u = minDistance(dist, visited);
    visited[u] = true;
    for (int v = 0; v < V; v++) {
        if (!visited[v] && graph[u][v] && 
            dist[u] + graph[u][v] < dist[v]) {
            dist[v] = dist[u] + graph[u][v];
        }
    }
}

在代码中，`minDistance`函数返回未访问顶点中距离最小者的索引，外层循环执行 V-1 次以确保所有顶点都被处理。`graph[u][v]` 表示边权值，松弛过程据此更新当前最短路径。

4.4 Floyd-Warshall算法在稠密图中的应用

Floyd-Warshall算法采用动态规划思想，计算图中所有顶点对之间的最短路径，特别适合边数接近 V 的稠密图场景。

算法核心思想

通过三重嵌套循环逐步优化任意两点间的路径长度，允许中间经过其他顶点。其时间复杂度为 O(V)，在稠密图中性能优于多次运行Dijkstra算法。

算法实现

def floyd_warshall(graph):
    n = len(graph)
    dist = [row[:] for row in graph]  # 拷贝邻接矩阵
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

该代码通过三重循环实现松弛操作：外层循环遍历所有可能的中间节点 k，内层则对每一对顶点 (i, j) 更新其当前最短路径距离。初始图结构以邻接矩阵形式表示，其中无法直接连通的边权值设为无穷大。

适用场景分析：

• 稠密图：当图中边的数量接近 $V^2$ 时，Floyd-Warshall 算法表现出更高的效率。
• 全源最短路径需求：在需要计算任意两节点之间最短路径的场景下具有显著优势。
• 支持负权重边：只要图中不包含负权环，算法仍可正确运行。

第五章：总结与进阶学习建议

构建持续学习的技术路径

面对快速演进的技术生态，保持竞争力的核心在于建立系统化、可持续的学习机制。建议定期研读官方文档，积极参与开源社区项目，并在本地环境中动手复现关键功能模块。例如，在深入掌握 Go 语言的并发模型时，可以尝试自行实现一个轻量级的任务调度器，从而加深对 goroutine 和 channel 协作机制的理解。

package main

import (
    "fmt"
    "sync"
    "time"
)

func worker(id int, jobs <-chan int, wg *sync.WaitGroup) {
    defer wg.Done()
    for job := range jobs {
        fmt.Printf("Worker %d processing job %d\n", id, job)
        time.Sleep(time.Second)
    }
}

func main() {
    jobs := make(chan int, 100)
    var wg sync.WaitGroup

    // 启动3个工作协程
    for w := 1; w <= 3; w++ {
        wg.Add(1)
        go worker(w, jobs, &wg)
    }

    // 发送5个任务
    for j := 1; j <= 5; j++ {
        jobs <- j
    }
    close(jobs)

    wg.Wait()
}

选择高价值的进阶方向

结合当前行业趋势与技术需求，以下几个领域具备较高的学习回报率：

• 云原生架构：深入学习 Kubernetes 控制器的开发原理及服务网格（如 Istio）的配置实践。
• 可观测性工程：掌握 OpenTelemetry 在微服务架构中的集成方法，实现日志、指标与追踪的统一采集。
• 安全编码实践：熟悉常见安全漏洞的成因与防御手段，如 SQL 注入、XSS 跨站脚本攻击等。
• 性能调优技能：利用 pprof 工具对 Go 程序进行 CPU 与内存使用情况的深度分析，定位性能瓶颈。

通过真实项目提升实战能力

项目类型	推荐平台	技能收益
分布式缓存设计	GitHub 开源项目	掌握一致性哈希算法与故障转移机制的设计与实现
API 网关开发	GitLab 社区贡献	理解中间件链式处理逻辑与限流算法的具体应用

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：从零开始 邻接矩阵 核心技术 C语言 interface