图的存储需求

图结构具有复杂的关联特性，任意两个顶点间都可能存在连接关系，因此需要专门的存储机制。常见的图存储方案包括：邻接矩阵、边集数组、邻接表以及链式前向星。本文重点探讨邻接矩阵的实现原理与应用。

邻接矩阵核心原理

邻接矩阵采用二维数组描述顶点间的连接状态，是最直观的图存储方式。其实现分为两个层面：使用一维数组记录顶点信息，借助二维方阵维护邻接关系。

无向图的矩阵表示

对于无向图，邻接矩阵具有严格的数学特性：

• 若顶点 vᵢ 与 vⱼ 相连，则 M[i][j] = M[j][i] = 1
• 主对角线元素 M[i][i] 通常置零，表示无自环
• 矩阵关于主对角线完全对称

顶点度数可直接从矩阵计算：第 i 行（或列）中值为1的元素个数即为顶点 vᵢ 的度。无向图中出度与入度相等。

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector<vector<int>> buildUndirected(int n, const string& labels, const vector<pair<char, char>>& connections)
{
    unordered_map<char, int> idx;
    for (int i = 0; i < n; ++i) idx[labels[i]] = i;
    
    vector<vector<int>> mat(n, vector<int>(n, 0));
    for (auto& e : connections) {
        int u = idx[e.first], v = idx[e.second];
        mat[u][v] = mat[v][u] = 1;
    }
    return mat;
}

void display(const string& labels, const vector<vector<int>>& mat)
{
    cout << "  ";
    for (char c : labels) cout << c << " ";
    cout << "\n";
    for (int i = 0; i < (int)labels.size(); ++i) {
        cout << labels[i] << "|";
        for (int j = 0; j < (int)labels.size(); ++j)
            cout << mat[i][j] << " ";
        cout << "\n";
    }
}

int main()
{
    string nodes = "abcd";
    vector<pair<char, char>> edges = {{'a','b'}, {'b','c'}, {'c','d'}, {'d','a'}};
    auto m = buildUndirected(4, nodes, edges);
    display(nodes, m);
    return 0;
}

有向图的矩阵表示

有向图的邻接矩阵不再保证对称性：

• M[i][j] = 1 表示存在从 vᵢ 指向 vⱼ 的有向边
• 第 i 行元素之和为顶点 vᵢ 的出度
• 第 j 列元素之和为顶点 vⱼ 的入度

vector<vector<int>> buildDirected(int n, const string& labels, const vector<pair<char, char>>& arcs)
{
    unordered_map<char, int> idx;
    for (int i = 0; i < n; ++i) idx[labels[i]] = i;
    
    vector<vector<int>> mat(n, vector<int>(n, 0));
    for (auto& e : arcs) {
        mat[idx[e.first]][idx[e.second]] = 1;
    }
    return mat;
}

带权图的扩展

带权图（网）的邻接矩阵将布尔值替换为权重数值：

• 存在边时存储权值 w
• 无边时存储特殊标记（如 INT_MAX 或 0x3f3f3f3f）
• 对角线元素为0，表示自身距离

#include <climits>

struct WeightedArc {
    char src, dst;
    int w;
};

vector<vector<int>> buildWeighted(int n, const string& labels, const vector<WeightedArc>& arcs)
{
    unordered_map<char, int> idx;
    for (int i = 0; i < n; ++i) idx[labels[i]] = i;
    
    vector<vector<int>> mat(n, vector<int>(n, INT_MAX));
    for (int i = 0; i < n; ++i) mat[i][i] = 0;
    
    for (auto& e : arcs) {
        mat[idx[e.src]][idx[e.dst]] = e.w;
    }
    return mat;
}

最短路径应用：Dijkstra算法

邻接矩阵为经典图算法提供了高效的数据基础。以下展示基于邻接矩阵的Dijkstra实现：

#include <iostream>
#include <algorithm>

const int MAXV = 1005;
const int INF = 0x3f3f3f3f;

int graph[MAXV][MAXV];
int dist[MAXV], pre[MAXV];
bool visited[MAXV];

void dijkstra(int start, int n)
{
    fill(dist, dist + n + 1, INF);
    fill(visited, visited + n + 1, false);
    
    dist[start] = 0;
    for (int i = 1; i <= n; ++i) {
        int u = -1, minD = INF;
        for (int j = 1; j <= n; ++j)
            if (!visited[j] && dist[j] < minD)
                minD = dist[j], u = j;
        
        if (u == -1) break;
        visited[u] = true;
        
        for (int v = 1; v <= n; ++v)
            if (!visited[v] && graph[u][v] != INF && 
                dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                pre[v] = u;
            }
    }
}

特性权衡

邻接矩阵适用于顶点规模可控、边密度较高的场景，如社交网络分析、路由表维护等。对于大规模稀疏图，建议采用邻接表等压缩存储方案。