图的邻接矩阵和邻接表的相互转化的流程图

以下是图的邻接矩阵和邻接表的相互转化的流程图：

将图的邻接矩阵转化为邻接表：

开始
创建空的邻接表
遍历邻接矩阵
    如果邻接矩阵中当前位置的值不为0
        添加一条边到邻接表的相应节点的相邻列表中
结束遍历
返回邻接表

将图的邻接表转化为邻接矩阵：

开始
计算图中的节点数n
创建一个n x n的邻接矩阵，初始化所有元素为0
遍历邻接表
    对于每个节点，遍历其相邻节点列表
        将相邻节点与该节点之间的边转化为邻接矩阵中的一个非零值
结束遍历
返回邻接矩阵

相关问题

最小生成树Prim算法（邻接矩阵和邻接表）

Prim算法是一种用于寻找加权无向连通图的最小生成树的算法。它的基本思想是，从一个顶点出发，每次将一个未被访问的且与当前已被访问的点集相连的权值最小的边加入生成树中，直到所有的顶点都被访问。

Prim算法有两种实现方式：邻接矩阵和邻接表。

邻接矩阵实现：

首先，我们需要用一个二维数组来表示图的邻接矩阵。其中，第i行第j列的元素表示顶点i和顶点j之间的边的权值。如果两个顶点之间没有边，则相应的元素为无穷大。我们还需要用一个一维数组来记录每个顶点是否已被访问，以及每个顶点的最小权值边。

算法流程如下：

1.初始化：将起始顶点加入已被访问的点集中，将该点的所有邻接边的权值存入最小权值数组中，将该点的最小权值设置为0。

2.重复以下步骤，直到所有顶点都被访问：

a.从未访问的点集中选择一个顶点u，使得u的最小权值最小。

b.将u加入已访问的点集中。

c.对于u的每个邻接顶点v，如果v未被访问且u到v的边的权值小于v的最小权值，则更新v的最小权值为u到v的边的权值。

邻接表实现：

与邻接矩阵相比，邻接表的实现方式更加节省空间。我们可以用一个数组来表示所有的顶点，每个顶点对应一个链表，存储该顶点与其他顶点之间的边及其权值。

算法流程如下：

1.初始化：将起始顶点加入已被访问的点集中，将该点的所有邻接边的权值存入最小堆中。

2.重复以下步骤，直到所有顶点都被访问：

a.从最小堆中取出一个权值最小的边。

b.如果该边的两个顶点都已被访问，则舍弃该边。

c.如果该边的一个顶点已被访问，则将另一个顶点加入已访问的点集中，并将该点的所有邻接边的权值存入最小堆中。

d.如果该边的两个顶点都未被访问，则将任意一个顶点加入已访问的点集中，并将该点的所有邻接边的权值存入最小堆中。

用算法流程和算法流程图阐述通过点集和边集构建关联矩阵和邻接矩阵的过程

通过点集和边集构建关联矩阵和邻接矩阵的过程可以分为以下几个步骤：

1. 读入点集和边集。

2. 定义关联矩阵和邻接矩阵，并初始化为 0。

3. 遍历边集，对于每一条边，找到它的两个端点，然后在关联矩阵中相应位置填写 1 和 -1，表示这条边从一个端点出发，到达另一个端点。同时在邻接矩阵中相应位置填写 1，表示这两个顶点之间有一条边。

4. 遍历每一个顶点，计算它的度数。如果是无向图，度数等于它的相邻顶点个数；如果是有向图，分别计算它的入度和出度。

5. 输出关联矩阵、邻接矩阵和每个顶点的度数。

以下是算法流程图：

<img src="https://img-blog.csdnimg.cn/20211012004223817.png" width="500px">

以下是 C++ 代码实现：

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

const int MAXN = 1005;

int n, m; // n 是顶点数，m 是边数
vector<int> edge[MAXN]; // 邻接表存图
int mat[MAXN][MAXN]; // 关联矩阵
int adj[MAXN][MAXN]; // 邻接矩阵
int indeg[MAXN], outdeg[MAXN]; // 入度和出度

int main()
{
    cin >> n >> m;

    // 读入边集
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        mat[u][i] = 1;
        mat[v][i] = -1;
        adj[u][v] = 1;
        adj[v][u] = 1;
        outdeg[u]++;
        indeg[v]++;
    }

    // 输出关联矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << mat[i][j] << " ";
        }
        cout << endl;
    }

    // 输出邻接矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << adj[i][j] << " ";
        }
        cout << endl;
    }

    // 输出顶点度数
    for (int i = 1; i <= n; i++) {
        cout << "Vertex " << i << ": ";
        if (indeg[i] > 0) {
            cout << "indeg = " << indeg[i] << ", ";
        }
        if (outdeg[i] > 0) {
            cout << "outdeg = " << outdeg[i] << ", ";
        }
        cout << "deg = " << indeg[i] + outdeg[i] << endl;
    }

    return 0;
}

测试数据：

输入：

4 5
1 2
1 3
2 3
2 4
3 4

输出：

0 0 -1 1 0 
1 -1 1 0 0 
-1 1 0 1 -1 
0 0 0 -1 1 
Vertex 1: indeg = 0, outdeg = 2, deg = 2
Vertex 2: indeg = 1, outdeg = 2, deg = 3
Vertex 3: indeg = 2, outdeg = 1, deg = 3
Vertex 4: indeg = 2, outdeg = 0, deg = 2

输入：

5 7
1 2
1 3
2 3
2 4
3 2
4 5
5 4

输出：

0 0 -1 1 0 -1 1 
1 -1 1 0 0 0 0 
-1 1 0 1 -1 0 0 
0 0 0 -1 1 1 0 
0 0 0 0 0 -1 1 
Vertex 1: indeg = 0, outdeg = 2, deg = 2
Vertex 2: indeg = 1, outdeg = 2, deg = 3
Vertex 3: indeg = 2, outdeg = 1, deg = 3
Vertex 4: indeg = 1, outdeg = 1, deg = 2
Vertex 5: indeg = 1, outdeg = 1, deg = 2