1. 什么是邻接矩阵？

邻接矩阵是图的一种最基础的存储表示方法。它使用一个二维数组（即矩阵）来表示图中各个顶点之间的邻接关系。

对于一个有 n 个顶点的图，其邻接矩阵是一个 n x n 的方阵，我们通常称之为 A。

2. 矩阵元素的定义

矩阵中每个元素 A[i][j] 的值，表示顶点 i 与顶点 j 之间的关系。这个关系的具体含义根据图的类型有所不同：

对于无向图

1. A[i][j] = 1：表示顶点 i 和顶点 j 之间有一条边相连。

2. A[i][j] = 0：表示顶点 i 和顶点 j 之间没有边相连。

重要特性：无向图的邻接矩阵是一个对称矩阵，即 A[i][j] = A[j][i]。因为边 (i, j) 和边 (j, i) 是等同的。

对于有向图

1. A[i][j] = 1：表示存在一条从顶点 i 指向顶点 j 的弧（有向边）。

2. A[i][j] = 0：表示没有从顶点 i 指向顶点 j 的弧。

重要特性：有向图的邻接矩阵不一定对称。A[i][j] = 1 并不保证 A[j][i] = 1。

对于带权图（网络）

1. A[i][j] = w：表示顶点 i 和顶点 j 之间的边的权重为 w（如果存在边）。

2. A[i][j] = 0 或 ∞：表示顶点 i 和顶点 j 之间没有边。通常，我们用一个很大的数（如 ∞）或一个特殊值（如 0，但这可能与零权边冲突）来表示不存在的边，具体取决于算法设计。更常见的做法是：对角线上为0（自己到自己的距离为0），不存在的边用 ∞ 表示。

3. 具体示例

示例1：无向图

假设我们有如下无向图，包含4个顶点 (V0, V1, V2, V3)：

(V0) —— (V1)
 |  \     |
 |   \    |
 |    \   |
(V2) —— (V3)

其邻接矩阵为：

观察：

• 矩阵沿主对角线对称。

• 主对角线上的元素都是0，因为我们通常不考虑顶点自身到自身的边（自环）。

示例2：有向图

假设我们有如下有向图：

(V0) ———> (V1)
  ^        |
  |        |
  |        v
(V3) <——— (V2)

其邻接矩阵为：

观察：

• 矩阵不对称。例如，A[0][1]=1（V0->V1），但 A[1][0]=0（V1->V0不存在）。

4. 邻接矩阵的性质与特点

优点

1. 直观易懂：结构简单，易于理解和实现。

2. 快速判断邻接关系：可以在 O(1) 的时间复杂度内判断任意两个顶点 i 和 j 之间是否存在边，只需检查 A[i][j] 的值即可。

3. 便于计算：很多基于矩阵运算的图算法（如通过计算矩阵的幂来求路径数量）非常方便。

4. 适合稠密图：当图的边数接近顶点数的平方时（即稠密图），空间利用率高。

缺点

1. 空间复杂度高：空间复杂度为 O(n²)，其中 n 是顶点数。对于一个有1000个顶点的稀疏图（边数很少），也需要一个100万元素的矩阵，其中大部分是0，造成空间浪费。

2. 添加/删除顶点效率低：添加或删除一个顶点需要改变整个矩阵的大小，操作代价高。

3. 遍历邻接点效率低：要找出一个顶点的所有邻接点，需要扫描对应的一整行，时间复杂度为 O(n)。对于稀疏图，这比邻接表（时间复杂度 O(度)）效率低。

代码实现：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// 全局变量存储图的核心信息
vector<vector<int>> adjMatrix;  // 邻接矩阵
int numVertices;                // 顶点数量
bool isDirected;                // 是否为有向图
int INF = INT_MAX;              // 无边连接的标记

// 初始化图
void initGraph(int n, bool directed = false, int inf = INT_MAX) {
    numVertices = n;
    isDirected = directed;
    INF = inf;
    // 初始化矩阵：n×n，对角线为0，其余为INF
    adjMatrix.resize(n, vector<int>(n, INF));
    for (int i = 0; i < n; ++i) {
        adjMatrix[i][i] = 0;
    }
}

// 添加边
void addEdge(int from, int to, int weight = 1) {
    if (from < 0 || from >= numVertices || to < 0 || to >= numVertices) {
        cerr << "顶点索引越界！" << endl;
        return;
    }
    adjMatrix[from][to] = weight;
    if (!isDirected) {  // 无向图添加反向边
        adjMatrix[to][from] = weight;
    }
}

// 删除边
void removeEdge(int from, int to) {
    if (from < 0 || from >= numVertices || to < 0 || to >= numVertices) {
        cerr << "顶点索引越界！" << endl;
        return;
    }
    adjMatrix[from][to] = INF;
    if (!isDirected) {  // 无向图删除反向边
        adjMatrix[to][from] = INF;
    }
}

// 获取边的权值
int getWeight(int from, int to) {
    if (from < 0 || from >= numVertices || to < 0 || to >= numVertices) {
        cerr << "顶点索引越界！" << endl;
        return -1;
    }
    return adjMatrix[from][to];
}

// 打印邻接矩阵
void printAdjMatrix() {
    cout << "邻接矩阵（" << (isDirected ? "有向图" : "无向图") << "）：" << endl;
    // 打印列索引
    cout << "   ";
    for (int i = 0; i < numVertices; ++i) {
        cout << i << "  ";
    }
    cout << endl;
    // 打印每行数据
    for (int i = 0; i < numVertices; ++i) {
        cout << i << "  ";
        for (int j = 0; j < numVertices; ++j) {
            if (adjMatrix[i][j] == INF) {
                cout << "∞  ";
            } else {
                cout << adjMatrix[i][j] << "  ";
            }
        }
        cout << endl;
    }
}


int main() {
    // 测试无向无权图
    cout << "===== 无向无权图 =====" << endl;
    initGraph(4);  // 4个顶点，默认无向图
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 2);
    addEdge(1, 3);
    addEdge(2, 3);
    printAdjMatrix();

    // 测试有向带权图
    cout << "\n===== 有向带权图 =====" << endl;
    initGraph(3, true);  // 3个顶点，有向图
    addEdge(0, 1, 5);
    addEdge(1, 2, 3);
    addEdge(2, 0, 2);
    printAdjMatrix();

    // 测试删除边
    cout << "\n删除有向图中1->2的边后：" << endl;
    removeEdge(1, 2);
    printAdjMatrix();

    return 0;
}