注意:线性表可以是空表,树可以是空树,但是图不可以是空图,也就是说,图中不能一个顶点都没有,图的边集可以为空,但是图的顶点集一定不为空。
注:在国外教材中,有向图的边集一般用字母A来表示,A为arrow的首字母
极大连通子图为无向连通图的本身,极小连通子图为无向图的生成树。
考虑最极端的情况,这个非连通无向图由一个完全图加一个孤立的结点构成,即这e条边全部都在那个完全图里即:解方程解出一个N来,然后N+1加上一个孤立的结点,即为最后结果
TL;DR由顶点集和顶点集共同构成的图不是强连通图,原因如下:从顶点b出发可以经过路径bfg
抵达顶点g,但是从顶点g出发却没有一条路径可以抵达顶点b,所以顶点b和顶点g直接不是强连通的,所以由顶点集构成的图不为强连通图。
国外教材上一般把顶点的度记为,并且将入度记为,将出度记为,此处指明的TD即为Total Degree的缩写。
其中n为顶点的个数,e为边的条数。因为每条边都和两个顶点相互关联。
A[i][j]=1
的条件是图中存在边 A[i][j]=0
。对于带权图而言,当边存在时,其邻接矩阵的取值为当前边的权值,不存在时一般取 为什么使用上述语句而不直接使用如下的形式判断:1arcs[v][w] ? "Yes" : "No"Copied!上面的这种形式对于map来说是很不安全的,原因很简单,当这个map里面并没有这一项的时候,你使用上面的这种形式判断是否存在此项,map也会给你创建出一个来,也就是说即便你没有对map进行插入操作,你使用[]运算符判断是否存在,map也会给你把这一项创建出来。我们可以在STL的源代码里看到如下的代码:1template<class _Keyty,2class... _Mappedty>3_Pairib _Try_emplace(_Keyty&& _Keyval,4_Mappedty&&... _Mapval)5{ // fail if _Keyval present, else emplace6iterator _Where = _Mybase::lower_bound(_Keyval);7if (_Where == _Mybase::end()8|| _DEBUG_LT_PRED(_Mybase::_Getcomp(),9_Keyval, _Mybase::_Key(_Where._Ptr)))10return (_Pairib(11_Mybase::emplace_hint(_Where,12piecewise_construct,13_STD forward_as_tuple(14_STD forward<_Keyty>(_Keyval)),15_STD forward_as_tuple(16_STD forward<_Mappedty>(_Mapval)...)),17true));18else19return (_Pairib(_Where, false));20}21// 对其中的emplace_hint的代码如下:22template<class... _Valty>23iterator emplace_hint(const_iterator _Where, _Valty&&... _Val)24{ // insert value_type(_Val...) at _Where25_Nodeptr _Newnode = this->_Buynode(_STD forward<_Valty>(_Val)...);26return (_Insert_hint(_Where, _Newnode->_Myval, _Newnode));27}Copied!当判断条件_Where == _Mybase::end()
成立时,也就是当前map中并没有这一项时,他就会执行调用函数emplace_hint
在_Mybase::end()
处(使用默认构造函数)新建这一项。而且此时函数会返回新创建的这一项,多数情况下,我们仅仅是为了判断此项是否存在,而不希望其不存在时还要把这一项创建出来,所以判断key是否存在于map中,我们可以使用其find函数,检查其返回值是否等于map.end()
。
i
行的非零元素的个数恰好是图第i
个结点的度。i
行的非零元素的个数恰好是图第i
个结点的出度,第i
列的非零元素的个数恰好是图第i
个结点的入度。vector
本身就是一个可动态扩容的数组,其初始情况下默认分配一段较小的存储空间,随着存储规模的增长,其会动态扩容。这种方法严格意义上来说其实不能算为邻接表。ivex
和jvex
代表了当前边所连接的两个顶点,ilink
指向下一条依附于ivex
的边,jlink
指向下一条依附于jvex
的边。mark
标识域,即标记当前边有没有被搜索过,以及info
域,指向和边相关的各种信息。TL;DR如果对有向图也仅设0未访问,1访问过了这2种状态的话,对于上图左边的那个有向图而言,访问从0开始->1->2,这时0,1,2三个结点都被标记为了已访问,此时递归回溯到结点0,又从0开始访问2,这时2已经是已访问状态了,此时就会被错误地判定成有向图中存在环,而实际情况是有向图中不存在环。
dist
,其初始值为 dist
中,然后再依次抵达这些邻接点,再从这些邻接点开始继续访问下面的结点,每次访问将路径长度加起来,然后比较新的路径的路径长度与dist
存放的路径长度的大小,将小的那个放入dist
数组中,依次向下,直到走完了所有能抵达的目标顶点的路径,此时,dist
数组中存放的值即为最短路径。