精华内容
下载资源
问答
  • 邻接矩阵邻接表的相互转换
    2021-05-25 01:34:51

    编写一个程序,输出带权图的邻接矩阵,并能将该邻接矩阵转换成相应的邻接表,并输出该邻接表,带权图如下图所示。

    具体效果如下:  2.1.编写一个算法,实现由已知的邻接表产生对应的邻接矩阵,并输出。 具体效果如下:

    #include

    #include

    #define MAXV 100

    #define MaxSize 100

    #define INF 327676

    using namespace std;

    typedef char InfoType;

    typedef char ElemType;

    //邻接矩阵声明

    typedef struct

    {

    int no;

    InfoType info;

    } VertexType;

    typedef struct

    {

    int edges[MAXV][MAXV];

    int n,e;

    VertexType vexs[MAXV];

    } MatGraph;

    //邻接表声明

    typedef struct ANode

    {

    int adjvex;

    struct ANode *nextarc;

    int weight;

    } ArcNode;

    typedef struct Vnode

    {

    InfoType info;

    ArcNode *firstarc;

    } VNode;

    typedef struct

    {

    VNode adjlist[MAXV];

    int n,e;

    } AdjGragh;

    //创建邻接矩阵

    void CreatrMat(MatGraph &g,int A[MAXV][MAXV],int n,int e)

    {

    int i,j;

    g.n=n;

    g.e=e;

    for(i=0; i

    for(j=0; j

    g.edges[i][j]=A[i][j];

    }

    //输出邻接矩阵

    void DispMat(MatGraph g)

    {

    int i,j;

    for(i=0; i

    {

    for(j=0; j

    {

    if(g.edges[i][j]!=INF)

    printf("%4d",g.edges[i][j]);

    else

    printf("%4s","∞");

    }

    cout<

    }

    }

    //邻接矩阵转换为邻接表

    void MatToList(MatGraph g,AdjGragh *&G)

    {

    int i,j;

    ArcNode *p;

    G=(AdjGragh *)malloc(sizeof(AdjGragh));

    for(i=0; i

    G->adjlist[i].firstarc=NULL;

    for(i=0; i

    {

    for(j=g.e-1; j>=0; j--)

    {

    if(g.edges[i][j]!=0&&g.edges[i][j]!=INF)

    {

    p=(ArcNode *)malloc(sizeof(ArcNode));

    p->adjvex=j;

    p->weight=g.edges[i][j];

    p->nextarc=G->adjlist[i].firstarc;

    G->adjlist[i].firstarc=p;

    }

    }

    }

    G->n=g.n;

    G->e=g.e;

    }

    //输出邻接表

    void DispAdj(AdjGragh *G)

    {

    int i;

    ArcNode *p;

    for(i=0; in; i++)

    {

    p=G->adjlist[i].firstarc;

    printf("%3d: ",i);

    while(p!=NULL)

    {

    printf("%3d(%d) ",p->adjvex,p->weight);

    p=p->nextarc;

    }

    cout<

    }

    }

    //邻接表转换成邻接矩阵

    void ListToMat(AdjGragh *G,MatGraph &g)

    {

    int i;

    ArcNode *p;

    for(i=0; in; i++)

    {

    p=G->adjlist[i].firstarc;

    while(p!=NULL)

    {

    g.edges[i][p->adjvex]=p->weight;

    p=p->nextarc;

    }

    }

    g.n=G->n;

    g.e=G->e;

    }

    //主函数

    int main()

    {

    MatGraph g;

    AdjGragh *G;

    int A[MAXV][MAXV]= {{0,5,INF,7,INF,INF},{INF,0,4,INF,INF,INF},

    {8,INF,0,INF,INF,9},{INF,INF,5,0,INF,6},

    {INF,INF,INF,5,0,INF},{3,INF,INF,INF,1,0}

    };

    printf("有向图G的邻接矩阵:\n");

    CreatrMat(g,A,6,6);

    DispMat(g);

    printf("图G的邻接矩阵转换成邻接表:\n");

    MatToList(g,G);

    DispAdj(G);

    printf("图G的邻接表转换成邻接矩阵:\n");

    ListToMat(G,g);

    DispMat(g);

    printf("图G的邻接表:\n");

    MatToList(g,G);

    DispAdj(G);

    return 0;

    }

    更多相关内容
  • 学习数据结构和离散数学的同学, 这是我的理解和相关代码
  • 图的邻接矩阵邻接表实现, 深度搜索, 广度搜索, Dijstra最短路径
  • 领会图的两种主要存储结构、图基本运算算法和两种遍历算法设计内容:编写一个程序,设计带权图的邻接矩阵邻接表的创建和输出运算,并在此基础上设计一个主程序完成如下功能:(1)建立如图所示的有向图G的邻接矩阵...
  • 程序设计任务: 设计一个程序,实现以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。基本要求:以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的...
  • 下面用Python实现图论中图结构的邻接表以及邻接矩阵, 都采用Python内置的列表数据类型实现. 代码 def matrix2table(martrix): result = [] N = len(matrix) for i in range(N): tmp1 = [] for j in range(N): if ...

    tags: Python GT

    写在前面

    学图论当然要学其中的算法, 学算法的基础在数据结构, 当然也少不了程序. 虽然不是专门研究图论, 但是能根据算法写出代码, 才算是真正掌握了这些概念了吧.

    下面用Python实现图论中图结构的邻接表以及邻接矩阵, 都采用Python内置的列表数据类型实现.

    代码

    def matrix2table(martrix):
        result = []
        N = len(matrix)
        for i in range(N):
            tmp1 = []
            for j in range(N):
                if matrix[i][j]:
                    tmp1.append(j)
            result.append(tmp1)
        return result
    
    
    def table2matrix(table):
        ret = []
        N = len(table)
        for i in range(N):
            tmp = [0] * N
            for j in table[i]:
                tmp[j] = 1
            ret.append(tmp)
        return ret
    
    
    matrix = [
        [0, 1, 0, 0, 0],
        [0, 0, 1, 1, 0],
        [0, 0, 0, 0, 1],
        [1, 0, 0, 0, 1],
        [0, 1, 0, 0, 0]
    ]
    
    tb = matrix2table(matrix)
    print(tb)
    
    mat = table2matrix(tb)
    print(mat)
    
    

    思路很简单, 在这里小小记录一下.

    展开全文
  • 利用邻接矩阵容易判定任意两个顶点之间是否有边(或弧)相连,并容易求得各个顶点的度。 c语言代码实现如下: #include #include #define MAX_VER_NUM 50 typedef char VertexType; typedef enum { DG,UDG }...
  • 数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历 数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历.rar
  • 图的邻接表 邻接矩阵表示的迪杰斯特拉算法 普里姆算法 克鲁斯卡尔算法 用c++实现 codeblocks编译通过
  • 文章目录邻接矩阵邻接表储存图的信息图的存储方式邻接矩阵的介绍邻接矩阵的实现定义邻接矩阵创建邻接矩阵打印邻接矩阵完整代码邻接表的介绍邻接表的实现定义邻接表创建邻接表完整代码 /* *@author zhazhazhi *qq:...

    /*
    *@author zhazhazhi
    *qq:2055418639
    *github:zhazhazhi7
    */
    

    邻接矩阵及邻接表储存图的信息

    图的存储方式

    一般的图的基本存储方式有三种,邻接矩阵法、邻接表法和十字链表法,其中邻接矩阵与邻接表是最简单的图的储存结构。

    邻接矩阵的介绍

    顶点数据存储

    • 一位数组

    边(弧)信息的存储

    • 邻接矩阵:图中n个顶点之间相邻关系的n阶方阵(即二维数组a[n] [n])
    • 邻接矩阵中元素值的情况(规定自身无边、无弧)
    • 二维数组中的元素值为1表示存在关系、值为0表示不存在关系

    表示无向图时的特点:

    • 矩阵对角线对称
    • 行方向或列防向的非零元素个数为该顶点的度

    表示有向图时的特点:

    • 矩阵不对称
    • 行方向非零元素的个数表示顶点元素的出度
    • 列方向非零元素的个数表示顶点元素的入度

    邻接矩阵本身的特点:

    优点:容易实现图的操作,如:求某顶点的度、判断顶点之间是否有边(弧)、栈顶点的邻接点等。

    缺点:n个顶点需要n*n个单元存储边(弧);空间效率为O(n^2)。

    邻接矩阵的实现

    定义邻接矩阵

    typedef int ElemType;
    typedef struct MGraph{
    	int vn,en;
    	ElemType vex[MAXIN];
    	ElemType arc[MAXIN][MAXIN];
    }MGraph;//定义无向图
    

    创建邻接矩阵

    int CreateGraph(MGraph &g){
    	cout<<"请输入图的顶点数与边数"<<endl;
    	cin>>g.vn>>g.en;
    	cout<<"请输入顶点信息"<<endl;
    	for(int i=0;i<g.vn;i++){
    		cin>>g.vex[i];
    	}
    	for(int i=0;i<g.vn;i++){
    		for(int j=0;j<g.vn;j++){
    			g.arc[i][j] = 0;
    		}
    	}//初始化邻接矩阵
    	cout<<"请输入图的关系"<<endl;
    	int f,l;
    	for(int i=0;i<g.en;i++){
    		cin>>f>>l;
    		g.arc[f][l] = 1;
    		g.arc[l][f] = g.arc[f][l];
    	}
    	cout<<"创建成功"<<endl;
    }//创建无向图 
    

    打印邻接矩阵

    void Print(MGraph g){
    	for(int i=0;i<g.vn;i++){
    		for(int j=0;j<g.vn;j++){
    			cout<<g.arc[i][j]<<" ";
    		}
    		cout<<endl;
    	}
    }//打印邻接矩阵 
    

    完整代码

    #include<bits/stdc++.h>
    //利用邻接矩阵存储无向图 
    using namespace std;
    
    #define MAXIN 20
    
    typedef int ElemType;
    typedef struct MGraph{
    	int vn,en;
    	ElemType vex[MAXIN];
    	ElemType arc[MAXIN][MAXIN];
    }MGraph;//定义无向图
    
    int CreateGraph(MGraph &g){
    	cout<<"请输入图的顶点数与边数"<<endl;
    	cin>>g.vn>>g.en;
    	cout<<"请输入顶点信息"<<endl;
    	for(int i=0;i<g.vn;i++){
    		cin>>g.vex[i];
    	}
    	for(int i=0;i<g.vn;i++){
    		for(int j=0;j<g.vn;j++){
    			g.arc[i][j] = 0;
    		}
    	}//初始化邻接矩阵
    	cout<<"请输入图的关系"<<endl;
    	int f,l;
    	for(int i=0;i<g.en;i++){
    		cin>>f>>l;
    		g.arc[f][l] = 1;
    		g.arc[l][f] = g.arc[f][l];
    	}
    	cout<<"创建成功"<<endl;
    }//创建无向图 
    
    void Print(MGraph g){
    	for(int i=0;i<g.vn;i++){
    		for(int j=0;j<g.vn;j++){
    			cout<<g.arc[i][j]<<" ";
    		}
    		cout<<endl;
    	}
    }//打印邻接矩阵 
    
    int main(){
    	MGraph g;
    	CreateGraph(g);
    	Print(g);
    }
    

    邻接表的介绍

    是顺序与链接相结合的图的存储方式

    所有顶点组成一个数组,每个顶点建立一个单链表

    有两部分组成:

    • 表头——顶点数组(存放顶点信息)
    • 表体——单链表(存放与顶点相关的边或者弧的关系)

    表示无向图时的特点:

    • 顶点的度——与结点相连的单链表的个数

    表示有向图时的特点:

    • 顶点的出度——与结点相连的单链表的个数
    • 顶点的入度——遍历所有结点,统计得到

    邻接表本身的特点:

    有点:空间效率高,容易找到顶点的邻接点

    缺点:判断两个顶点是否有关联时需要遍历该结点的单链表,没有邻接矩阵方便

    邻接表的实现

    定义邻接表

    typedef int ElemType;
    typedef struct ArcNode{
    	ElemType vertvex;
    	ArcNode *next;
    }ArcNode,*Arc;//创建结点存储链表结构
    typedef struct {
    	ElemType adjvex;
    	ArcNode *firstarc;
    }VexNode;//结点类型
    typedef struct {
    	int vn,en;
    	VexNode vex[MAXIN];
    }ALGraph;//创建邻接表存储结构 
    

    创建邻接表

    int CreateGraph(ALGraph &a){
    	 cout<<"请输入有向图的结点数与弧数"<<endl;
    	 cin>>a.en>>a.vn;
    	 cout<<"请输入结点信息"<<endl;
    	 for(int i=0;i<a.vn;i++){
    	 	cin>>a.vex[i].adjvex;
    	 	a.vex[i].firstarc = NULL;
    	 }
    	 cout<<"请输入结点关系"<<endl;
    	 int f,l;
    	 for(int i=0;i<a.en;i++){
    	 	cin>>f>>l;
    	 	Arc p = (ArcNode *)malloc(sizeof(ArcNode));
    	 	p->vertvex = l;
    	 	p->next = a.vex[f].firstarc;
    	 	a.vex[f].firstarc = p;
    	 }
    	 cout<<"创建成功"<<endl;
    }//创建邻接表 
    

    完整代码

    #include<bits/stdc++.h>
    //邻接表存储结构的有向图 
    using namespace std;
    
    #define MAXIN 20
    
    typedef int ElemType;
    typedef struct ArcNode{
    	ElemType vertvex;
    	ArcNode *next;
    }ArcNode,*Arc;//创建结点存储链表结构
    typedef struct {
    	ElemType adjvex;
    	ArcNode *firstarc;
    }VexNode;//结点类型
    typedef struct {
    	int vn,en;
    	VexNode vex[MAXIN];
    }ALGraph;//创建邻接表存储结构 
    
    int CreateGraph(ALGraph &a){
    	 cout<<"请输入有向图的结点数与弧数"<<endl;
    	 cin>>a.en>>a.vn;
    	 cout<<"请输入结点信息"<<endl;
    	 for(int i=0;i<a.vn;i++){
    	 	cin>>a.vex[i].adjvex;
    	 	a.vex[i].firstarc = NULL;
    	 }
    	 cout<<"请输入结点关系"<<endl;
    	 int f,l;
    	 for(int i=0;i<a.en;i++){
    	 	cin>>f>>l;
    	 	Arc p = (ArcNode *)malloc(sizeof(ArcNode));
    	 	p->vertvex = l;
    	 	p->next = a.vex[f].firstarc;
    	 	a.vex[f].firstarc = p;
    	 }
    	 cout<<"创建成功"<<endl;
    }//创建邻接表 
    
    int main(){
    	ALGraph a;
    	CreateGraph(a);
    }
    

    谢谢阅读!

    展开全文
  • 1. 图 图是一种非线性数据结构,由「节点(顶点)vertex」和「边 edge」组成,每条边连接一对顶点。根据边的方向有无,图可分为「有向图」和「无向图」。本文 以无向图为例开展介绍。...邻接表 2. 邻接矩阵

    1. 图

    图是一种非线性数据结构,由「节点(顶点)vertex」和「边 edge」组成,每条边连接一对顶点。根据边的方向有无,图可分为「有向图」和「无向图」。本文 以无向图为例开展介绍。

    如下图所示,此无向图的 顶点 和 边 集合分别为:

    顶点集合: vertices = {1, 2, 3, 4, 5}
    边集合: edges = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5), (4, 5)}
    在这里插入图片描述
    表示图的方法通常有两种:

    • 邻接矩阵
    • 邻接表

    2. 邻接矩阵

    • 用数组 vertices存储顶点,邻接矩阵 edges 存储边
    • edges[i][j]代表节点 i + 1 和 节点 j + 1之间是否有边
      在这里插入图片描述
    int[] vertices = {1, 2, 3, 4, 5};
    int[][] edges = {{0, 1, 1, 1, 1},
                     {1, 0, 0, 1, 0},
                     {1, 0, 0, 0, 1},`在这里插入代码片`
                     {1, 1, 0, 0, 1},
                     {1, 0, 1, 1, 0}};
    

    3. 邻接表

    • 使用数组 vertices存储顶点,邻接表 edges 存储边。
    • edges为一个二维容器,第一维 i 代表顶点索引,第二维 edges[i]存储此顶点对应的边集和;
    • 例如 edges[0] = [1, 2, 3, 4]代表 vertices[0] 的边集合为 [1, 2, 3, 4] 。

    在这里插入图片描述

    int[] vertices = {1, 2, 3, 4, 5};
    List<List<Integer>> edges = new ArrayList<>();
    
    List<Integer> edge_1 = new ArrayList<>(Arrays.asList(1, 2, 3, 4));
    List<Integer> edge_2 = new ArrayList<>(Arrays.asList(0, 3));
    List<Integer> edge_3 = new ArrayList<>(Arrays.asList(0, 4));
    List<Integer> edge_4 = new ArrayList<>(Arrays.asList(0, 1, 4));
    List<Integer> edge_5 = new ArrayList<>(Arrays.asList(0, 2, 3));
    edges.add(edge_1);
    edges.add(edge_2);
    edges.add(edge_3);
    edges.add(edge_4);
    edges.add(edge_5);
    

    4. 邻接矩阵 VS 邻接表

    邻接矩阵的大小只与节点数量有关,即 N^2,其中 N 为节点数量。因此,当边数量明显少于节点数量时,使用邻接矩阵存储图会造成较大的内存浪费。

    • 邻接表适合存储稀疏图(顶点较多、边较少)
    • 邻接矩阵 适合存储稠密图(顶点较少、边较多)
    展开全文
  • 图的邻接矩阵实现 逻辑结构分为两部分:V和E集合。因此,用一个一维数组存放图中所有顶点数据;用一个二维数组存放顶点间关系(边或弧)的数据,这个二维数组称为邻接矩阵邻接矩阵又分为有向图邻接矩阵和无向图邻接...
  • 邻接矩阵邻接表

    千次阅读 2020-07-05 19:30:41
    图的存储结构主要分两种,一种是邻接矩阵,一种是邻接表。 1.邻接矩阵 邻接矩阵的存储方式是用两个数组来表示图。一个一维数组储存图中顶点信息,一个二维数组储存图中的边或弧的信息。 无向图 这里右图是把...
  • 邻接矩阵转换为邻接表邻接表转换为邻接矩阵

    千次阅读 多人点赞 2020-10-24 19:47:04
    1.两种存储结构(邻接表邻接矩阵) //图的两种存储结构 #define INF 32767 //定义∞ #define MAXV 100 //最大顶点个数 typedef char InfoType; //以下定义邻接矩阵类型 typedef struct { int no; //...
  • 邻接矩阵邻接表

    2017-08-17 21:50:20
    邻接矩阵:使用|V|*|V|的二维数组来表示图,g[i][j]表示顶点i和顶点j的关系。 在无向图中可以用1和0表示两顶点之间的边是否存在。 在有向图中用同样的方法表示连接,需要注意的是因为有向图中表示方向,所以中不满足...
  • 分别以邻接矩阵邻接表的方式实现图的深度优先搜索、广度优先搜索
  • 图的邻接矩阵邻接表的比较

    万次阅读 多人点赞 2018-08-16 15:39:11
    图的存储结构主要分两种,一种是邻接矩阵,一种是邻接表。1.邻接矩阵 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息。 设图G有n个顶点...
  • G的邻接矩阵是一个具有下列性质的n阶方阵:①对 无向图 而言,邻接矩阵一定是对称的,而且主对角线一定为零(在此仅讨论无向简单图),副对角线不一定为0, 有向图 则不一定如此。. ②在无向图中,任一顶点i的度为第...
  • tags: Python GT 写在前面 应傻狗的评论, 这里给出加权图的邻接矩阵邻接表的转换, 格式是按照networkx的格式来的. 注意这里的矩阵遵循: 自己跟自己距离为0, 不邻接的两个节点距离为inf, 但是在networkx中, 邻接...
  • 邻接矩阵的C语言描述 基本运算的算法——建立无向网的邻接矩阵、求图中与顶点i邻接的第一个顶点、求图中顶点i相对于顶点j的下一个邻接点、若图G中存在顶点u,则返回该顶点在图中的位置、图的广度优先遍历、图的深度...
  • /*以下定义邻接表类型*/ typedef struct ANode /*弧的结点结构类型*/ { int adjvex; /*该弧的终点位置*/ struct ANode *nextarc; /*指向下一条弧的指针*/ InfoType info; /*该弧的相关信息,这里用于存放权值*/ }...
  • 辛丑年冬月初一,微冷,键盘不如砚冰坚,手指尚能屈伸,但仍旧敲不出只有五行算法的Floyd,自修室确实好睡,周杰伦唱《雨下一整晚》,周树皮能口水流一整页,也算是身体的一部分和算法融为一体了,课设是不敢稍逾约...
  • 图的存储一般来说有四种,但是由于考试还有本人是鶸,所以就只讨论邻接矩阵邻接表 图的模板基类 const int maxWeight = ……; //无穷大的值(=) const int DefaultVertices = 30; //最大顶点数(=n) ...
  • 一般图的表示方法为G(V,E),其中G表示graphic图,V表示点的集合,E表示边的集合,一般可以用邻接矩阵邻接表来表示一个图 图的分类: 按照方向可以分为有向图和无向图 按照权重可以分为带权图和不带权图 邻接...
  • 利用networkx,numpy,matplotlib,将邻接矩阵输出为图形。 1,自身确定一个邻接矩阵,然后通过循环的方式添加变,然后输出图像 import networkx as nx import matplotlib.pyplot as plt import numpy as np G = nx...
  • 用Python将Excel网络关系(两列,id1,id2)转换为邻接矩阵(有向网络和无向网络均可),并画出网络图
  • 图的表示形式:邻接矩阵邻接表

    千次阅读 2021-03-21 08:48:40
    图是对象和对象之间存在的关系的有限集合。如果将对象表示为顶点(或节点),将关系表示为边,则可以得到以下两种图形: ...邻接表 邻接矩阵 让我们考虑一个图,其中有从0到N-1编号的N个顶点和(i,j)形式的E...
  • 图的存储结构(邻接矩阵邻接表) 前言: 前面我们学习图的有些定义和术语,对图这个数据结构有了新的见解和认知,让我们理解图结构的知识,今天我们学习图的存储结构,图的存储结构比较多,我们今天主要是学习邻接...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 39,298
精华内容 15,719
关键字:

邻接矩阵 邻接表

友情链接: vbSendMail.rar