【图的存储】邻接矩阵与邻接表的转换

wuchangjian2021-11-16 19:53:02编程学习

邻接矩阵转换成邻接表

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 n n m m m

接下来 m m m 行,每行包含三个整数 u u u, v v v, w w w,表示点 u u u 和点 v v v 之间存在一条权值为 w w 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 (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;
}

输入格式

第一行包含两个整数 n n n m m m

接下来 m m m 行,每行包含三个整数 u u u, v v v, w w w,表示点 u u u 和点 v v v 之间存在一条权值为 w w 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 - 

相关文章

MSP430F5xx / F6xx系列 DCO频率范围选择方法

1. 数控振荡器(DCO) DCO是一个集成的数字控制振荡...

Redis

目录     1. redis         1. 概念         2. 下载...

面试复盘|杭州-蚂蚁金服-CTO-Java研发

序言 参加完一场惨烈的秋招战斗,最终签约蚂蚁,现来总结秋招...

GIS实战应用案例100篇(四)-影像多种分类方法对比分析(非监督分类、监督分类、决策树分类)

GIS实战应用案例100篇(四)-影像多种分类方法对比分析(非监督分类、监督分类、决策树分类)

目的 1、掌握遥感影像的各种分类方法; 2、比较Landsat数据和哨兵数据分类...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。