图的基本组成与邻接矩阵表示方法

在计算机科学领域，图是一种关键的数据结构，用于描述对象之间的关联关系。它由一组节点（也称顶点）以及连接这些节点的边构成。依据边是否具有方向性，图可划分为有向图和无向图；若边上附带数值信息，则称为带权图。这类结构被广泛应用于社交网络分析、路径规划及推荐系统等场景。

图的核心元素解析

顶点（Vertex）： 图中的基本单位，例如用户、城市等实体均可作为顶点。

边（Edge）： 表示两个顶点之间的连接关系，可以是有向或无向的。

权重（Weight）： 赋予边的一个数值属性，常用来表示距离、成本或相似度等。

邻接矩阵的实现方式

邻接矩阵采用二维数组的形式来表达图中各顶点间的连接状态。对于含有 n 个顶点的图，使用一个 n×n 的矩阵进行存储：

• 如果从顶点 i 到顶点 j 存在一条边，则矩阵中对应位置 $ A[i][j] $ 设置为 1 或具体的权重值；
• 否则该位置为 0。

对于无向图而言，其邻接矩阵呈现对称特性。这种表示法的优势在于能够以 O(1) 时间判断两节点间是否存在边，但空间复杂度为 O(n)，在稀疏图中容易造成内存浪费。

	A	B	C
A	0	1	1
B	1	0	0
C	1	0	0

// Go语言中定义一个简单的邻接矩阵
package main

import "fmt"

func main() {
    // 3x3 邻接矩阵表示无向图 A-B, A-C
    graph := [][]int{
        {0, 1, 1}, // A 连接到 B 和 C
        {1, 0, 0}, // B 只连接到 A
        {1, 0, 0}, // C 只连接到 A
    }

    fmt.Println("Adjacency Matrix:")
    for _, row := range graph {
        fmt.Println(row)
    }
}

graph TD
A --> B
A --> C
B --> A
C --> A

graph

邻接矩阵的设计原理与初始化过程

图的数学定义及其矩阵表达机制

从数学角度看，图是一个二元组 $ G = (V, E) $，其中 $ V $ 是有限的顶点集合，$ E \subseteq V \times V $ 表示边的集合。根据边的方向性，可分为有向图与无向图。

邻接矩阵的结构特点

利用二维数组 $ A $ 来记录顶点之间的连接情况。当图包含 $ n $ 个顶点时，矩阵大小为 $ n \times n $，其元素定义如下：

$$ A[i][j] = \begin{cases} 1, & \text{若存在从 } i \text{ 到 } j \text{ 的边} \\ 0, & \text{否则} \end{cases} $$

• 无向图对应的邻接矩阵关于主对角线对称；
• 有向图则不一定对称；
• 自环（即顶点指向自身）反映在对角线元素上。

type Graph struct {
    vertices int
    matrix   [][]int
}

func NewGraph(n int) *Graph {
    mat := make([][]int, n)
    for i := range mat {
        mat[i] = make([]int, n)
    }
    return &Graph{n, mat}
}

func (g *Graph) AddEdge(u, v int) {
    g.matrix[u][v] = 1 // 设置边存在
}

C语言中邻接矩阵的数据结构设计

在C语言中，通常通过二维数组实现邻接矩阵，适用于表示顶点之间连接关系紧密的稠密图。任意边的访问时间复杂度为 O(1)。

基础结构定义

定义一个图结构体，其中包含顶点数量和二维数组用于存储连接状态。

#define MAX_VERTICES 100

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

上述结构中，adjMatrix[i][j] 表示从顶点 i 到顶点 j 是否存在边。初始状态下所有值设为 0，表示无边；添加边后将相应位置置为 1 或权重值。

adjMatrix[i][j]

i

j

初始化操作流程

• 为图结构动态分配内存，并设置顶点总数；
• 将邻接矩阵所有元素初始化为 0；
• 支持后续通过修改矩阵值来动态添加边。

图的初始化与顶点-边关系建模

构建图的第一步是完成初始化并建立顶点与边之间的逻辑映射。常见的图表示方式包括邻接表和邻接矩阵。

邻接表的实现方式

采用哈希表形式组织无向图结构，AddEdge 方法用于插入有向边，g.vertices[u] 存储从顶点 u 出发可达的所有邻居节点。

type Graph struct {
    vertices map[int][]int
}

func NewGraph() *Graph {
    return &Graph{vertices: make(map[int][]int)}
}

func (g *Graph) AddEdge(u, v int) {
    g.vertices[u] = append(g.vertices[u], v)
}

数据组织策略对比

• 邻接表更节省空间，适合稀疏图；
• 邻接矩阵便于快速查询边的存在性，更适合稠密图；
• 对于加权图，可通过嵌套映射如 map[int]map[int]int 实现权重存储。

有向图与无向图的矩阵构造差异

邻接矩阵是图论中重要的图表示工具，两者在构造上的主要区别体现在矩阵的对称性。

对称性特征分析

无向图的邻接矩阵满足 $ A[i][j] = A[j][i] $，因为边没有方向限制。而有向图中，即使存在从 i 到 j 的边，也不意味着反向边一定存在，因此矩阵通常不对称。

A[i][j] = A[j][i]

i → j

j → i

代码示例展示了两种图的构建方式：无向图中节点 0 与 1、2 相连，导致矩阵对称；而在有向图中，由于边具有方向性，矩阵无需对称。

# 无向图邻接矩阵示例（对称）
adj_undirected = [
    [0, 1, 1],
    [1, 0, 0],
    [1, 0, 0]
]

# 有向图邻接矩阵示例（非对称）
adj_directed = [
    [0, 1, 0],
    [0, 0, 1],
    [1, 0, 0]
]

构建特性对比表

特性	无向图	有向图
矩阵对称性	是	否
边的存储方式	双向记录（互填）	单向记录（仅填起点到终点）

实战应用：C语言实现图的创建与初始化

邻接矩阵法的应用

在C语言中，使用二维数组实现邻接矩阵是图初始化的常见手段，尤其适用于边密集的图结构，且边的访问效率高达 O(1)。

#define MAX_VERTICES 100
typedef struct {
    int vertices;
    int adjMatrix[MAX_VERTICES][MAX_VERTICES];
} Graph;

Graph* createGraph(int n) {
    Graph* g = (Graph*)malloc(sizeof(Graph));
    g->vertices = n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            g->adjMatrix[i][j] = 0;
    return g;
}

函数 createGraph 动态申请图结构内存，并将整个邻接矩阵初始化为 0，表示初始无任何连接。字段 vertices 记录顶点总数，方便后续遍历与扩展操作。

适用场景比较

• 邻接矩阵： 适合顶点数较少但边较多的稠密图；
• 邻接表： 空间利用率高，适用于边稀疏的大规模图。

基于邻接矩阵的图操作实现

插入顶点与添加边的操作机制

在图结构中，新增顶点和添加边是构建关系网络的基础步骤。首先需确保顶点的唯一性，防止重复加入引发数据错误。

顶点插入流程

1. 检查待插入顶点是否已存在于图中；
2. 若不存在，则为其分配必要的存储空间并初始化相关连接信息；
3. 将其注册进全局顶点集合中。

边的添加实现方式

func (g *Graph) AddEdge(src, dst string) {
    if !g.Contains(src) {
        g.AddVertex(src)
    }
    if !g.Contains(dst) {
        g.AddVertex(dst)
    }
    g.adjacencyList[src] = append(g.adjacencyList[src], dst)
}

通过设置邻接矩阵中对应位置的值来完成边的添加。对于无向图，需同时更新 $ A[i][j] $ 和 $ A[j][i] $；而对于有向图，仅需设置 $ A[i][j] $ 即可。

graph[i][j] = 1

上述代码演示了有向图中添加边的核心逻辑：首先确认源顶点与目标顶点均已存在于图中，随后将目标节点加入源节点的邻接列表。该操作的时间复杂度为 O(1)，特别适用于需要频繁进行边增删的动态图结构场景。

3.2 顶点与边的删除策略

在图结构的操作过程中，删除顶点或边时必须谨慎处理关联关系，以避免出现悬空引用或数据不一致的问题。

边的删除实现方式

对于采用邻接表表示的图结构，删除一条边可通过从源顶点的邻接列表中移除对应的目标节点来完成：

// 删除顶点u到v的有向边
func removeEdge(graph map[int][]int, u, v int) {
    for i, neighbor := range graph[u] {
        if neighbor == v {
            graph[u] = append(graph[u][:i], graph[u][i+1:]...)
            break
        }
    }
}

此函数利用切片操作实现边的移除，其时间复杂度为 O(n)，更适合应用于稀疏图环境。

顶点删除的连锁反应处理

当执行顶点删除操作时，需同步清理所有指向该顶点的边连接。通常采取两步法进行处理： - 遍历图中所有其他顶点，逐一删除与其相连的边； - 最后从顶点集合中彻底移除该顶点。 这一策略有效保障了图结构的完整性，防止内存泄漏及后续访问异常的发生。

3.3 实战演练：动态图结构修改的完整代码实现

在图计算系统中，支持运行时动态调整图结构是实现实时数据更新的关键能力。本节通过一个完整的代码示例展示如何安全地在程序执行过程中增删节点和边。

核心接口设计

为确保线程安全与数据一致性，提供统一的API用于图结构的变更操作。

// AddVertex 动态添加顶点
func (g *Graph) AddVertex(id string, attrs map[string]interface{}) {
    g.Lock()
    defer g.Unlock()
    g.vertices[id] = attrs
}

上述方法通过引入互斥锁机制保护共享状态，从而避免并发写入引发的数据竞争问题。

边的动态更新机制实现

系统支持在运行期间建立或断开节点之间的连接关系。

// AddEdge 添加有向边
func (g *Graph) AddEdge(src, dst string) {
    g.Lock()
    defer g.Unlock()
    if _, exists := g.edges[src]; !exists {
        g.edges[src] = make(map[string]bool)
    }
    g.edges[src][dst] = true
}

该实现采用嵌套映射结构存储邻接关系，实现了O(1)时间复杂度的边查找性能，非常适合高频更新的应用场景。

第四章 图的遍历与典型算法应用

4.1 深度优先遍历（DFS）的矩阵实现方式

在使用邻接矩阵表示的图中，深度优先遍历可借助递归或栈结构逐层探索每个顶点的未访问邻居。其中，矩阵的每一行代表当前顶点，各列则反映其与其他顶点的可达性。 算法流程说明： - 初始化一个布尔型访问标记数组

visited[]

，用于记录各节点是否已被访问； - 从指定起始顶点出发，遍历其邻接矩阵行中的每一个元素； - 若发现存在边（即值为1），且对应目标节点尚未被访问，则递归进入该节点继续搜索。 代码实现细节：

void dfs(int matrix[][V], int start, int visited[]) {
    visited[start] = 1;
    printf("%d ", start);
    for (int i = 0; i < V; i++) {
        if (matrix[start][i] == 1 && !visited[i]) {
            dfs(matrix, i, visited);
        }
    }
}

该函数接收三个参数：邻接矩阵

matrix

、起始节点编号

start

以及访问状态数组

visited

。当条件

matrix[start][i]

成立（表示存在边）且

visited[i]

为假（表示未访问）时，递归调用访问节点

i

，确保整个连通分量内的所有节点均被正确遍历。

4.2 广度优先遍历（BFS）中队列机制的应用

广度优先遍历（BFS）依赖队列“先进先出”的特性，实现对图或树结构的层级式访问。具体过程如下：从起始节点开始，将其入队；然后循环执行出队操作，并访问其所有尚未被访问的邻接节点，再将这些邻接点依次入队，从而保证距离起点更近的节点优先被处理。 队列在BFS中的关键作用： 队列维持了节点的访问顺序，确保每一层的所有节点都在下一层之前被完全处理，是实现层级遍历不可或缺的数据结构。

// BFS 遍历图的邻接表表示
func BFS(graph map[int][]int, start int) {
    visited := make(map[int]bool)
    queue := []int{start}
    visited[start] = true

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:] // 出队
        fmt.Println(node)

        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor) // 入队
            }
        }
    }
}

在上述代码中，

queue

模拟了标准的队列行为，

visited

用于防止重复访问。每次从队首取出一个节点后，将其所有未访问的邻接节点添加至队尾，实现按层次向外扩展的效果。

4.3 最短路径问题：Floyd算法原理与编码实现

算法思想解析： Floyd算法用于求解图中所有顶点对之间的最短路径，适用于带权的有向图或无向图。其核心基于动态规划思想——通过枚举中间顶点，逐步优化任意两点间的路径估计值。 算法实现过程：

def floyd_warshall(n, edges):
    # 初始化距离矩阵
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w

    # 动态规划更新最短路径
    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

在代码中，

dist[i][j]

表示从顶点

i

到顶点

j

的当前最短距离。通过三重循环遍历所有可能的中间点

k

，尝试借助该中间点缩短路径长度。整体时间复杂度为

O(n?)

，适合中小规模且边数较多的稠密图场景。

4.4 最小生成树构建：Prim算法详解与实现

Prim算法用于在加权无向图中构造最小生成树（MST）。其基本思路是从某一初始顶点出发，逐步扩展生成树范围，每一步选择连接已选顶点集合与未选顶点集合之间权重最小的边。 算法步骤概括： - 初始化阶段：任选一个顶点作为起点，加入生成树集合； - 循环执行：选取连接已访问与未访问顶点集中权值最小的边； - 更新相关顶点状态，直到所有顶点都被纳入生成树。 Python 示例实现：

import heapq

def prim(graph, start):
    mst = []
    visited = set([start])
    edges = [(weight, start, to) for to, weight in graph[start]]
    heapq.heapify(edges)

    while edges:
        weight, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((frm, to, weight))
            for neighbor, w in graph[to]:
                if neighbor not in visited:
                    heapq.heappush(edges, (w, to, neighbor))
    return mst

该实现借助优先队列维护候选边集合，确保每次都能高效取出权重最小的边。图结构以邻接表形式存储，整体时间复杂度为 O(E log E)，适用于边数较多的稠密图场景。

第五章 性能分析与邻接矩阵适用场景总结

邻接矩阵在稠密图中的优势体现

对于边数接近顶点数平方量级的稠密图，邻接矩阵展现出卓越的查询效率。任意两个顶点间是否存在边均可在 O(1) 时间内判断，因此特别适合边查询频繁的应用场景。

图类型	空间复杂度	边查询时间	适用场景
稠密图	O(V)	O(1)	社交网络全连接分析
稀疏图	O(V)	O(1)	不推荐使用

实际内存占用对比分析： 以包含 10,000 个顶点的图为例，若使用布尔型邻接矩阵，所需内存约为 100MB（计算公式：10 × 10 / 8 / 1024）。若改用 float64 类型存储权重信息，则总内存消耗可达约 800MB。这种高内存开销在嵌入式系统等资源受限环境中往往难以接受。 典型应用场景举例： - 图像处理中像素点之间的邻域连接常采用邻接矩阵建模； - 航班网络若需保存所有城市对之间的直飞信息，适合使用邻接矩阵存储； - 在实时路径规划系统中，预先计算并存储的邻接矩阵可显著加速最短路径查询过程。

代码实现中的优化技巧

为降低空间开销，可采用位压缩技术对邻接矩阵进行优化。以下为 Go 语言中的示例实现：

// 使用 bitset 压缩存储布尔邻接矩阵
type BitMatrix struct {
    data []uint64
    size int
}

func (bm *BitMatrix) Set(i, j int) {
    idx := i*bm.size + j
    bm.data[idx/64] |= 1 << (idx % 64)
}

func (bm *BitMatrix) Get(i, j int) bool {
    idx := i*bm.size + j
    return (bm.data[idx/64] & (1 << (idx % 64))) != 0
}

示例矩阵行表示如下： [顶点A] —— 矩阵行 ——> [1 0 1 1] [顶点B] —— 矩阵行 ——> [0 1 0 1]

每个顶点所关联的所有连接情况，均以行的形式进行表示。

具体而言，每一行数据反映了从对应顶点出发所能到达的其他顶点及其连接状态。

graph

这种表达方式常用于图结构中，便于描述顶点之间的邻接关系，清晰展现网络或图的拓扑构造。