图的基本术语及遍历.ppt

1、图的基本术语及遍历,图的基本术语及遍历,教学目的 1 了解图的基本概念 2 掌握图的存储结构及深度优先搜索和宽度优先搜索算法 教学内容 一 图的基本术语 二 图的存储结构 三 深度优先搜索 四 宽度优先搜索,一、图的基本术语 1、图的分类 2、图的属性 3、网,图的基本术语及遍历,图的基本术语图的分类 图: 图G由两个集合V（G）和E（G）组成，记作G=（ V，E） 其中V(G)是顶点的非空有穷集合 E(G)是边的有穷集合，而边是顶点的无序对或有序对。,图的基本术语及遍历,无向图: 在图中，若边是顶点的无序对，则称G为无向图。 有向图：若边是顶点的有序对，则称G为有向图。,图的基本术语及遍历,

2、图的基本术语图的分类 完全图：在n个顶点的无向图G中，若每 一顶点与其余n 一 1个顶点都有 边，则称G为完全图。,图的基本术语及遍历,有向完全图：在n个顶点的有向图中，若每一个顶点与其余n一1个顶点都 有弧存在，则称G为有向完全图，具有n (n-1)条弧。,图的基本术语及遍历,子图: 假设有两个图G和G,且满足： 且 则称G为G的子图。,图的基本术语及遍历,前三个图都是最后一个的子图。,图的基本术语图的属性 无向图的度: 在无向图中， 若（v1，v2） E（G）， 称 v1，v2 为邻接的，或称边（v1，v2 ）依附与顶点v1和v2。 依附于某顶点的边数叫作该点的度.,图的基本术语及遍历,度

3、是2,有向图的度: 在有向图中，以某顶点为尾的弧数叫该点的出度；以某顶点为头的弧数叫该点的入度。 出度和入度的和是该点的度。,图的基本术语及遍历,度为2,出度1,路径：在无向图G中从顶点vp到顶点vq的路径是一个顶点序列（vp,vi1,vi2,.，vin,vq），其中（vp, vi1）（vi1, vi2）,（vin, vq）是E（G）中的边。 路径长度：称路径上边的数目为路径长度。,图的基本术语及遍历,2到4的路径为2-3-4；长度为2,图的基本术语图的属性 连通图: 在无向图G中，若vi到vj有一条路径存在，则称vi到vj是连通的。若对于V（G）中每对顶点都连通，则称G为连通图。 连通分量：

4、在无向图中，极大连通子图称为连通分量。,图的基本术语及遍历,连通图,图的基本术语图的属性 强连通图： 在有向图G中，若对于V（G）中每一对不同的顶点都存在一条从vi到vj和vj 到vi的路径，则称G是强连通图。 强连通分量： 有向图中的极大强连通子图是它的强连通分量。,图的基本术语及遍历,若加上这条线就成强连通图了,图的基本术语图的属性 网：在图G中，若图的边带有权值，比如图的边上有表示从一个顶点到另一个顶点的距离或是花费，则称G为网。,图的基本术语及遍历,二、图的存储结构 1、邻接矩阵 2、邻接表,图的基本术语及遍历,图的存储结构邻接矩阵 设G=（V，E）是有n个顶点的图，G的邻接矩阵A（i

5、，j）是一个二维的nn数组，并具有下列性质：,图的基本术语及遍历,图的邻接矩阵,图的存储结构邻接矩阵 网的邻接矩阵可定义为：,图的基本术语及遍历,网的邻接矩阵,图的存储结构邻接表 邻接表：这种存储结构是对图中每个顶点建立一个单链表。第i个单链表中的每一个结点是依附于顶点vi的边(对有向图是以顶点vi为尾的弧)。,图的基本术语及遍历,该图邻接表,逆邻接表：对每个顶点vi建立一个以vi为头的弧的单链表,图的基本术语及遍历,逆邻接表,图的存储结构邻接表 另外，有向图的另一种链式存储结构，称为十字链表：把邻接表和逆邻接表揉到一起，建立一个十字链表。 无向图的另一种链式存储结构，称为邻接多重链表。,图的

6、基本术语及遍历,三、深度优先搜索 1、递归算法 2、非递归算法,图的基本术语及遍历,深度优先搜索递归算法 递归算法思想：首先从图G=(V,E)中某一顶点v0出发，访问任意一个和v0邻接的顶点w1，再从w1出发，再访问和w1邻接且未被访问过的任意顶点w2。然后，从w2出发进行如上访问。重复这个过程，直到某一个顶点的所有邻接点都被访问过时，回退到尚有邻接点未被访问过的顶点。再从该顶点出发，重复上述过程，直到所有顶点都被访问过为止。 例:,图的基本术语及遍历,图的基本术语及遍历,深度优先,2已经访问返回8,所有都访问完毕了,深度优先搜索非递归算法 非递归算法思想：由访问vi的邻接表转到访问vj的邻接

7、表时，vi进栈。从栈中依次弹出结点v0,访问v0的单链表中未被访问过的的结点，在访问过程中并重复上述的入栈过程 。过程如下页图示:,图的基本术语及遍历,非递归,图的基本术语及遍历,栈,非递归,图的基本术语及遍历,栈,非递归,图的基本术语及遍历,栈,非递归,图的基本术语及遍历,栈,非递归,图的基本术语及遍历,栈,5的邻接表空，回退8出栈,非递归,图的基本术语及遍历,栈,非递归,图的基本术语及遍历,栈,非递归,图的基本术语及遍历,栈,非递归,图的基本术语及遍历,栈,非递归,图的基本术语及遍历,栈,7的邻接表空，逐一退栈,四、宽度优先搜索 1、宽度优先搜索 2、图的连通分量,图的基本术语及遍历,宽度优先搜索算法 思想：设一先进先出的队Q，从v结点出发，访问v结点,再访问v的所有邻接点，并将所有邻接点入队。队头元素出队，设为a，接着访问a的所有邻接点，并将a的所有邻接点入队。队头元素出队，重复上述过程，直到队空。图示过程如下:,图的基本术语及遍历,宽度,图的基本术语及遍历,队,宽度,图的基本术语及遍历,队,宽度,图的基本术语及遍历,队,宽度,图的基本术语及遍历,队,宽度,图的基本术语及遍历,队,宽度,图的基本术语及遍历,队,宽度,图的基本术语及遍历,队,宽度,图的基本术语及遍历,队,宽度优