邻接表与邻接矩阵的相互转换

这篇具有很好参考价值的文章主要介绍了邻接表与邻接矩阵的相互转换。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

邻接表转邻接矩阵的算法思想:首先初始化邻接矩阵。遍历邻接表,在依次遍历顶点vertices[i]的边链表时,修改邻接矩阵的第i行的元素值。若链表边结点的值为 j,则置邻接矩阵的edge[i][j]=1。遍历完邻接表时,整个转换过程结束。此算法对于无向图有向图均适用。
邻接矩阵转邻接表的算法思想:首先初始化邻接表的各个边表结点,将边表结点的first指针指向NULL。遍历邻接矩阵,遍历到edge[i][j]==1时,将结点值为j的顶点插入到vertices[i]的边链表中。遍历完邻接矩阵,整个转换过程结束。

图的邻接表存储结构定义如下

const int MaxVertexNum = 100; // 图中顶点数目的最大值
typedef struct ArcNode { //边表结点
    int adjvex; // 该弧所指向的顶点的位置
    struct ArcNode *next; //指向下一条弧的指针
    // int weight; //网的边权值
    // Infotype info;
}ArcNode;
typedef struct VNode { //顶点表结点
    ArcNode *first; // 指向第一条依附该顶点的弧的指针
}VNode, AdjList[MaxVertexNum];
typedef struct {
    AdjList vertices; //邻接表
    int vexnum, arcnum; //图的顶点数和弧数
}ALGraph; // ALGraph是以邻接表存储的图类型

图的邻接矩阵存储结构定义如下

typedef struct{
    int Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵,边表
    int vexnum, arcnum; //图的当前顶点数和弧数
}MGraph;

邻接矩阵转化为邻接表算法实现如下

void matrix_convert_table(ALGraph &G1, MGraph G2) { // 邻接矩阵转化为邻接表
    G1.arcnum = G2.arcnum;
    G1.vexnum = G2.vexnum;
    for(int i = 1; i <= G1.vexnum; i++) {
        G1.vertices[i].first = NULL; // 初始化指向第一条依附该顶点的弧的指针
    }
    ArcNode *p;
    for(int i = 1; i <= G2.vexnum; i++) { // 依次遍历整个邻接矩阵
        for(int j = 1; j <= G2.vexnum; j++) {
            if(G2.Edge[i][j] == 1) {
                p = (ArcNode *) malloc (sizeof(ArcNode));
                p -> adjvex = j;
                p -> next = G1.vertices[i].first;
                G1.vertices[i].first = p;
            }
        }
    }
}

邻接表转化为邻接矩阵算法实现如下

void table_convert_matrix(MGraph &G1, ALGraph G2) { // 邻接表转化为邻接矩阵
    G1.arcnum = G2.arcnum;
    G1.vexnum = G2.vexnum;
    for(int i = 1; i <= G1.vexnum; i++) {
        for(int j = 1; j <= G1.vexnum; j++) {
            G1.Edge[i][j] = 0; // 初始化邻接矩阵
        }
    }
    ArcNode *p;
    for(int i = 1; i <= G2.vexnum; i++) { //依次遍历各顶点表结点为头的边链表
        p = G2.vertices[i].first; // 取出顶点 i 的第一条出边
        while(p) { //遍历边链表
            G1.Edge[i][p->adjvex] = 1; 
            p = p -> next; // 取出下一条出边
        }
    }
}

我们依然以下面这个图为例子,便得到了一个输入样例:

6 8
1 2
1 4
4 2
2 5
5 4
3 5
3 6
6 6

邻接矩阵转化为邻接表,数据结构,算法,图论

完整可执行代码如下:文章来源地址https://www.toymoban.com/news/detail-524714.html

#include<bits/stdc++.h>
using namespace std;
//图的邻接表存储结构定义如下
const int MaxVertexNum = 100; // 图中顶点数目的最大值
typedef struct ArcNode { //边表结点
    int adjvex; // 该弧所指向的顶点的位置
    struct ArcNode *next; //指向下一条弧的指针
    // int weight; //网的边权值
    // Infotype info;
}ArcNode;
typedef struct VNode { //顶点表结点
    ArcNode *first; // 指向第一条依附该顶点的弧的指针
}VNode, AdjList[MaxVertexNum];
typedef struct {
    AdjList vertices; //邻接表
    int vexnum, arcnum; //图的顶点数和弧数
}ALGraph; // ALGraph是以邻接表存储的图类型

//图的邻接矩阵存储结构定义如下
typedef struct{
    int Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵,边表
    int vexnum, arcnum; //图的当前顶点数和弧数
}MGraph;

void Create_Graph(ALGraph &AG, MGraph &MG) { //创建一个邻接表和邻接矩阵
    scanf("%d%d", &AG.vexnum, &AG.arcnum); //输入图的顶点数和边数
    MG.arcnum = AG.arcnum;
    MG.vexnum = AG.vexnum;
    for(int i = 1; i <= MG.vexnum; i++) { // 初始化邻接矩阵
        for(int j = 1; j <= MG.vexnum; j++) {
            MG.Edge[i][j] = 0;
        }
    }
    for(int i = 1; i <= AG.vexnum; i++) {
        AG.vertices[i].first = NULL; //初始化第一条依附该顶点的弧的指针为空
    }
    ArcNode *p;
    for(int i = 0; i < AG.arcnum; i++) {
        int u, v;
        scanf("%d%d", &u, &v); //u, v表示u有一条边指向v;
        MG.Edge[u][v] = 1;
        p = (ArcNode *) malloc (sizeof(ArcNode)); // p = new ArcNode;
        p -> adjvex = v;
        p -> next = AG.vertices[u].first; //用头插法将v插到结点u的边表结点中
        AG.vertices[u].first = p; // 插入后将第一条依附该顶点的弧的指针修改为p
    }
}

void matrix_convert_table(ALGraph &G1, MGraph G2) { // 邻接矩阵转化为邻接表
    G1.arcnum = G2.arcnum;
    G1.vexnum = G2.vexnum;
    for(int i = 1; i <= G1.vexnum; i++) {
        G1.vertices[i].first = NULL; // 初始化指向第一条依附该顶点的弧的指针
    }
    ArcNode *p;
    for(int i = 1; i <= G2.vexnum; i++) { // 依次遍历整个邻接矩阵
        for(int j = 1; j <= G2.vexnum; j++) {
            if(G2.Edge[i][j] == 1) {
                p = (ArcNode *) malloc (sizeof(ArcNode));
                p -> adjvex = j;
                p -> next = G1.vertices[i].first;
                G1.vertices[i].first = p;
            }
        }
    }
}

void table_convert_matrix(MGraph &G1, ALGraph G2) { // 邻接表转化为邻接矩阵
    G1.arcnum = G2.arcnum;
    G1.vexnum = G2.vexnum;
    for(int i = 1; i <= G1.vexnum; i++) {
        for(int j = 1; j <= G1.vexnum; j++) {
            G1.Edge[i][j] = 0; // 初始化邻接矩阵
        }
    }
    ArcNode *p;
    for(int i = 1; i <= G2.vexnum; i++) { //依次遍历各顶点表结点为头的边链表
        p = G2.vertices[i].first; // 取出顶点 i 的第一条出边
        while(p) { //遍历边链表
            G1.Edge[i][p->adjvex] = 1; 
            p = p -> next; // 取出下一条出边
        }
    }
}

void print_matrix(MGraph G) { // 打印邻接矩阵
    for(int i = 1; i <= G.vexnum; i++) {
        for(int j = 1; j <= G.vexnum; j++) {
            cout << G.Edge[i][j] << " ";
        }
        puts("");
    }
}
void print_table(ALGraph G) { // 打印邻接表
    for(int i = 1; i <= G.vexnum; i++) {
        printf("(%d) ", i);
        ArcNode *p = G.vertices[i].first;
        while(p) {
            printf("-> %d ", p -> adjvex);
            p = p -> next;
        }
        puts("");
    }
}
int main() {
    MGraph MG1, MG2;
    ALGraph AG1, AG2;
    Create_Graph(AG1, MG1);
    cout << endl;
    print_matrix(MG1);
    cout << endl;
    print_table(AG1);
    cout << endl;
    matrix_convert_table(AG2, MG1); // 邻接矩阵转邻接表
    print_table(AG2); // 打印转化后的邻接表
    cout << endl;
    table_convert_matrix(MG2, AG1); // 邻接表转邻接矩阵
    print_matrix(MG2); // 打印转化后的邻接矩阵
    
    return 0;
}
/*
测试样例二:
9 14
1 2
1 3
2 5
2 4
5 3
5 4
5 6
6 5
3 8
8 9
9 6
4 7
7 6
7 9
*/

到了这里,关于邻接表与邻接矩阵的相互转换的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 对无向图进行邻接矩阵的转化,并且利用DFS(深度优先)和BFS(广度优先)算法进行遍历输出, 在邻接矩阵存储结构上,完成最小生成树的操作。

    目录 一 实验目的 二 实验内容及要求 实验内容: 实验要求: 三 实验过程及运行结果 一 算法设计思路 二 源程序代码 三、截图 四 调试情况、设计技巧及体会 1.掌握图的相关概念。 2.掌握用邻接矩阵和邻接表的方法描述图的存储结构。 3.掌握图的深度优先搜索和广度优

    2024年02月04日
    浏览(57)
  • 【数据结构】邻接矩阵和邻接图的遍历

    本篇文章开始学习数据结构的图的相关知识,涉及的基本概念还是很多的。 本文的行文思路: 学习图的基本概念 学习图的存储结构——本文主要介绍邻接矩阵和邻接表 对每种结构进行深度优先遍历和广度优先遍历 话不多说,狠活献上 等等,先别急,正式学习之前先认识几个

    2024年02月04日
    浏览(52)
  • 【数据结构】邻接矩阵法

    顶点用一维数组Vex表示,其中可存放较为复杂的信息(如下标),边表用二维数组Edge表示,存放边的信息(两顶点之间有直接相连的边为1,否则为0)。  如何求顶点的入度 、出度? 对于无向图  第 i 个节点的度: 该结点所在行列的非0元素个数 对于有向图  第i个节点的

    2024年02月12日
    浏览(60)
  • 数据结构——图篇(邻接矩阵、邻接表、深度优先搜索、广度优先搜索)

    描述 图比树更为复杂,展现的是一种多对多的关系,图的结构是任意两个数据对象之间都可能存在某种特定的关系的数据结构 概念 顶点 : 基本介绍 顶点集合表示为V集合,要求图中顶点至少要有一个,即V集合不能为空集。通常使用|V|来表示顶点的个数,通常使用E(V)来表示

    2024年02月04日
    浏览(41)
  • ABB机器人欧拉角与四元数的相互转化以及旋转矩阵的求法

    做项目时用到ABB机器人,直接通过ABB内置的函数可以轻松实现四元数读数与欧拉角的相互转化。但实际项目需要从示教器读出相关位置并自行计算,尤其需要计算旋转矩阵。 本文以 ABB IRB120机器人 (不确定其他机器人是否与ABB机器人一致)为例如下姿态为例来描述上述几个量

    2024年02月03日
    浏览(57)
  • 数据结构与算法基础-学习-23-图之邻接矩阵与邻接表

    目录 一、定义和术语 二、存储结构 1、邻接矩阵 1.1、邻接矩阵优点 1.2、邻接矩阵缺点 2、邻接表 3、邻接矩阵和邻接表的区别和用途 3.1、区别 3.2、用途 三、宏定义 四、结构体定义 1、邻接矩阵 2、邻接表 3、网数据类型(造测试数据) 五、函数定义 1、使用邻接矩阵创建无

    2024年02月14日
    浏览(35)
  • 数据结构——图的基本定义以及图的存储结构,邻接矩阵,邻接表

    目录 图的定义和术语 图的存储结构 顺序存储结构—邻接矩阵 链式存储结构 邻接表 邻接多重表 十字链表 图的遍历 图的连通性问题 有向无环图及其应用 最短路径 图的定义:图是一种非线性的复杂的数据结构,图中的数据元素的关系是多对多的关系 ,在图中我们常常把数

    2024年02月04日
    浏览(58)
  • C++数据结构之图的存储结构——邻接矩阵和邻接表实现无向图

    关键点: 1.构建二维数组 2.对应边的位置赋值为1 由于比较简单就直接上代码: 个人对邻接表实现无向图的理解如下,仅供参考:         由于无向图的组成是由多个顶点和多条无向边组成的,因此我们可以把它拆分成两个结构,分别是顶点和无向边,又由于我们是使用

    2024年02月05日
    浏览(55)
  • 数据结构-邻接矩阵的创建与遍历

    上篇文章已经介绍了邻接矩阵的具体作用与如果利用邻接矩阵寻找相邻顶点,这次介绍重点为邻接矩阵的创建与两种遍历方式 邻接矩阵的创建 其结构体需要能记录顶点、顶点数、边数及邻接矩阵,即 创建方式则为读入边数、顶点数即各边的两个顶点和权值 图的遍历 DFS(深

    2024年02月20日
    浏览(47)
  • 【数据结构】图的创建(邻接矩阵,邻接表)以及深度广度遍历(BFS,DFS)

    图是由顶点集合及顶点间的关系组成的一种数据结构:G = (V, E),其中: 顶点集合V = {x|x属于某个数据对象集}是有穷非空集合; E = {(x,y)|x,y属于V}或者E = {x, y|x,y属于V Path(x, y)}是顶点间关系的有穷集合,也叫 做边的集合。 完全图:在有n个顶点的无向图中,若有n * (n-1)/2条边,

    2024年02月04日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包