1、2图图 u图是由顶点集合图是由顶点集合 V 及顶点间的关系集合及顶点间的关系集合 E 所组成所组成的一种数据结构：的一种数据结构：Graph 其中：其中：V=x|x 某个数据对象某个数据对象 是是非空的非空的有限顶点集合；有限顶点集合；E=(x,y)|x,y V /边边(Edge)的集合的集合 或或 E=|x,y V /弧弧(Arc)的集合的集合 是顶点之间关系的有限集合。是顶点之间关系的有限集合。在线性表中，元素个数可以为零，称为空表；在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。在图中
2、，顶点个数不能为零，但可以没有边。3无向图无向图u无向图无向图 G 是由两个集合是由两个集合 V(G)和和 E(G)组成的组成的 其中：其中：V(G)是顶点的非空有限集；是顶点的非空有限集；E(G)是边的有限集合，边是顶点的无序对，是边的有限集合，边是顶点的无序对，记为（记为（v,w）或（）或（w,v)，并且（，并且（v,w)=(w,v)有向图有向图u有向图有向图 G 是由两个集合是由两个集合 V(G)和和 E(G)组成的组成的 其中：其中：V(G)是顶点的非空有限集；是顶点的非空有限集；E(G)是有向边（也称弧）的有限集合，弧是有向边（也称弧）的有限集合，弧是顶点的有序对，记为是顶点的有序对
3、，记为，v,w是顶点，是顶点，v 为弧为弧尾尾(或始点或始点)，w 为弧头为弧头(终点终点)，。4例例u无向图无向图G1V(G1)=1,2,3,4,5,6,7E(G1)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)u有向图有向图G2V(G2)=1,2,3,4,5,6 E(G2)=,245136G2157324G165图的抽象数据类型图的抽象数据类型class Graph public:Graph();/建立一个空图建立一个空图 void InsertVertex(Type&vertex);void InsertEdge(int v1,int v2);voi
4、d RemoveVertex(int v);void RemoveEdge(int v1,int v2);int IsEmpty();Type GetWeight(int v1,int v2);int GetFirstNeighbor(int v);int GetNextNeighbor(int v1,int v2);6邻接点（或相邻点，关联）邻接点（或相邻点，关联）u如果如果 e=(u,v)是是 E(G)中的一条边，则称中的一条边，则称 u 与与 v 互互为邻接点或相邻点；称边为邻接点或相邻点；称边 e 与顶点与顶点 u,v 关联；关联；u如果如果 a=是是 E(G)中的一条弧，则称中的一条
5、弧，则称 u 邻接到邻接到v 或或 v 邻接于邻接于 u；称弧；称弧 a 与顶点与顶点u,v关联。关联。在线性结构中，数据元素之间仅具有线性关系；在线性结构中，数据元素之间仅具有线性关系；在树结构中，结点之间具有层次关系；在树结构中，结点之间具有层次关系；在图结构中，任意两个顶点之间都可能有关系。在图结构中，任意两个顶点之间都可能有关系。FECBAD线性结构线性结构ABCDEF树结构树结构V1V2V3V4V5图结构图结构不同结构中逻辑关系的对比不同结构中逻辑关系的对比在线性结构中，元素之间的关系为在线性结构中，元素之间的关系为和和；在树结构中，结点之间的关系为在树结构中，结点之间的关系为和和；
6、在图结构中，顶点之间的关系为在图结构中，顶点之间的关系为。FECBAD线性结构线性结构ABCDEF树结构树结构V1V2V3V4V5图结构图结构不同结构中逻辑关系的对比不同结构中逻辑关系的对比9权权u与图的边或弧相关的数。与图的边或弧相关的数。网网u带权的无向图称为无向网；带权的无向图称为无向网；u带权的有向图称为有向网。带权的有向图称为有向网。有向网有向网无向网无向网10顶点的度（与树中结点的度不同）顶点的度（与树中结点的度不同）u无向图中，顶点的度是与每个顶点关联的边数，无向图中，顶点的度是与每个顶点关联的边数，记作记作 TD(v)。u有向图中，顶点的度分成入度与出度有向图中，顶点的度分成入
7、度与出度入度：以该顶点为终头的弧的数目，记为入度：以该顶点为终头的弧的数目，记为 ID(v)出度：以该顶点为始点的弧的数目，记为出度：以该顶点为始点的弧的数目，记为 OD(v)一个顶点的度等于该顶点的入度与出度之和，即一个顶点的度等于该顶点的入度与出度之和，即TD(v)=OD(v)+ID(v)niivTDe1)(21evODvIDniinii11)()(11自环自环u称边称边(v,v)E(G)或弧或弧 E(G)为自环为自环 多重边（或弧）多重边（或弧）u若在若在 G 中有两条或两条以上相同的边或弧，称之中有两条或两条以上相同的边或弧，称之为多重边（或弧）为多重边（或弧）12简单图简单图u图中不
8、含有自环和多重边（或弧）的图称为简单图中不含有自环和多重边（或弧）的图称为简单图，否则称为非简单图。图，否则称为非简单图。u本章只讨论简单图，即有两类图形不在本章讨论本章只讨论简单图，即有两类图形不在本章讨论之列之列13完全图完全图 u若有若有 n 个顶点的无向图有个顶点的无向图有 n(n-1)/2 条边，则此图为条边，则此图为完全无向图。完全无向图。u若有若有 n 个顶点的有向图有个顶点的有向图有n(n-1)条边，则此图为完条边，则此图为完全有向图。全有向图。稀疏图（稀疏图（sparse graph）u边或弧很少的图，通常边数边或弧很少的图，通常边数 enlog2n稠密图（稠密图（Dense
9、 graph）u无向图中，边数接近无向图中，边数接近n(n-1)/2；u有向图中，弧数接近有向图中，弧数接近n(n-1)。14路径路径u在图在图 G 中，顶点序列中，顶点序列(vi1,vi2,vim)且且(vij,vij+1)E 或或 E，j=1,2,m-1，则称此序列为，则称此序列为从顶点从顶点 vi1 到顶点到顶点vim的一条路径。的一条路径。u顶点顶点 vi1 称为始点；顶点称为始点；顶点vim 称为终点。称为终点。回路回路u始点和终点相同的路径。始点和终点相同的路径。15简单路径简单路径u序列中顶点不重复出现的路径。序列中顶点不重复出现的路径。简单回路简单回路u始点和终点相同的简单路径
10、。始点和终点相同的简单路径。16路径长度路径长度 u无权图的路径长度是指此路径上边（或弧）的条无权图的路径长度是指此路径上边（或弧）的条数。数。u带权图的路径长度是指路径上各边（或弧）的权带权图的路径长度是指路径上各边（或弧）的权之和。之和。17子图子图u已知图已知图 G(V,E)和图和图 G(V,E)。若。若VV 且且 EE，则称，则称 G 为为 G 的子图。的子图。18连通图连通图u在无向图中，在无向图中，若从顶点若从顶点v1到顶点到顶点v2有路径，则称有路径，则称顶点顶点v1与与v2是连通的。是连通的。u图中任意两个顶点都连通的无向图称为连通图。图中任意两个顶点都连通的无向图称为连通图。
11、连通分量连通分量u非连通图中极大连通子图称做连通分量。非连通图中极大连通子图称做连通分量。1.1.含有极大含有极大顶点顶点数；数；2.2.依附于这些顶点的所有依附于这些顶点的所有边边。19例例ABCDEFGIJLHMKABCDEHMFGIJLK3个连通分量个连通分量 20强连通图与强连通分量强连通图与强连通分量u在有向图中，若对于每一对顶点在有向图中，若对于每一对顶点 vi 和和 vj，都存在，都存在一条从一条从 vi 到到 vj 和从和从 vj 到到 vi 的有向路径，则称此图的有向路径，则称此图是强连通图。是强连通图。u非强连通图的极大强连通子图称做强连通分量。非强连通图的极大强连通子图称
12、做强连通分量。V1V2V3V4V1V3V4V22个强连通分量个强连通分量 21生成树生成树un个顶点的连通图的生成树是包含图中全部个顶点的连通图的生成树是包含图中全部 n 个顶个顶点的一个极小连通子图；点的一个极小连通子图；ABCDEHM无向图无向图G ABCDEHM无向图无向图G的生成树的生成树 多多构成回路构成回路少少不连通不连通含有含有n-1条边条边22生成森林生成森林u由若干棵生成树组成，含全部顶点，但构成这些由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。树的边是最少的。FGIJLK生成森林生成森林ABCDEFGIJLHMK无向图无向图GABCDEHM23是否可以采用顺序存
13、储结构存储图是否可以采用顺序存储结构存储图?u图的特点：顶点之间的关系是图的特点：顶点之间的关系是m:n，即任何两个顶，即任何两个顶点之间都可能存在关系（边），无法通过存储位点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图置表示这种任意的逻辑关系，所以，图无法无法采用采用顺序存储结构。顺序存储结构。如何存储图如何存储图?u考虑图的定义，图是由顶点和边组成的，分别考考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。虑如何存储顶点、如何存储边。24邻接矩阵（邻接矩阵（Adjacency Matrix）u在图的邻接矩阵表示中在图的邻接矩阵表示中有一个记
14、录各个顶点信息的有一个记录各个顶点信息的顶点表顶点表（一维数组）（一维数组）还有一个表示各个顶点之间还有一个表示各个顶点之间邻接邻接关系的关系的邻接矩阵邻接矩阵u设图设图 G=(V,E)是一个有是一个有 n 个顶点的图，则个顶点的图，则 G 的的邻接矩阵定义如下邻接矩阵定义如下 Aij=1 若若(vi,vj)E 或或 E 0 反之反之25u例，无向图的邻接矩阵例，无向图的邻接矩阵V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V426u例，有向图的邻接矩阵例，有向图的邻接矩阵V1V2V
15、3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V427u从邻接矩阵中可以反映图的许多特征从邻接矩阵中可以反映图的许多特征无向图无向图l(1)对称矩阵（可采用压缩存储）；对称矩阵（可采用压缩存储）；l(2)每一行（或列）每一行（或列）1的个数是该顶点的度；的个数是该顶点的度；l(3)主对角线全为主对角线全为0（简单图）。（简单图）。有向图有向图l(1)每一行每一行1的个数是该顶点的出度；的个数是该顶点的出度；l(2)每一列每一列1的个数是该顶点的入度；的个数是该顶点的入度；l(3)主对角线全为主
16、对角线全为0（简单图）；（简单图）；l(4)有向图的邻接矩阵不一定对称。有向图的邻接矩阵不一定对称。28u带权图的邻接矩阵带权图的邻接矩阵Aij 0 i=j 其它其它 wij 若若(vi,vj)E 或或 E 29u用邻接矩阵表示的图的类的定义用邻接矩阵表示的图的类的定义 class AdjMatrix /非带权图非带权图 int n；/顶点的个数顶点的个数 int matrixMaxSize MaxSize；/邻接矩阵邻接矩阵 public:AdjMatrix(int m)n=m；;/AdjMatrix class AdjMatrix /带权图带权图 const int INFINITE=；i
17、nt n；/顶点的个数顶点的个数 float matrixMaxSizeMaxSize；/邻接矩阵邻接矩阵 public:AdjMatrix(int m)n=m；;/AdjMatrix30class AdjGraph AdjMatrix*adj；DataType*elem；public:AdjGraph(int m)adj=new AdjMatrix(m)；elm=new DataSet(m)；void CreateGraph();/建立一个图建立一个图G的邻接矩阵的邻接矩阵Matrixint LocateVex(v);/确定图确定图G中顶点中顶点v在顶点中的位置在顶点中的位置 DataTyp
18、e GetVex(v);/得到图得到图G中顶点中顶点v的值的值int FirstAdjVex(v);/确定图确定图G中顶点中顶点v的第一个邻接点的第一个邻接点 int NextAdjVex(v,w);/确定图确定图G中顶点中顶点v相对于相对于w的下一个的下一个邻接点邻接点 void DFSTraverse(int v)；/图图的深度优先遍历的深度优先遍历 void BFSTraverse(int v)；/图图的的广度优先遍历广度优先遍历;/AdjGraph31u邻接矩阵的优点邻接矩阵的优点容易实现图的操作，如：求某顶点的度、判断顶点之间容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（
19、弧）、找顶点的邻接点等等。是否有边（弧）、找顶点的邻接点等等。u邻接矩阵的缺点邻接矩阵的缺点n 个顶点需要个顶点需要 nn 个单元存储边；空间效率为个单元存储边；空间效率为O(n2)。对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。32邻接表（邻接表（Adjacency List）表示法）表示法u无向图的邻接表无向图的邻接表为每个顶点建立一个单链表为每个顶点建立一个单链表第第 i 个单链表中的结点表示与顶点个单链表中的结点表示与顶点 vi 所关联的所有边所关联的所有边AEDCBACBED10011243243404321注：邻接表不唯一，因各个边结点的链入顺序是任意的。注：邻接表不唯一，因
20、各个边结点的链入顺序是任意的。33问题问题l在无向图的邻接表中，如何求每个顶点的度？在无向图的邻接表中，如何求每个顶点的度？第第 i 个链表中的边结点个数是顶点个链表中的边结点个数是顶点 i 的度的度l若顶点数为若顶点数为 n，边数为，边数为 e 时，则在无向图的邻接表中时，则在无向图的邻接表中共需多少个结点？共需多少个结点？n 个顶点结点，个顶点结点，2e 个边结点个边结点 34u有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表在有向图的邻接表中，第在有向图的邻接表中，第 i 个单链表链接的弧都是顶点个单链表链接的弧都是顶点vi发出的，也称做发出的，也称做出边表出边表。在有向图的逆邻接表中，
21、第在有向图的逆邻接表中，第 i 个单链表链接的弧都是进个单链表链接的弧都是进入顶点入顶点 vi 的，也称做的，也称做入边表入边表。v1v2v3v4V4V3V2V12301V4V3V2V13020邻接表邻接表逆邻接表逆邻接表01230123 用邻接表或逆邻接表表示有向图时，只需用邻接表或逆邻接表表示有向图时，只需 n 个顶点结点，个顶点结点，e 个弧结点。个弧结点。35data：结：结点的数据域，保存点的数据域，保存顶顶点的数据值。点的数据值。firstout：结点的指针域，指向与该结点的指针域，指向与该顶顶点相关联的第一条边点相关联的第一条边 （弧）（弧）的地址的地址表头结点表头结点dataf
22、irstoutadjvexlink边边/弧结点弧结点adjvex：该边或弧所指向的顶点的序号：该边或弧所指向的顶点的序号link：指向下一条边或弧的指针：指向下一条边或弧的指针adjvexlinkdatafirstout36u网（带权图）的邻接表网（带权图）的邻接表边边/弧结点弧结点adjvexcostlink37u邻接表表示的图的类定义邻接表表示的图的类定义class EArcNode /边边(或弧或弧)结点结点 int adjvex；/该边或弧所指向的顶点的序号该边或弧所指向的顶点的序号EArcNode*link；/指向下一条边或弧的指针指向下一条边或弧的指针 public:EArcNod
23、e(int adj)adjvex=adj;link=NULL;friend class LinkGraph;/EArcNodeclass VNode /表头结点表头结点 DataType data；/顶点的信息顶点的信息 EArcNode *firstout；/指向与该顶点关联的第一条边指向与该顶点关联的第一条边(弧弧)public:VNode(DataType e)data=e;f irstout=NULL;friend class LinkGraph;/VNode38class LinkGraph /邻接表邻接表 int n；/顶点的个数顶点的个数 VNode gheadMaxSize；/
24、邻接表邻接表 public:LinkGraph(int m)n=m；void CreateGraph()；/建立图建立图g int LocateVex(v)；/得到顶点得到顶点v在图中的序号在图中的序号 DataType GetVex(v)；/得到顶点得到顶点v的值的值 int FirstAdjVex(v)；/得到顶点得到顶点v的第一个邻接顶点的第一个邻接顶点 int NextAdjVex(v,w);/确定图确定图G中顶点中顶点v相对于相对于w的下一的下一个邻接点个邻接点 void DFSTraverse(int v)；/图的深度优先遍历图的深度优先遍历 void BFSTraverse(in
25、t v)；/图的广度优先遍历图的广度优先遍历;/LinkGraph39u图的操作在邻接表的上的实现图的操作在邻接表的上的实现 int FirstAdjVex(int v)return gheadv-firstout.adjvex；/FirstAdjVex int NextAdjVex(int v，int w)p=gheadv-firstout；while(p&p-adjVex!=w)p=p-link；if(!p|!p-link)return 0；else return p-link-adjVex；/NextAdjVex40讨论：邻接表与邻接矩阵的比较讨论：邻接表与邻接矩阵的比较u联系联系都可以
26、用来存储有向图和无向图；都可以用来存储有向图和无向图；邻接表中每个链表对应于邻接矩阵中的一行，链表中结邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。点个数等于一行中非零元素的个数。41u区别区别对于任一确定的无向图，邻接矩阵是唯一的（行列号与对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。号无关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(n2)，而邻接表的空间复杂度，而邻接表的空间复杂度为为O(n+e)。邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠
27、密图的存储（e接近接近n(n-1)/2）；而邻）；而邻接表多用于稀疏图的存储（接表多用于稀疏图的存储（en2）。）。42图的遍历图的遍历u从图中某一顶点出发，按照某种搜索路径访问图从图中某一顶点出发，按照某种搜索路径访问图中所有的顶点，使得每个顶点被访问一次且仅被中所有的顶点，使得每个顶点被访问一次且仅被访问一次。访问一次。图的遍历操作要解决的关键问题图的遍历操作要解决的关键问题u在图中，如何选取遍历的起始顶点？在图中，如何选取遍历的起始顶点？解决方案：解决方案：从编号小的顶点开始从编号小的顶点开始 43u从某个起点开始可能到达不了所有其它顶点，怎从某个起点开始可能到达不了所有其它顶点，怎么办
28、？么办？解决方案：解决方案：多次调用从某顶点出发遍历图的算法。多次调用从某顶点出发遍历图的算法。u图中可能存在回路，某些顶点可能会被重复访问，图中可能存在回路，某些顶点可能会被重复访问，如何避免遍历因回路而陷入死循环。如何避免遍历因回路而陷入死循环。解决方案：解决方案：附设访问标志数组附设访问标志数组visitedn u在图中，一个顶点可以和其它多个顶点相连，当在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问后，如何选取下一个要访问的顶这样的顶点访问后，如何选取下一个要访问的顶点？点？解决方案：解决方案：深度深度优先遍历和优先遍历和广度广度优先遍历优先遍历44深度优先遍历深度优先遍历D
29、FS（Depth First Search）DFS算法思想算法思想u从图中某个顶点从图中某个顶点V0 出发，访问此顶点，然后依次出发，访问此顶点，然后依次从从V0的各个未被访问的邻接点出发深度优先搜索的各个未被访问的邻接点出发深度优先搜索遍历图，直至遍历图，直至V0 的所有邻接点都被访问到。的所有邻接点都被访问到。u若此时图中尚有顶点未被访问，则另选图中一个若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。至图中所有顶点都被访问到为止。45例例46u从访问图中某一起始点从访问图中某一起始点
30、 v 开始，由开始，由 v 出发，访问它出发，访问它的第一邻接点的第一邻接点 w1；再从；再从 w1 出发，访问与出发，访问与 w1邻接邻接但还没有访问过的顶点但还没有访问过的顶点 w2；然后再从；然后再从 w2 出发，出发，进行类似的访问，进行类似的访问，如此进行下去，直到某一顶如此进行下去，直到某一顶点所有的邻接点都被访问完。点所有的邻接点都被访问完。u退回到上一步刚访问过的顶点，看是否还有其它退回到上一步刚访问过的顶点，看是否还有其它没有被访问的邻接点。如果有，则访问此顶点，没有被访问的邻接点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；之后再从此顶点出发，进行与前述
31、类似的访问；如果没有，就再退回一步进行搜索。如果没有，就再退回一步进行搜索。u重复上述过程，直到连通图中所有顶点都被访问重复上述过程，直到连通图中所有顶点都被访问过为止。过为止。47连通图的深度优先遍历算法连通图的深度优先遍历算法void DFSTraverse()/深度优先求图的连通分量深度优先求图的连通分量 int visitedn；/设置访问标志数组设置访问标志数组 for(v=0;vn;v+)visitedv=0；/初始化访问标志数组初始化访问标志数组 for(v=0;vn;v+)if(!visitedv)DFS(v)；/每次从尚未访问过的顶点出发每次从尚未访问过的顶点出发/DFSTr
32、aversevoid DFS(int v)/从顶点从顶点v出发访问包含该顶点的最大连通子图中的所有顶点出发访问包含该顶点的最大连通子图中的所有顶点 visitedv=1；visit(v)；for(w=firstAdjVex(v);w;w=nextAdjVex(v,w)if(!visitedw)DFS(w)；/DFS48例，深度优先遍历序列，入栈序列，出栈序列。例，深度优先遍历序列，入栈序列，出栈序列。V1V3V2V4V5V6V7V8深一层递归深一层递归递归返回递归返回 V1遍历序列：遍历序列：V2 V4 V549例，深度优先遍历序列，入栈序列，出栈序列。例，深度优先遍历序列，入栈序列，出栈序列
33、。V1V3V2V4V5V6V7V8深一层递归深一层递归递归返回递归返回 V1遍历序列：遍历序列：V2 V4 V850例，深度优先遍历序列，入栈序列，出栈序列。例，深度优先遍历序列，入栈序列，出栈序列。V1V3V2V4V5V6V7V8深一层递归深一层递归递归返回递归返回 V1遍历序列：遍历序列：V2 V451例，深度优先遍历序列，入栈序列，出栈序列。例，深度优先遍历序列，入栈序列，出栈序列。V1V3V2V4V5V6V7V8深一层递归深一层递归递归返回递归返回 V1遍历序列：遍历序列：V7 V3 V652u不同存储结构下的不同存储结构下的DFS实现实现图以邻接矩阵存储图以邻接矩阵存储 void D
34、FS(int v)visitedv=1;visit(v);for(w=0;w0)if(!visitedw)DFS(w);/DFS图以邻接表存储图以邻接表存储void DFS(int v)visitedv=1;p=gheadv-firstout;while(p)w=p-adjvex;if(!visitedw)DFS(w);p=p-link;/DFS53例例V1V2V4V5V3V7V6V8例例01231342data firstout 1 6 7 2adjvex link45 5 3 716785676深度遍历：深度遍历：V1V3 V7 V6 V2 V4 V8 V554算法分析算法分析u图中有图中
35、有 n 个顶点，个顶点，e 条边。条边。u如果用邻接矩阵存储图，则查找每一个顶点的所如果用邻接矩阵存储图，则查找每一个顶点的所有的边，所需时间为有的边，所需时间为O(n)，则遍历图中所有的顶点，则遍历图中所有的顶点所需的时间为所需的时间为O(n2)。u如果用邻接表存储图，在每一个单链如果用邻接表存储图，在每一个单链 表中可以找表中可以找到某个顶点到某个顶点 v 的所有邻接顶点的所有邻接顶点 w。由于总共有。由于总共有 2e 个边结点个边结点(无向图无向图)，所以扫描边的时间为，所以扫描边的时间为O(e)。而。而且对所有顶点递归访问且对所有顶点递归访问1次，所以遍历图的时间复次，所以遍历图的时间
36、复杂性为杂性为O(n+e)。55广度优先遍历广度优先遍历BFS（Breadth First Search）思路思路u在访问了起始顶点在访问了起始顶点 v 之后，由之后，由 v 出发，依次访问出发，依次访问 v 的所有未被访问过的邻接点的所有未被访问过的邻接点 w1,w2,wt，然后，然后再顺序访问再顺序访问 w1,w2,wt 的所有未被访问过的邻的所有未被访问过的邻接点。再从这些访问过的顶点出发，再访问它们接点。再从这些访问过的顶点出发，再访问它们的所有未被访问过的邻接点，的所有未被访问过的邻接点，如此重复，直，如此重复，直到图中所有顶点都被访问完为止。到图中所有顶点都被访问完为止。56例例
37、57说明说明u广度优先遍历是一种分层的搜索过程，每向前走广度优先遍历是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先遍历不是一个有往回退的情况。因此，广度优先遍历不是一个递归的过程，其算法也不是递归的。递归的过程，其算法也不是递归的。u为了实现逐层访问，算法中使用了一个队列，以为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的顶点，以便向下一层访问。记忆正在访问的顶点，以便向下一层访问。u与深度优先遍历过程一样，为避免重复访问，需与深度优先遍历过程一样，为避免重复访问，需要一个辅助数组要一个辅
38、助数组 visited n，对被访问过的顶点加，对被访问过的顶点加以标记。以标记。58算法思想算法思想u1）清队列）清队列Q；u2）对出发顶点）对出发顶点 v 做做v 入队；标记入队；标记 v；u3）当）当 Q 不空反复做：不空反复做：出队头元素到出队头元素到 u；访问访问 u；将将 u 的每个未被访问的邻接点的每个未被访问的邻接点 w 入队；标记入队；标记 w。59广度优先搜索算法广度优先搜索算法void BFS(int v)/广度优先求图的连通分量广度优先求图的连通分量 Q=new Queue()；/清队列清队列Q Q.Enter(v)；/每次从尚未访问过的顶点中选取一个顶点每次从尚未访问
39、过的顶点中选取一个顶点v visitedv=1；/标记标记v while(!Q.Empty()/Q不空不空 u=Q.Leave()；/出队头元素到出队头元素到u visited(u)；/访问访问u for(w=FirstAdjVex(u);w;w=NextAdjVex(u,w)if(!visitedw)Q.Enter(w)；/将将u的每个未被访问的邻接点的每个未被访问的邻接点w 入队入队 visitedw=1；/BFS60uBFS从出发点只能遍历一个连通分量，若对任意图从出发点只能遍历一个连通分量，若对任意图的遍历需要对每个分量中一个未被访问的顶点为的遍历需要对每个分量中一个未被访问的顶点为出
40、发点进行出发点进行BFS遍历。遍历。void BFSTraverse()/广度优先求图的连通分量广度优先求图的连通分量 int visitedn；/设置访问标志数组设置访问标志数组 for(v=0；vn；v+)visitedv=0；/初始化访问标志初始化访问标志 for(v=0；vn；v+)if(!visitedv)BFS(v)；/BFSTraverse61例，广度优先遍历序列，入队序列，出队序列。例，广度优先遍历序列，入队序列，出队序列。V1V3V2V4V5V6V7V8遍历序列：遍历序列：V5V6V7V8V4V1V2V362算法分析算法分析u如果用邻接矩阵存储图，则对于每一个被访问过如果用邻
41、接矩阵存储图，则对于每一个被访问过的顶点，循环要检测矩阵中的的顶点，循环要检测矩阵中的 n 个元素，总的时个元素，总的时间代价为间代价为O(n2)。u如果用邻接表存储图，则循环的总时间代价为如果用邻接表存储图，则循环的总时间代价为 D0+D1+Dn-1=O(e)，其中的，其中的 Di 是顶点是顶点 i 的的度。而且对所有顶点访问度。而且对所有顶点访问1次，所以遍历图的时间次，所以遍历图的时间复杂性为复杂性为O(n+e)。63DFS 与与 BFS 之比较之比较u空间复杂度相同，都是空间复杂度相同，都是O(n)（借用了堆栈或队列）；（借用了堆栈或队列）；u时间复杂度只与存储结构（邻接矩阵或邻接表）
42、时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。有关，而与搜索路径无关。64生成树生成树u包含连通无向图中全部顶点的极小连通子图（包含连通无向图中全部顶点的极小连通子图（n 个个顶点、顶点、n-1 条边）条边）u一个连通图的生成树不唯一一个连通图的生成树不唯一使用不同的遍历图的方法，可以得到不同的生成树使用不同的遍历图的方法，可以得到不同的生成树从不同的顶点出发，也可能得到不同的生成树从不同的顶点出发，也可能得到不同的生成树u对于非连通图，通过图的遍历，得到的是生成森对于非连通图，通过图的遍历，得到的是生成森林林65例例（a）深度优先生成树深度优先生成树 （b）广度优先生成树
43、广度优先生成树V1V3V2V4V5V6V7V8V1V3V2V4V5V6V7V866最小生成树最小生成树MST（Minimum-cost Spanning Tree）u连通无向网中连通无向网中边权之和边权之和最小的生成树最小的生成树最小生成树最小生成树MST的典型用途的典型用途u假设在假设在 7 个城市之间要建立通信网络线，要求使得个城市之间要建立通信网络线，要求使得每个城市之间连通且费用最少。每个城市之间连通且费用最少。数学模型数学模型连通网连通网表示表示7个城市间的通信网个城市间的通信网l顶点顶点表示城市表示城市l边边表示城市间的通信线路表示城市间的通信线路l边的权值边的权值表示线路的经济代
44、价表示线路的经济代价281234567101614181225242267构造最小生成树的准则构造最小生成树的准则u必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；u必须使用且仅使用必须使用且仅使用 n-1 条边来连接网络中的条边来连接网络中的 n 个顶个顶点；点；u不能使用产生回路的边。不能使用产生回路的边。求一个连通无向网中最小生成树的方法求一个连通无向网中最小生成树的方法uPrim 算法算法uKruskal 算法算法都是利用都是利用MST的性质的性质构造最小生成树构造最小生成树68最小生成树的性质最小生成树的性质u若集合若集合 U 是集合是集合 V 的一个
45、非空子集，若的一个非空子集，若(u,v)是是一条具有最小权值的边，其中一条具有最小权值的边，其中 u U，v V-U；则：；则：(u,v)必在最小生成树上。必在最小生成树上。UV-U69Prim 算法算法uPrim 算法的基本思想算法的基本思想设连通设连通 N=V,E，T 是是 N 的最小生成树中边的集合，的最小生成树中边的集合，U 是生成树的顶点集合。是生成树的顶点集合。（1）T=，U=u （u 为任一顶点）；为任一顶点）；（2）在所有）在所有 uU，vV-U 的边的边(u,v)E 中找一条代中找一条代价最小的边价最小的边(u,v)加入集合加入集合 T 中，同时中，同时 v 加入加入 U；（
46、3）重复（）重复（2），直到），直到 U=V 为止。为止。70u例例0126345281612222510251418T=U=0 Min10,28=10(0,5),5Min25,28=25,(5,4),4Min28,25,22=22,(4,3),3Min28,25,18,12=12,(3,2),2Min28,25,18,16=16,(2,1),1Min25,18,14=14,(1,6),6 U=V，算法结束，算法结束71uPrim 算法的实现算法的实现图的存储：邻接矩阵图的存储：邻接矩阵在构造过程中，还设置了一个辅助数组在构造过程中，还设置了一个辅助数组closedge：l每个元素每个元素cl
47、osedgev有两个域有两个域 lowcost：存放生成树顶点集合内顶点到生成树外各顶点：存放生成树顶点集合内顶点到生成树外各顶点v的各边上的当前最小权值的各边上的当前最小权值 adjvex：记录生成树顶点集合外各顶点距离集合内哪个：记录生成树顶点集合外各顶点距离集合内哪个顶点最近（即权值最小）顶点最近（即权值最小）72u从顶点从顶点0出发利用出发利用Prim算法构造最小生成树过程中算法构造最小生成树过程中辅助数组各分量的值的变化辅助数组各分量的值的变化i1 23456closedgeadjvexlowcost0280000100525422424312318216i1 23456edgead
48、jvexlowcost1140123456U100000052501011422131212161114173u利用利用 Prim 算法求最小生成树的算法算法求最小生成树的算法class AddArray int adjvex;float lowcost;/AddArrayvoid MinSpanTree_Prim(int u,AddArray closedge,AddArray edge,AdjMatrix G)/设图以邻接矩阵存储，用设图以邻接矩阵存储，用Prim算法从顶点算法从顶点u出发构造网出发构造网G的的最小生成树且保存到数组最小生成树且保存到数组edge中中 for(v=0；vn；
49、v+)Uv=0；Uu=1；for(v=0；v n；v+)if（u!=v)closedgev.adjvex=u;74 closedgev.lowcost=G.matrixuv;for(t=1；tn；t+)/选择其余的选择其余的n-1个顶点个顶点 k=minimum(closedge)；/求出求出T的下一个顶点的下一个顶点k顶点顶点 u=closedgek.adjvex；edgek.lowcost=G.matrixku;/保存选中边的权值保存选中边的权值 edgek.adjvex=u;/保存选中边的顶点保存选中边的顶点 Uk=1；for(j=0；jG.matrixkj)closedgej.lowc
50、ost=G.matrixkj；closedgej.adjvex=k；/for /MinSpanTree_Prim75uPrime 算法分析算法分析设连通无向网有设连通无向网有 n 个顶点，则该算法的时间复杂度为个顶点，则该算法的时间复杂度为O(n2)适用于稠密的网络适用于稠密的网络76Kruscal 算法算法u基本思想基本思想 先构造一个只含先构造一个只含 n 个顶点、不含有边的零图个顶点、不含有边的零图 T，然后从，然后从权值最小的边开始，若它的添加不使权值最小的边开始，若它的添加不使 T 产生回路，则在产生回路，则在 T 上加上这条边，如此重复，直至加上上加上这条边，如此重复，直至加上 n
