精华内容
下载资源
问答
  • 邻接矩阵和邻接表
    千次阅读
    2020-07-05 19:30:41

    图的存储结构主要分两种,一种是邻接矩阵,一种是邻接表。

    1.邻接矩阵

    邻接矩阵的存储方式是用两个数组来表示图。一个一维数组储存图中顶点信息,一个二维数组储存图中的边或弧的信息。

    无向图

    这里写图片描述

    这里右图是把顶点作为矩阵内行和列的标头罗列出来。如果在两个顶点之间存在一条边,那么就把 1 放在这个位置上。如果边不存在,那么就赋值为 0。

    从上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都是相等的。

    从矩阵中很容易分析到图中信息:

    1)判断顶点之间是否有边很容易;

    2)要知道顶点的度,其实就是这个顶点在第i行(或第i列)的元素之和;

    3)求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点。

    有向图

    上图图右是一个有向图。有向图是看入度和出度的(顶点的入边数和出边数),例如V2,就有2个出边。列代表着顶点的入边,列的元素相加代表顶点的入度,而行则代表该顶点所有的出边,元素相加则为顶点的出度。假如V2->V1的这个关系要写到邻接矩阵,首先先找到V1的列,然后在对应V2行的位置写上一个1,就可以了。

    网络

    网络是一个带权图。邻接矩阵如下图:

    有两种表示方法,没有边的两个顶点,可以用0表示,也可以用最大值表示。

    2.邻接表

    邻接矩阵是不错的一种图存储结构,但是,对于边数相对顶点较少的图,这种结构存在对存储空间的极大浪费。因此,找到一种数组与链表相结合的存储方法称为邻接表。

    邻接表的处理方法是这样的:
           1)图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过,数组可以较容易的读取顶点的信息,更加方便。
           2)图中每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以,用单链表存储,无向图称为顶点vi的边表,有向图则称为顶点vi作为弧尾的出边表(只管顶点的出边不管入边)。

    这里写图片描述

    从图中可以看出,顶点表的各个结点由data和firstedge两个域表示,data是数据域,存储顶点的信息,firstedge是指针域,指向边表的第一个结点,即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域,存储某顶点的邻接点在顶点表中的下标,next则存储指向边表中下一个结点的指针。

     

     

     

     

    更多相关内容
  • 图的邻接矩阵和邻接表实现, 深度搜索, 广度搜索, Dijstra最短路径
  • 领会图的两种主要存储结构、图基本运算算法两种遍历算法设计内容:编写一个程序,设计带权图的邻接矩阵邻接表的创建输出运算,并在此基础上设计一个主程序完成如下功能:(1)建立如图所示的有向图G的邻接矩阵...
  • 图的C++的邻接表和邻接矩阵完整实现,功能齐全,运行界面效果好
  • 图的邻接表 邻接矩阵表示的迪杰斯特拉算法 普里姆算法 克鲁斯卡尔算法 用c++实现 codeblocks编译通过
  • 严蔚敏《数据结构》中的图的邻接矩阵和邻接表的建立与输出,两种形式的C++代码,数据结构课写过的作业,基础的C++代码。
  • 图的存储方式2.1 邻接矩阵2.2 邻接表3.两种方式的比较 1. 基本概念 1.什么是图? 图由顶点和边组成,表示为G(V,E),其中G表示一个图,V是图G中顶点的集合,E是图G中边的集合。根据边是否有方向,可分为有向图...

    1. 基本概念

    1.什么是图?

    图由顶点和边组成,表示为G(V,E),其中G表示一个图,V是图G中顶点的集合,E是图G中边的集合。根据边是否有方向,可分为有向图和无向图。

    在这里插入图片描述

    2. 邻接点

    两结点之间通过边相连,则互为邻接点。如在上面的无向图中,(1,3),(2,5)等都为邻接点。

    3. 顶点的度

    顶点的度指的是与顶点v相连的边的数目。对于无向图来讲,只有度的概念,而对于有向图来讲,可分为入度出度。入度是指向该顶点的边的条数,出度是从该顶点发出的边的条数。上面的有向图中,顶点1的入度为1,出度为2。

    4. 权值

    表示从一个顶点到另一个顶点的距离或耗费。

    在这里插入图片描述
    5. 连通性

    对于两结点u,v,若通过u可到达v,则u和v是联通的。

    在图 G 中,任意的 结点vi,vj∈ V,有 vi,vj 连通,图 G 是连通的。

    在这里插入图片描述

    6. 连通分量

    图中的极大联通子图。

    2. 图的存储方式

    图有两种常用的存储方式——邻接矩阵和邻接表

    存储方式思想
    邻接矩阵用一维数组存储结点,二维数组(行数=列数)存储边等信息
    邻接表用一维数组存储结点,链表存储邻接点等信息

    2.1 邻接矩阵

    思想

    图的结点存储在一维数 组Vex[] 内,另外有一二维数组 Edge[][] 来存储结点到结点的信息:若结点Vex[i]到Vex[j]存在一条边,权值为w,则Edge[i][j]=w,否则,Edge[i][j]=∞。

    示意图

    在这里插入图片描述
    代码

    #include <iostream>
    #define INFINITY 99999
    #define MAX_VEX_NUM 20
    using namespace std;
    typedef char NumType;
    struct Graph
    {
        NumType Vex[MAX_VEX_NUM];
        int Edge[MAX_VEX_NUM][MAX_VEX_NUM];
        int VexNum;
        int EdgeNum;
    };
    int Locate(Graph G,NumType v)
    {
        int i;
        for(i=0;i<G.VexNum;i++)
            if(G.Vex[i]==v)return i;
        return -1;
    }
    void CreateGraph(Graph &G)
    {
        cout<<"请输入结点个数和边的条数:";
        cin>>G.VexNum;
        cin>>G.EdgeNum;
        int i,j,k;
        for(i=0;i<G.VexNum;i++)
            for(j=0;j<G.VexNum;j++)G.Edge[i][j]=INFINITY;
        cout<<"请输入顶点信息:";
        for(i=0;i<G.VexNum;i++)cin>>G.Vex[i];
        cout<<"请输入边和权值:";
        int w;
        NumType v1,v2;
        for(k=0;k<G.EdgeNum;k++)
        {
            cin>>v1;cin>>v2;cin>>w;
            i=Locate(G,v1);j=Locate(G,v2);
            G.Edge[i][j]=w;
            //若为无向图需要加入下面代码
            //G.Edge[j][i]=G.Edge[i][j];
        }
        for(i=0;i<G.VexNum;i++)
        {
            for(j=0;j<G.VexNum;j++)cout<<G.Edge[i][j]<<" ";
            cout<<endl;
        }
    }
    int main()
    {
        Graph G;
        CreateGraph(G);
        return 0;
    }
    
    

    2.2 邻接表

    思想

    图的结点使用一维数组Vex[]存储,邻接点用链表存储。

    示意图

    在这里插入图片描述
    代码

    #include <iostream>
    #define MAX_VEX_NUM 20
    using namespace std;
    typedef char NumType;
    struct EdgeNode
    {
        int adjvex;
        EdgeNode *nextedge;
    };
    struct VexNode
    {
        NumType data;
        EdgeNode *firstedgd;
    };
    struct Graph
    {
        VexNode Vex[MAX_VEX_NUM];
        int VexNum;
        int EdgeNum;
    };
    int Locate(Graph G,NumType v)
    {
        int i;
        for(i=0;i<G.VexNum;i++)
            if(G.Vex[i].data==v)return i;
        return -1;
    }
    void CreateGraph(Graph &G)
    {
        cout<<"请输入结点个数和边的条数:";
        cin>>G.VexNum;cin>>G.EdgeNum;
        int i,j,k;
        cout<<"请输入结点信息:";
        for(i=0;i<G.VexNum;i++){cin>>G.Vex[i].data;G.Vex[i].firstedgd=0;}
        NumType v1,v2;
        for(k=0;k<G.EdgeNum;k++)
        {
            cin>>v1;cin>>v2;
            i=Locate(G,v1);j=Locate(G,v2);
            EdgeNode *p=new EdgeNode();
            EdgeNode *p0=new EdgeNode();
            *p={j,G.Vex[i].firstedgd};
            G.Vex[i].firstedgd=p;
            //如果是无向图需要加入下面代码
            //*p0={i,G.Vex[j].firstedgd};
            //G.Vex[j].firstedgd=p0;
        }
    }
    int main()
    {
        cout << "Hello world!" << endl;
        return 0;
    }
    
    

    3.两种方式的比较

    对于一个具有n个顶点e条边的无向图,它的邻接表表示有n个顶点表结点2e个边表结点。

    对于一个具有n个顶点e条边的有向图,它的邻接表表示有n个顶点表结点e个边表结点。

    如果图中边的数目远远小于n2称作稀疏图,这是用邻接表表示比用邻接矩阵表示节省空间;

    如果图中边的数目接近于n2,对于无向图接近于n*(n-1)称作稠密图,考虑到邻接表中要附加链域,采用邻接矩阵表示法为宜。

    展开全文
  • 自行实现图的邻接矩阵和邻接表存储结构 邻接矩阵和邻接表类的实现及测试函数 功能全 代码易理解 可直接运行
  • (1)邻接矩阵 (2)邻接表(无向图) (3)其他 一、初识图 (1)图的定义 图(Graph)是由顶点的有穷非空集合(必须存在顶点)顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中...

    目录

    一、初识图

    (1)图的定义

    (2)图的分类

    二、图的存储结构

    (1)邻接矩阵

    (2)邻接表(无向图)

    (3)其他


    一、初识图

    (1)图的定义

             图(Graph)是由顶点的有穷非空集合(必须存在顶点)和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合

    (2)图的分类

            若顶点到顶点之间的边设有方向,则称这条边为无向边。如果图中任意两个顶点之间的边都是无向边,则称该图为无向图

            若顶点到顶点的边有方向,则称这条边为有向边,也称为弧。如果图中任意两个顶点之间的边都是有向边,则称该图为有向图

     除此之外还有:

    • 简单图
    • 无向完全图
    • 有向完全图
    • 稠密图
    • 带权图(网)
    • ...

    二、图的存储结构

    (1)邻接矩阵

            图的邻接矩阵存储方式是用二维数组来表示图,我们来看一个实例

           它的邻接矩阵为:

            简单解释一下,对于矩阵的主对角线的值,即arc[0][0]、arc[1][1]、arc[2[2]、arc[3][3],全为0是因为不存在顶点到自身的边,比如v_{0}v_{0}。arc[0][1]=1是因为v_{0}v_{1}的边存在,而arc[1][3]=0是因为v_{1}v_{3}的边不存在。并且由于是无向图,v_{1}v_{3}的边不存在,意味着v_{3}v_{1}的边也不存在。所以无向图的边数组是一个对称矩阵。

            有了这个矩阵,我们就可以很容易地知道图中的信息。

    1. 我们要知道某个顶点的度,其实就是这个顶点在邻接矩阵中第ⅰ行(或第i列)的元素之和。比如顶点1的度就是1+0+1+0=2。
    2. 求顶点M的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点。

            有向图的邻接矩阵也是一样

            而如果是带权图的话,如果两个顶点可达,那么我们就将arc[i][j]的1变为他们两点之间的权值,如果两个顶点之间不可达,那么我们就将arc[i][j]的0变为无穷大。这里需要注意自己到自己的权值为0。

     邻接矩阵(无向图)的实现:

    #include<iostream>
    using namespace std;
    
    #define MAXVEX 100//最大顶点数
    typedef char VertexType;//顶点类型
    typedef int EdgeType;//边上的权值类型
    typedef struct
    {
    	VertexType vexs[MAXVEX];//顶点表
    	EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵
    	int numVertexte;//当前顶点数
    	int numEdges;//当前边数
    }MGraph;
    
    void CreateMGraph(MGraph* G)//建立无向网图的邻接矩阵表示
    {
    	int i, j, k, w;
    	cout << "请输入顶点数和边数:" << endl;
    	cin >> G->numVertexte >> G->numEdges;
    	for ( i = 0; i < G->numVertexte; ++i)//读入顶点信息,建立顶点表
    	{
    		cin >> G->vexs[i];
    	}
    
    	for (i = 0; i < G->numVertexte; ++i)
    	{
    		for ( j = 0; j < G->numVertexte; ++j)
    		{
    			G->arc[i][j] = INT_MAX;//邻接矩阵初始化
    		}
    	}
    
    	for (k = 0; k < G->numEdges; ++k)
    	{
    		cout << "输入边(vi,vj)上的下标i,下标 j 和权 w:" << endl;
    		cin >> i >> j >> w;
    		G->arc[i][j] = w;
    		G->arc[j][i] = G->arc[i][j];
    	}
    }
    
    int main()
    {
    	MGraph G;
    	CreateMGraph(&G);
    	return 0;
    }

    (2)邻接表(无向图)

            邻接矩阵是不错的一种图存储结构,但是我们也发现,对于边数相对顶点较少的图,这种结构是存在对存储空间的极大浪费的。于是引出了链式存储的结构。

            邻接表的处理办法是这样。

    1. 图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过数组可以较容易地读取顶点信息,更加方便。另外,对于顶点数组中,每个数据元素还需要存储指向第一个邻接点的指针,以便于查找该顶点的边信息。
    2. 图中每个顶点的所有邻接点构成一个线性表,由于邻接点的个数不定,所以用单链表存储。

    例如

    无向图的邻接表

     有向图的邻接表

     对于带权值的网图

    邻接表(无向图)的实现

    #include<iostream>
    using namespace std;
    
    #define MAXVEX 100//最大顶点数
    typedef char VertexType;//顶点类型
    typedef int EdgeType;//边上的权值类型
    
    typedef struct EdgeNode
    {
    	int adjvex;//邻接点域,存储该顶点对应的下标
    	EdgeType weight;//用于存储权值,对于非网图可以不需要
    	struct EdgeNode* next;//指向下一个邻接点
    }EdgeNode;
    
    typedef struct VertexNode //顶点表结点
    {
    	VertexType data;//存储顶点信息
    	EdgeNode* firstedge;//指向该顶点的第一个相邻结点
    }VertexNode,AdjList[MAXVEX];
    
    typedef struct
    {
    	AdjList adjList;
    	int numVertexes;//当前顶点数
    	int numEdges;//当前边数
    }GraphAdjList;
    
    void CreateALGraph(GraphAdjList* G)//建立无向网图的邻接矩阵表示
    {
    	int i, j, k;
    	EdgeNode* e;
    	cout << "请输入顶点数和边数:" << endl;
    	cin >> G->numVertexes >> G->numEdges;
    	for ( i = 0; i < G->numVertexes; ++i)//读入顶点信息,建立顶点表
    	{
    		cin >> G->adjList[i].data;
    		G->adjList[i].firstedge = nullptr;
    	}
    
    	for (k = 0; k < G->numEdges; ++k)//建立邻接表
    	{
    		cout << "输入边(vi,vj)上的顶点序号:" << endl;
    		cin >> i >> j;
    		e = new EdgeNode;
    		e->adjvex = j;
    		e->next = G->adjList[i].firstedge;
    		G->adjList[i].firstedge = e;//头插法
    
    		e = new EdgeNode;
    		e->adjvex = i;
    		e->next = G->adjList[j].firstedge;
    		G->adjList[j].firstedge = e;//头插法
    	}
    }
    
    int main()
    {
    	GraphAdjList G;
    	CreateALGraph(&G);
    	return 0;
    }
    

    (3)其他

            除上述两种方法之外,图的存储方式还有十字链表,邻接多重表,边集数组等。

    展开全文
  • 图的储存方式有邻接矩阵 和邻接表 下面就是如何创建邻接矩阵和邻接表 这是邻接矩阵的无向图 /*构建领接矩阵 无向图*/ #include<iostream> #include<cstring> using namespace std; #define Max_int ...

    图的储存方式有邻接矩阵 和邻接表
    下面就是如何创建邻接矩阵和邻接表

    这是邻接矩阵的无向图
    在这里插入图片描述

    /*构建领接矩阵 无向图*/
    
    #include<iostream>
    #include<cstring>
    using namespace std;
    
    #define Max_int 32767//最大的数 无穷大 
    #define Mvnum 100
    bool visited[Mvnum];
    typedef struct {
    	char vexs[Mvnum];//vertex
    	int arc[Mvnum][Mvnum];
    	int vexnum;
    	int arcnum; 
    }AMGraph;// Adjacency Matrix 
    
    int LocateVex(AMGraph G,char e)
    {
    	int i;
    	for(i=0;i<G.vexnum;i++)
    	{
    		if(G.vexs[i]==e)
    		{
    			return i;
    		}
    	}
    	return -1;
    }
    
    void Create(AMGraph &G)
    {
    	
    	int i,j,k;
    
    	cout<<"请输入总顶点数: ";
    	cin>>G.vexnum;
    	cout<<endl;
    	
    	cout<<"请输入总边数:";
    	cin>>G.arcnum;
    	cout<<endl;
    	
    	cout<<"输入名称,列如a,A,b,B等"<<endl;
    	for(i=0;i<G.vexnum;i++)
    	{
    		cout<<"请输入第"<<i+1<<"个结点的名称:";
    		cin>>G.vexs[i];	 
    	 }
    	 
    	 for(i=0;i<G.vexnum;i++)
    	 {
    	 	for(j=0;j<G.vexnum;j++)
    	 	{
    	 		G.arc[i][j] = Max_int;//初始化为无穷大
    			  
    		 }
    	 }
    
    	 
    	 
    	 
    	 
    	cout<<"输入结点与结点之间边的权值列如 a b 5"<<endl;
    	for(k=0;k<G.arcnum;k++)
    	{
    		char e1,e2;
    		int w;
    		
    		cout<<"输入第"<<k+1<<"条边依附的顶点和权值:";
    		cin>>e1>>e2>>w;
    		
    		
    		
    		i=LocateVex(G,e1);
    		j=LocateVex(G,e2);
    		
    		G.arc[i][j]=w;
    		G.arc[j][i]=w;
    		
    	} 
    	 
    }
    
    int main()
    {
    	AMGraph G;
    	Create(G);
    	
    	int i,j;
    	cout<<"\t";
    	for(i=0;i<G.vexnum;i++)
    	{
    		cout<<G.vexs[i]<<"\t";
    	}
    	cout<<endl;
    	for(i=0;i<G.vexnum;i++)
    	{
    		cout<<G.vexs[i]<<"\t";
    		for(j=0;j<G.vexnum;j++)
    		{
    			if(G.arc[i][j]!=Max_int)
    			{
    				cout<<G.arc[i][j]<<"\t";
    			}
    			
    			else 
    			{
    				 
    				cout<<"∞\t"; 
    			} 
    		
    		}
    		cout<<endl;
    	}
    	
    		cout<<endl;
    	 
    } 
    

    这就是邻接矩阵的创建方法
    效果及输入
    在这里插入图片描述
    接下来就是邻接表
    在这里插入图片描述

    #include<iostream>
    using namespace std;
    
    #define Mvnum 100
    
    typedef struct ArcNode{//边结点 
    	int adjvex;
    	struct ArcNode *nextarc;
    	int info;//阔以存储与边相关的信息 比如权值 
    }ArcNode;
    
    typedef struct vNode{
    	char data;
    	ArcNode *firstarc ;//指向第一条依附该顶点的边 的指针
    	 
    }vNode,AdjList[Mvnum];
    
    typedef struct {
    	AdjList vertices;
    	int vexnum;
    	int arcnum;
    }ALGraph;
    
    int LocateVex(ALGraph G,char e)
    {
    	int i;
    	for(i=0;i<G.vexnum;i++)
    	{
    		if(G.vertices[i].data==e)
    		{
    			return i;
    		}
    	}
    	return -1;
    }
    
    
    void Create(ALGraph &G)
    {
    	
    	int i,j,k;
    
    	cout<<"请输入总顶点数: ";
    	cin>>G.vexnum;
    	cout<<endl;
    	
    	cout<<"请输入总边数:";
    	cin>>G.arcnum;
    	cout<<endl;
    	
    	cout<<"输入名称,列如a,A,b,B等"<<endl;
    	for(i=0;i<G.vexnum;i++)
    	{
    		cout<<"请输入第"<<i+1<<"个结点的名称:";
    		cin>>G.vertices[i].data;
    		G.vertices[i].firstarc=NULL;	 
    	 }
    	 
    	cout<<"输入结点与结点之间的边列如 a b"<<endl;
    	for(k=0;k<G.arcnum;k++)
    	{
    		char e1,e2;
    		int w;
    		cout<<"输入第"<<k+1<<"条边依附的顶点:";
    		cin>>e1>>e2;
    		
    		
    		i=LocateVex(G,e1);
    		j=LocateVex(G,e2);//这个是被连接   下面是头插法
    		 
    		
    		ArcNode *p1 = new ArcNode;//生成一个新的结点 
    		p1->adjvex = j;//新的结点的顶点就是被连接的顶点下表 
    		p1->nextarc = G.vertices[i].firstarc;//把这个结点插入到顶点的边表头部 
    		G.vertices[i].firstarc = p1;//
    		
    		ArcNode *p2 = new ArcNode;//双向绑定  因为这是无向图 
    		p2->adjvex = i;
    		p2->nextarc = G.vertices[j].firstarc;
    		G.vertices[j].firstarc = p2; 
    		
    	}
    	
    
    }
    int main()
    {
    	ALGraph G;
    	Create(G);
    	cout<<endl;
    	
    	cout<<"这是领接表创建的无向图:"<<endl;
    	int i;
    	
    	for(i=0;i<G.vexnum;i++)
    	{
    		vNode temp = G.vertices[i];
    		ArcNode *p = temp.firstarc;
    		if(p==NULL)
    		{
    			cout<<G.vertices[i].data;
    			cout<<endl;
    		}
    		
    		else{
    			
    			cout<<temp.data;
    			while(p){
    				
    				cout<<"->";
    				cout<<p->adjvex;
    				p=p->nextarc;
    			}
    		}
    		cout<<endl;
    	}
    	
    	return 0;
    } 
    
    

    效果如下在这里插入图片描述

    展开全文
  • 前言 因为工作的需要深刻认识到了数据结构的重要性,故现在重新学习...邻接表(无向图/有向图) 是顺序存储链式存储相结合的一种存储方式,使用于稀疏图,表删方式不唯一,时间复杂度低 邻接多重表(无向图) 十字.
  • 我们不叫顺序存储结构了,叫邻接矩阵邻接表和我们十字链有异曲同工之处,只不过邻接表的链表要多一点,好了话不多说我们开始学习吧!!! 每日一遍,防止颓废 1.邻接矩阵 官方术语: 邻接矩阵(Adjacency Matrix...
  • C语言实现图的邻接矩阵和邻接表存储,其中包含如下函数:CreateMat(MatGraph &g, int A[MAXV][MAXV], int n, int e):由边数组A、顶点数n和边数e创建图的邻接矩阵g。DispMat(MatGraph g):输出邻接矩阵g。...
  • //邻接矩阵 typedef struct{ int Vex[MaxNum]; //顶点 int edge[MaxNum][MaxNum]; //边 int arcnum,vexnum; //边顶点个数 }MGraph; //邻接表 typedef struct ArcNode{ int adjvex; struct ArcNode *...
  • //以下定义邻接矩阵类型 typedef struct { int no; //顶点编号 int info; //顶点其余的信息 }VertexType; typedef struct { int edges[MAXV][MAXV]; //邻接矩阵 int n,e; //顶点数,弧数 VertexType vexs[MAXV...
  • 一般图的表示方法为G(V,E),其中G表示graphic图,V表示点的集合,E表示边的集合,一般可以用邻接矩阵和邻接表来表示一个图 图的分类: 按照方向可以分为有向图无向图 按照权重可以分为带权图不带权图 邻接...
  • G的邻接矩阵是一个具有下列性质的n阶方阵:①对 无向图 而言,邻接矩阵一定是对称的,而且主对角线一定为零(在此仅讨论无向简单图),副对角线不一定为0, 有向图 则不一定如此。. ②在无向图中,任一顶点i的度为第...
  • 邻接矩阵的作用就是可以记录边与边之间的关系,如果是无向图那么矩阵存储的就是顶点的度;如果是有向图那么存储的就是出度。邻接矩阵的优点是可以快速达到两点之间边的关系,但是对于图中有多少条边,确定需要较多的...
  • 图的邻接矩阵存储方式是两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(即为邻接矩阵)存储图中的边或弧的信息 设图G有n个顶点,则邻接矩阵为一个n×n的方阵,定义为: 抽象数据类型如下 typedef ...
  • 图的表示形式:邻接矩阵和邻接表

    千次阅读 2021-03-21 08:48:40
    图是对象对象之间存在的关系的有限集合。如果将对象表示为顶点(或节点),将关系表示为边,则可以得到以下两种图形: ...邻接表 邻接矩阵 让我们考虑一个图,其中有从0到N-1编号的N个顶点(i,j)形式的E...
  • 图的邻接矩阵和邻接表的比较

    万次阅读 多人点赞 2018-08-16 15:39:11
    图的存储结构主要分两种,一种是邻接矩阵,一种是邻接表。1.邻接矩阵 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息。 设图G有n个顶点...
  • 邻接矩阵的优缺点 优点 判断是否邻接效率高 缺点 在稀疏的情况耗费空间 构造的过程耗费时间,为O(N^2) 在查找某节点的邻接对象时耗费时间,为O(N^2),且需要一个一个地判断 邻接链表的优缺点 优点 在查找某节点...
  • (3)熟练掌握图的邻接矩阵和邻接表的存储方法。 【实验准备】 编写一个程序,实现下图的邻接矩阵和邻接表存储。并求出每个顶点的度。 #include <stdio.h> #include <malloc.h> #include<...
  • 图 graph 顶点 vertex 弧 arc 弧尾 tail 弧头 head 有向图 digraph 边 edge 无向图 undigraph 权 weight 网 network 邻接点 adjacent 依附 incident 度 degree 出度 ... } 邻接矩阵和邻接表的关系
  • 存储图:邻接矩阵和邻接表

    千次阅读 2022-03-14 17:48:38
    用两个数组分别储存顶点表和邻接矩阵​​​​​​​ 构造无向网的邻接矩阵算法 邻接表 定义存储结构节点类型 构造邻接表算法 邻接表邻接矩阵间的关系 ...
  • 代码基于:【数据结构】【严蔚敏】【清华大学】【邻接矩阵和邻接表相互转换算法】 问题描述:该算法的设计,要求运行结果如下所示: 图 G 的邻接矩阵: 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0...
  • 邻接矩阵和邻接表的使用 邻接矩阵 为了遍历一个图,我们使用了邻接矩阵,及用 ai,ja_{i,j}ai,j​表示由a到b的边权 注:若这两个点不相连或 i=ji=ji=j,那么这个值就会设定为一个非正常的值,以便遍历时特判不走这条...
  • 邻接矩阵和邻接表空间问题

    千次阅读 2019-04-06 14:03:00
    在使用邻接表的时候,顶点数组中同时有数据域指针域,占用2N2N2N空间,边节点假设有2E2E2E个(每条边都会出现两次),每个边节点有存储节点序号的数据域指向下一个节点的指针域共占用4E4E4E块空间。故使用邻接矩阵...

空空如也

空空如也

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

邻接矩阵和邻接表

友情链接: VbTestDll.rar