邻接矩阵如何生成无向图

邻接矩阵是一种表示图形的方法，其中图形中的每个节点表示为矩阵中的行和列。对于无向图，邻接矩阵是一个对称矩阵，其中对于每个边（i，j），邻接矩阵的i行j列和j行i列中的元素都是1。

邻接矩阵可以通过以下步骤生成无向图：

1. 创建一个n*n的矩阵，其中n是图中节点的数量。
2. 将矩阵的对角线元素设置为0，因为没有节点与它们本身相连。
3. 对于每个边（i，j），将邻接矩阵的i行j列和j行i列中的元素设置为1。
4. 对于没有边相连的节点，邻接矩阵中对应的元素为0。

例如，考虑以下无向图：

   1 -- 2
   |    |
   3 -- 4

该图可以表示为以下邻接矩阵：

   0  1  1  0
   1  0  1  1
   1  1  0  1
   0  1  1  0

其中矩阵的第一行和第一列分别表示节点1，第二行和第二列表示节点2，以此类推。因此，矩阵中的元素a[i][j]表示节点i和节点j之间是否有一条边相连。

相关问题

用邻接矩阵创建无向图

要用邻接矩阵创建无向图，你需要先确定图中的顶点数量。然后，创建一个大小为顶点数量的二维矩阵，初始化所有元素为0。接下来，对于每条边 (u, v)，将矩阵的第 u 行第 v 列和第 v 行第 u 列的元素设置为1，表示存在一条连接顶点 u 和 v 的边。

以下是一段示例代码，展示了如何用邻接矩阵创建无向图：

# 定义顶点数量
num_vertices = 5

# 创建一个大小为 num_vertices x num_vertices 的邻接矩阵
adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]

# 添加边 (u, v)
def add_edge(u, v):
    adj_matrix[u][v] = 1
    adj_matrix[v][u] = 1

# 示例：添加三条边
add_edge(0, 1)
add_edge(1, 2)
add_edge(2, 3)

# 打印邻接矩阵
for row in adj_matrix:
    print(row)

输出结果为：

[0, 1, 0, 0, 0]
[1, 0, 1, 0, 0]
[0, 1, 0, 1, 0]
[0, 0, 1, 0, 0]
[0, 0, 0, 0, 0]

这个邻接矩阵表示了一个有 5 个顶点的无向图，其中的 1 表示存在边，0 表示不存在边。

使用邻接矩阵存储无向图

使用邻接矩阵存储无向图的步骤如下：
1. 定义一个顶点类型的一维数组，用于存储顶点。
2. 定义一个int类型的二维数组，用于存储边。对于无向图，邻接矩阵是一个对称矩阵，即edge[i][j] = edge[j][i]。
3. 定义两个int型变量，分别存储顶点数、边数。
4. 初始化邻接矩阵，将所有元素初始化为0。
5. 根据图的实际情况，将边的信息存储到邻接矩阵中。对于无向图，如果顶点i和顶点j之间有一条边，则将edge[i][j]和edge[j][i]的值都设为1。
6. 根据需要，可以输出邻接矩阵或者进行其他操作。

下面是一个使用邻接矩阵存储无向图的示例代码：

#include <iostream>
using namespace std;

const int max_vertex_num = 100;

typedef char VexType; // 顶点类型
typedef int EdgeType; // 边权值类型

class AMGraph {
public:
    VexType vex[max_vertex_num]; // 存储顶点
    EdgeType edge[max_vertex_num][max_vertex_num]; // 存储边
    int vex_num, edge_num; // 顶点数、边数

    // 初始化邻接矩阵
    void Init() {
        for (int i = 0; i < vex_num; i++) {
            for (int j = 0; j < vex_num; j++) {
                edge[i][j] = 0;
            }
        }
    }

    // 添加边
    void AddEdge(int i, int j) {
        edge[i][j] = 1;
        edge[j][i] = 1;
    }

    // 输出邻接矩阵
    void Print() {
        for (int i = 0; i < vex_num; i++) {
            for (int j = 0; j < vex_num; j++) {
                cout << edge[i][j] << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    AMGraph g;
    g.vex_num = 5;
    g.edge_num = 6;
    g.vex[0] = 'A';
    g.vex[1] = 'B';
    g.vex[2] = 'C';
    g.vex[3] = 'D';
    g.vex[4] = 'E';
    g.Init();
    g.AddEdge(0, 1);
    g.AddEdge(0, 2);
    g.AddEdge(1, 2);
    g.AddEdge(1, 3);
    g.AddEdge(2, 3);
    g.AddEdge(3, 4);
    g.Print();
    return 0;
}