图的表示与遍历

· · 算法·理论

图的表示

1.图的定义

有向图

图G由顶点集V和边集E组成，记为G=(V,E)， 其中V(G)表示图G中顶点的有限非空集; E(G)表示图G中顶点之间的关系(边)集合。 若 V={v1,v½,…，v„}，则用|V表示图G中顶点的个数，也称图G的阶，E={(u,v)|u∈V,veV}， 用|E|表示图G中边的条数。

无向图

若E是有向边(也称弧)的有限集合时，则图G为有向图。 弧是顶点的有序对，记为<v, w>,其中 v,w是顶点，v称为弧尾，w称为弧头， <v,w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自 v。

2.一些概念

图中每个顶点的度定义为以该顶点为一个端点的边的数目。 对于无向图，顶点v的度是指依附于该顶点的边的条数，记为TD(v)。 在具有n个顶点、e条边的无向图中，TD(v)=2e，即无向图的全部顶点的度的和等于边i=1数的2倍，因为每条边和两个顶点相关联。 对于有向图,顶点v的度分为入度和出度,入度是以顶点v为终点的有向边的数目,记为ID(v);而出度是以顶点v为起点的有向边的数目，记为OD(v)。顶点v的度等于其入度和出度之和，即 TD(v) = ID(v) +OD(v)。 在具有n个顶点、e条边的有向图中，∑D(v)=∑0D(v) =e，即有向图的全部顶点的入度 之和与出度之和相等，并且等于边数。这是因为每条有向边都有一个起点和终点。

连通，连通图

在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。若图G中任意两个 顶点都是连通的，则称图G为连通图

强连通，强连通图

在有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是 强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图

边权与网

在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。

3.图的存储方式

邻接矩阵

所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息(即各顶点之间的邻接关系)，存储顶点之间邻接关系的二维数组称为邻接矩阵。 结点数为n的图G=(V,E)的邻接矩阵A是n*n的。将G的顶点编号为v_1,v_2,…, v_n。若(v„v)∈ E,则A[i][]=1，否则A[i][]=0。

对于带权图而言,若顶点v,和v之间有边相连，则邻接矩阵中对应项存放着该边对应的权值，若顶点 V和 V,不相连，则用∞来代表这两个顶点之间不存在边:

邻接表

当一个图为稀疏图时，使用邻接矩阵法显然要浪费大量的存储空间，而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。 所谓邻接表，是指对图G中的每个顶点v建立一个单链表，第i个单链表中的结点表示依附于顶点 v的边(对于有向图则是以顶点v为尾的弧)，这个单链表就称为顶点v;的边表(对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储(称为顶点表)，所以在邻接表中存在两种结点:顶点表结点和边表结点

顶点表结点由顶点域(data)和指向第一条邻接边的指针(firstarc) 构成，边表(邻接表)结点由邻接点域(adjvex)和指向下一条邻接边的指针域(nextarc)构成。

邻接表存储图的一些特点总结:

**①若G为无向图，则所需的存储空间为O(И+2|E|);若G为有向图，则所需的存储空间为

**②对于稀疏图，采用邻接表表示将极大地节省存储空间。** **③在邻接表中，给定一顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为$0(n)$。但是，若要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低。** **④ 在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数;但求其顶点的入度则需要遍历全部的邻接表。因此，也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然，这实际上与邻接表存储方式是类似的。** **⑤图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。** ## $$4.图的存储方式$$ **定义:图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。** - 广度优先遍历 广度优先搜索$(Breadth-First--Search,BFS)$类似于二叉树的层序遍历算法。基本思想是:首先访问起始顶点v,接着由v出发，依次访问v的各个未访问过的邻接顶点$w1,w2,wi$,然后依次访问$w1,w2，wi$,的所有未被访问过的邻接顶点;再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时图中尚有项点未被访问，则另选图中个未曾被访问的顶点作为始点，重复上述过程，直至图中所有项点都被访问到为止。 - 性能分析: 空间:无论是邻接表还是邻接矩阵的存储方式，$BFS$算法都需要借助一个辅助队列$Q,n$个顶点均需入队一次，在最坏的情况下，空间复杂度为$0(|V|)$。 时间:采用邻接表存储方式时，每个顶点均需搜索一次(或入队一次)，故时间复杂度为$0(|V|)$,在搜索任一顶点的邻接点时，每条边至少访问一次，故时间复杂度为$0(|E|)$，算法总的时间复杂度为$0(|V|+|E|)$。采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为$0(|V|)$,故算法总的时间复杂度为$0(|V|*|V|)$。 - 深度优先遍历 首先访问图中某一起始顶点$v$,然后由$v$出发，访问与v邻接且未被访问的任一顶点$w$,再访问与 $w$,邻接且未被访问的任一顶点$w2…$重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。 性能分析: 空间:需要借助一个$递归工作栈$，故其空间复杂度为$0(|V|)

时间:遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所用的存储结构。以邻接矩阵表示时，查找每个顶点的邻接点所需的时间为0(|V|),故总的时间复杂度为0(|v|*|V|)。以邻接表表示时，查找所有顶点的邻接点所需的时间为0(E),访问顶点所需的时间为0(|V|),此时，总的时间复杂度为0(|V|+|E|)。