有向图邻接矩阵表示法

有向图邻接矩阵表示法是一种常见的图的表示方法，它使用一个二维数组来表示有向图中各个节点之间的关系。

具体来说，如果有一个有向图 G=(V,E)，其中 V={v1,v2,...,vn} 表示节点集合，E 表示边的集合，那么可以使用一个 n×n 的二维数组 A 来表示这个图，其中 A[i][j] 表示从节点 i 到节点 j 是否有一条边。如果有边，那么 A[i][j] 的值为 1；否则，A[i][j] 的值为 0。

更进一步地，如果有向图中的边有权重，那么可以将 A[i][j] 的值改为边的权重。

有向图邻接矩阵表示法的优点是可以快速地判断两个节点之间是否有边，时间复杂度为 O(1)。缺点是如果图比较稀疏，即节点数远大于边数，那么邻接矩阵会占用大量的空间，造成浪费。此外，邻接矩阵表示法也不适合表示带有环的图。

相关问题

邻接矩阵表示法创建无向图

邻接矩阵是一种表示图的方式，用矩阵表示图中各个顶点之间的关系。对于无向图，邻接矩阵是一个对称矩阵，矩阵中的每个元素表示相邻顶点之间的边的数量或权重。

创建无向图的邻接矩阵表示法的步骤如下：

1. 创建一个 n × n 的矩阵，其中 n 是图中顶点的数量。

2. 在矩阵中标记顶点的编号，可以按照任意顺序给顶点编号。

3. 对于每条边 (i, j)，将矩阵中第 i 行第 j 列和第 j 行第 i 列的元素都置为 1，表示这两个顶点之间有一条边。

4. 如果图中有权重，则将矩阵中的元素改为相应的权重值。

下面是一个示例，展示如何用邻接矩阵表示法创建一个无向图：

假设有一个无向图，包含 5 个顶点和 7 条边，如下所示：

   1---2
   |\ /|
   | X |
   |/ \|
   3---4

首先，我们创建一个 5 × 5 的矩阵：

    1  2  3  4  5
  ---------------
1|  0  0  0  0  0
2|  0  0  0  0  0
3|  0  0  0  0  0
4|  0  0  0  0  0
5|  0  0  0  0  0

然后，我们按照顺序给顶点编号，并将边的信息填入矩阵中：

    1  2  3  4  5
  ---------------
1|  0  1  1  1  0
2|  1  0  1  1  0
3|  1  1  0  1  0
4|  1  1  1  0  0
5|  0  0  0  0  0

这个矩阵就是该无向图的邻接矩阵表示法。注意，由于是无向图，矩阵是对称的。例如，第 1 行第 2 列和第 2 行第 1 列的值都是 1，表示顶点 1 和顶点 2 之间有一条边。

邻接矩阵表示法创建无向图 代码

下面是使用邻接矩阵表示法创建无向图的代码示例，其中使用了二维数组来存储邻接矩阵：

#include<iostream>
using namespace std;

const int MAXN = 100; // 图的最大节点数
int graph[MAXN][MAXN]; // 邻接矩阵表示法
int n, m; // n 表示节点数，m 表示边数

int main()
{
    cin >> n >> m; // 输入节点数和边数
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v; // 输入一条边的两个端点
        graph[u][v] = 1; // 标记有一条从 u 到 v 的边
        graph[v][u] = 1; // 由于是无向图，所以还要标记有一条从 v 到 u 的边
    }
    return 0;
}

以上代码实现了使用邻接矩阵表示法创建无向图的功能，可以在输入节点数和边数后，逐个输入边的两个端点，然后标记对应的邻接矩阵元素。