[数据结构与算法]【图的存储】邻接矩阵与邻接表的转换

邻接矩阵转换成邻接表

输入格式

第一行包含两个整数 $n$ 和 $m$。

接下来 $m$ 行，每行包含三个整数 $u$,$v$,$w$，表示点 $u$ 和点 $v$ 之间存在一条权值为 $w$ 的边。

输入

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

输出

邻接矩阵表示法：
- 1 2 3 
1 - 2 - 
2 2 - 4 
3 - 4 - 

邻接表表示法(括号内为权值)：
与1相连的边有：4(3) 3(2) 2(1) 
与2相连的边有：3(2) 1(1) 
与3相连的边有：4(4) 2(2) 1(2) 
与4相连的边有：3(4) 1(3) 

c++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 100010, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];    // 邻接矩阵

struct Node
{
    int id; // 编号
    int w;  // 权值
    Node* next;
    Node(int _id, int _w) : id(_id), w(_w), next(NULL){}
} *head[N];     // 邻接表

void add(int a, int b, int w)
{
    Node* p = new Node(b, w);
    p->next = head[a];
    head[a] = p;
}

void convert()  // 邻接矩阵转换成邻接表
{
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (g[i][j] < INF / 2)
                add(i, j, g[i][j]);
}

int main()
{
    memset(g, 0x3f, sizeof g);
    cin >> n >> m;
    while (m -- )
    {
        int a, b, w;
        cin >> a >> b >> w;
        g[a][b] = g[b][a] = min(g[a][b], w);
    }
    
    puts("邻接矩阵表示法：");
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= n; j ++ )
            if (g[i][j] > INF / 2) cout << '-' << ' ';
            else cout << g[i][j] << ' ';
        cout << endl;
    }
    
    convert();
    
    puts("\n邻接表表示法(括号内为权值)：");
    for (int i = 1; i <= n; i ++ )
    {
        printf("与%d相连的边有：", i);
        for (auto p = head[i]; p; p = p->next)
            printf("%d(%d) ", p->id, p->w);
        cout << endl;
    }
    
    return 0;
}

邻接表转换成邻接矩阵

输入格式

第一行包含两个整数 $n$ 和 $m$。

接下来 $m$ 行，每行包含三个整数 $u$,$v$,$w$，表示点 $u$ 和点 $v$ 之间存在一条权值为 $w$ 的边。

输入

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

输出

邻接表表示法(括号内为权值)：
与1相连的边有：4(3) 3(2) 2(1) 
与2相连的边有：3(2) 1(1) 
与3相连的边有：4(4) 2(2) 1(2) 
与4相连的边有：3(4) 1(3) 

邻接矩阵表示法：
- 1 2 3 
1 - 2 - 
2 2 - 4 
3 - 4 - 

c++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 100010, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];    // 邻接矩阵

struct Node
{
    int id; // 编号
    int w;  // 权值
    Node* next;
    Node(int _id, int _w) : id(_id), w(_w), next(NULL){}
} *head[N];     // 邻接表

void add(int a, int b, int w)
{
    Node* p = new Node(b, w);
    p->next = head[a];
    head[a] = p;
}

void convert()  // 邻接表转换成邻接矩阵
{
    for (int i = 1; i <= n; i ++ )
    {
        for (auto p = head[i]; p; p = p->next)
        {
            int j = p->id;  // 与i相邻的点的编号
            g[i][j] = g[j][i] = p->w;
        }
    }
}

int main()
{
    memset(g, 0x3f, sizeof g);
    cin >> n >> m;
    while (m -- )
    {
        int a, b, w;
        cin >> a >> b >> w;
        // 假设没有重边
        add(a, b, w);
        add(b, a, w);
    }

    puts("邻接表表示法(括号内为权值)：");
    for (int i = 1; i <= n; i ++ )
    {
        printf("与%d相连的边有：", i);
        for (auto p = head[i]; p; p = p->next)
            printf("%d(%d) ", p->id, p->w);
        cout << endl;
    }    
      
    convert();
    
    puts("\n邻接矩阵表示法：");
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= n; j ++ )
            if (g[i][j] > INF / 2) cout << '-' << ' ';
            else cout << g[i][j] << ' ';
        cout << endl;
    }
    
    return 0;
}