今天鞋百科给各位分享无向图的存储空间怎么算的知识，其中也会对数据结构使用邻接矩阵和邻接表存储和计算有向图与无向图C语言程序进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在我们开始吧！

数据结构使用邻接矩阵和邻接表存储和计算有向图与无向图C语言程序

1352456545

设有一稀疏图G，则G采用什么存储较省空间

G采用邻接表存储较省空间。

邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。

对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。

扩展资料：

表示法

n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。(换句话说，每条边（i,j）在邻接表 中出现两次：一次在关于i的邻接表中，另一次在关于j的邻接表中)。

对于有向图，vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此，将有向图的邻接表称为出边表。对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。

参考资料：百度百科-邻接表

无论有向图还是无向图，顶点数n，边数e和度数之间有什么关系

总度数(D)等于边数(e)的两倍。

D=2e

图G的顶点数n和边数e的关系

1、若G是无向图，则0≤e≤n(n-1)/2。

恰有n(n-1)/2条边的无向图称无向完全图(Undireet-ed Complete Graph)。

2、若G是有向图，则0≤e≤n(n-1)。

恰有n(n-1)条边的有向图称为有向完全图(Directed Complete Graph)。

对于有向图最短路问题，计算步骤与求解无向图最短路问题相同，主要区别在于：无向图最短路问题使用单标号法。单标号法是对每一点赋予一个路权标号；而有向最短路问题使用双标号法．双标号法是对每一点赋予两个标号：路径和路权。

扩展资料对于有向图，情形就不同了，因为存在从u到v的路径，并不蕴涵也存在从v到u的路径。

设D是一个有向图，且u、v∈D，若存在从顶点u到顶点v的一条路径，则称从顶点v到顶点u可达。

可达的慨念与从u到v的各种路径的数目及路径的长度无关。另外，为了完备起见，规定任一顶点到达它自身的是可达的。

可达性是一个有向图顶点的二元关系，依照定义，它是自反的，且是传递的。一般来说，可达不是对称的，也不是反对称的。

[数据结构]已知无向图的邻接表，求所有的连通分量

图的邻接表存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。如词条概念图所示，表结点存放的是邻接顶点在数组中的索引。对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。

邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对图的每个顶点建立一个容器(n个顶点建立n个容器)，第i个容器中的结点包含顶点Vi的所有邻接顶点。实际上我们常用的邻接矩阵就是一种未离散化每个点的边集的邻接表。

在有向图中，描述每个点向别的节点连的边(点a->点b这种情况)。

在无向图中，描述每个点所有的边(点a-点b这种情况)

与邻接表相对应的存图方式叫做边集表，这种方法用一个容器存储所有的边。

工业上有很多非常好的图库的实现,例如C++的boost graph库.如果可以，尽量用这些库，这样可以大大提高你的效率。

表示法

注意:

n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。(换句话说，每条边(i,j)在邻接表 中出现两次:一次在关于i的邻接表中，另一次在关于j的邻接表中)

有向图

对于有向图，vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此，将有向图的邻接表称为出边表。

【例】有向图G6如下图所示，其中顶点v1的邻接表上两个表结点中的顶点序号分别为0和4，它们分别表示从v1射出的两条边(简称为v1的出边):和。

注意:

n个顶点e条边的有向图，它的邻接表表示中有n个顶点表结点和e个边表结点。(因为有向图是单向的)

逆邻接表

在有向图中，为图中每个顶点vi建立一个入边表的方法称逆邻接表表示法。

入边表中的每个表结点均对应一条以vi为终点(即射入vi)的边。

注意:

n个顶点e条边的有向图，它的逆邻接表表示中有n个顶点表结点和e个边表结点。

无向图的邻接矩阵是对称的是什么意思

可以这么理解:记邻接矩阵为A
如果顶点i和顶点j，有一条边，那么矩阵元素值A(i，j)和A(j，i)是一样的
所以A是对称的。

有6个顶点组成的无向图构成连通图，最少需要( )条边；当边的数目大于( )时，该图必定连通。

有6个顶点组成的无向图构成连通图，最少需要(5)条边；当边的数目大于(10)时，该图必定连通。

n个顶点e条边的图G用邻接表存储，则求每个顶点入度的时间复杂度为？查了好几个地方的答案，答案大部分

O(n+e)是对的，O(n*n)是用邻接矩阵存储时的时间复杂度。
算法就是遍历每一条边，然后把每条边的终点的入度+1.
在邻接表中，就是要依次访问每个顶点，然后在每个顶点中依次访问每条边，把这些边的终点的入度+1。也就是每个顶点和每条边依次要各访问一遍，所以时间复杂度是O(n+e)。
在邻接矩阵中，算法需要遍历邻接矩阵的每一个点，而邻接矩阵有n*n个点，所以时间复杂度是O(n*n)。
有什么不懂的可以追问。