数据结构严蔚敏7章图课件.ppt

1、返回返回7.1 图的定义和术语图的定义和术语第第7章章 图和广义表图和广义表7.2 图的存储结构图的存储结构7.3 图的遍历图的遍历7.4 连通图的最小生成树连通图的最小生成树7.5 单源最短路径单源最短路径7.6 拓朴排序拓朴排序7.7 关键路径关键路径*7.8 广义表广义表返回返回 图图(graph)是由一个是由一个顶点顶点(vertex)的有穷的有穷非空集非空集V(G)和一个和一个弧或边弧或边(arc)的集合的集合E(G)组成。记作组成。记作G=V,E.图又分为有向图和无向图图又分为有向图和无向图,图中的图中的顶点顶点即为即为数据元素数据元素。对有向图对有向图 没有箭头的出发端称为没有箭

2、头的出发端称为弧尾弧尾(tail)或或始点始点(initial)。带箭头的带箭头的终止端终止端称为称为弧头弧头(head)或或终点终点(terminal node)用有序对用有序对表示从表示从v到到w的一的一条弧。条弧。(如图中如图中）对无向图对无向图7.1 图的定义和术语图的定义和术语1 图的定义图的定义ABCDFEG(a)有向图有向图G1返回返回7.1 图的定义和术语图的定义和术语1 图的定义图的定义ACBEDF(b)无向图无向图G2 图图(graph)是由一个是由一个顶点顶点(vertex)的有穷的有穷非空集非空集V(G)和一个和一个弧或边弧或边(arc)的集合的集合E(G)组成。记作组

3、成。记作G=V,E.图又分为有向图和无向图图又分为有向图和无向图,图中的图中的顶点顶点即为即为数据元素数据元素。对有向图对有向图 没有箭头的出发端称为没有箭头的出发端称为弧尾弧尾(tail)或或始点始点(initial)。带箭头的带箭头的终止端终止端称为称为弧头弧头(head)或或终点终点(terminal node)用有序对用有序对表示从表示从v到到w的一的一条弧。条弧。(如图中如图中）对无向图对无向图,用用(v,w)表示一条边。表示一条边。如如(A,B)表示无向图表示无向图G2中的一条边。中的一条边。返回返回ACBEDF(b)无向图无向图G2图的表示图的表示 G1=(V1,E1)V1=A,

4、C,B,F,D,E,G E1=,(a)有向图有向图G1ABCDFEG G2=(V2,E2)V2=A,B,C,D,E,F E2=(A,B),(A,C),(B,C),(B,E),(B,F),(C,F),(C,D),(E,F),(C,F)返回返回 假设有两个图假设有两个图G=(V,E)和和G=(V,E),如果如果V V且且E E,则称则称G是是G的子图。的子图。可以证明可以证明,对于具有对于具有n个顶点的无向图的边和具有个顶点的无向图的边和具有n个个顶点的有向图的弧的最大数目分别为顶点的有向图的弧的最大数目分别为n(n-1)/2和和n(n-1)。称具有称具有n(n-1)/2条边的无向图为条边的无向图

5、为完全图完全图(completed grahp)。称具有称具有n(n-1)条弧的有向图为条弧的有向图为完全有向图完全有向图 称边或弧的数目称边或弧的数目enlogn的图为的图为稀疏图稀疏图(sparse graph),反之则称为反之则称为稠密图稠密图(dense graph)。子图子图2 几个常用术语几个常用术语ABCDFEGABFCDE返回返回 可以证明可以证明,对于具有对于具有n个顶点的无向图的边和具有个顶点的无向图的边和具有n个个顶点的有向图的弧的最大数目分别为顶点的有向图的弧的最大数目分别为n(n-1)/2和和n(n-1)。称具有称具有n(n-1)/2条边的无向图为条边的无向图为完全图

6、完全图(completed grahp)。称具有称具有n(n-1)条弧的有向图为条弧的有向图为完全有向图完全有向图 称边或弧的数目称边或弧的数目enlogn的图为的图为稀疏图稀疏图(sparse graph),反之则称为反之则称为稠密图稠密图(dense graph)。子图子图2 几个常用术语几个常用术语ACBEDFACDBEF 假设有两个图假设有两个图G=(V,E)和和G=(V,E),如果如果V V且且E E,则称则称G是是G的子图。的子图。返回返回度度、入度入度和和出度出度 若若uv是有向图中的一条弧是有向图中的一条弧,则称则称u邻接到邻接到v,或称或称v被被邻接到邻接到u。图中所邻接到顶

7、点图中所邻接到顶点v的弧的弧(即以它为弧头的弧即以它为弧头的弧)的数目的数目,称为顶点称为顶点v的的入度入度(indegree),记作记作ID(v);反之反之,从某顶点从某顶点u出发的弧出发的弧(即邻接自该顶点的弧即邻接自该顶点的弧),称为该顶点的称为该顶点的出度出度(outdegree),记作记作OD(u)。有向图中顶点有向图中顶点v的入度和出度之和的入度和出度之和称为该顶点的称为该顶点的总度总度,简称为简称为度度(degree),记作记作TD(v)ABCDFEG 如右所示的有向图如右所示的有向图 顶点顶点C邻接到顶点邻接到顶点E,vcvE ID(vc)=2OD(vc)=1TD(vc)=3返

8、回返回 无向图中顶点的度定义为与该顶点无向图中顶点的度定义为与该顶点相连的边的数目。相连的边的数目。如果顶点如果顶点vi的度记为的度记为TD(vi),则一个含则一个含n个顶点个顶点,e条边条边或弧的图或弧的图,满足如下关系满足如下关系ACBEDFTD(vB)=4 niivTDe1)(21度度、入度入度和和出度出度 若若uv是有向图中的一条弧是有向图中的一条弧,则称则称u邻接到邻接到v,或称或称v被被邻接到邻接到u。图中所邻接到顶点图中所邻接到顶点v的弧的弧(即以它为弧头的弧即以它为弧头的弧)的数目的数目,称为顶点称为顶点v的的入度入度(indegree),记作记作ID(v);反之反之,从某顶点

9、从某顶点u出发的弧出发的弧(即邻接自该顶点的弧即邻接自该顶点的弧),称为该顶点的称为该顶点的出度出度(outdegree),记作记作OD(u)。有向图中顶点有向图中顶点v的入度和出度之和的入度和出度之和称为该顶点的称为该顶点的总度总度,简称为简称为度度(degree),记作记作TD(v)返回返回路径和回路路径和回路 若有向图若有向图G中中k+1个顶点之间都有弧存在个顶点之间都有弧存在(即即,是图是图G中的弧中的弧),则这个顶点则这个顶点的序列的序列(v0,v1,.,vk)为从顶点为从顶点v0到顶点到顶点vk的一条的一条有向路径有向路径,路径中弧的数目定义为路径中弧的数目定义为路径长度路径长度。

10、若序列中的顶点都不相同若序列中的顶点都不相同,则称为则称为简单路径简单路径。(v0,v1,v2,v4,v1,v5,v6)是是v0到到v6的一条有向路径的一条有向路径(v0,v1,v5,v6)也是也是v0到到v6的一条有向路径的一条有向路径0123546简单路径简单路径返回返回路径和回路路径和回路 若有向图若有向图G中中k+1个顶点之间都有弧存在个顶点之间都有弧存在(即即,是图是图G中的弧中的弧),则这个顶点则这个顶点的序列的序列(v0,v1,.,vk)为从顶点为从顶点v0到顶点到顶点vk的一条的一条有向路径有向路径,路径中弧的数目定义为路径中弧的数目定义为路径长度路径长度。若序列中的顶点都不相

11、同若序列中的顶点都不相同,则称为则称为简单路径简单路径。对于对于无向图无向图,相邻顶点之间存在边的相邻顶点之间存在边的k+1个顶点序列个顶点序列构成一条长度为构成一条长度为k的的无向路径无向路径。(v0,v1,v2,v4,v5,v2,v3)是是v0到到v3的一条无向路径的一条无向路径(v0,v1,v2,v3)也是也是v0到到v3的一条有向路径的一条有向路径 如果如果v0和和vk是同一个顶点是同一个顶点,则是一条由某个顶点出发又回到该顶点的路径则是一条由某个顶点出发又回到该顶点的路径,称这种路称这种路径为径为回路回路或或环环(cycle).简单路径简单路径021435(v0,v1,v5,v2,v

12、0)是一条回路或环路是一条回路或环路返回返回连通图和连通分量连通图和连通分量 若若无向图无向图中任意两个顶点之间都中任意两个顶点之间都存在一条无向路径存在一条无向路径,则称该无向图为则称该无向图为连通图连通图。若若有向图有向图中任意两个顶点之间都存在一条有向路中任意两个顶点之间都存在一条有向路径径,则称该有向图为则称该有向图为强连通图强连通图。非非(强强)连通图中各个连通图中各个(强强)连通连通子图子图称为该图的称为该图的(强强)连通分量连通分量.连通图连通图非连通图非连通图ACBEDFABCDFEG强连通图强连通图非强连通图非强连通图2个连通分量个连通分量4个强连通分量个强连通分量返回返回带

13、权图和网带权图和网 边边(弧弧)上带有权值的图称为上带有权值的图称为网网。带权有向图带权有向图和和带权无向图带权无向图分别称为分别称为有向网和无向网有向网和无向网。102343 38 86 65 59 9有向网有向网返回返回图的基本操作图的基本操作 CreateGraph(&G,V,VR).BFSTraverse(G,v,visit()返回返回7.2 图的存储结构图的存储结构 1.图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示 2.图的邻接表存储表示图的邻接表存储表示 返回返回7.2 图的存储结构图的存储结构 7.2.1 图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示 无权图无权图

14、的邻接矩阵的定义的邻接矩阵的定义 设设G=(V,E)是具有是具有n(n0)个顶点的图个顶点的图,顶点的顺序顶点的顺序依次为依次为(v0,v1,vn-1),则则G的邻接矩阵的邻接矩阵A是是n阶方阵阶方阵A00 A01 A0n-1A10 A11 A1n-1 An-10 An-11 An-1n-1A=Aij=1 若若vi和和vj之间有弧或边存在之间有弧或边存在0 反之反之返回返回7.2 图的存储结构图的存储结构 7.2.1 图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示 网网的邻接矩阵的定义的邻接矩阵的定义 设设G=(V,E)是具有是具有n(n0)个顶点的带权图个顶点的带权图,顶点的顺顶点的顺

15、序依次为序依次为(v0,v1,vn-1),wij则是顶点则是顶点i和和j的弧的弧(边边)上的权值上的权值,则则G的邻接矩阵的邻接矩阵A是是n阶方阵阶方阵A00 A01 A0n-1A10 A11 A1n-1 An-10 An-11 An-1n-1A=Aij=wij若若vi和和vj之间有弧或边存在之间有弧或边存在反之反之返回返回G1v0v1v2v3v4v1v2v3v4v0(1)有向图的邻接矩阵有向图的邻接矩阵 0100100000110000110001010a.a.有向图的邻接矩阵一般是个稀疏矩阵有向图的邻接矩阵一般是个稀疏矩阵 12304b.b.第第i行非零元素的个数是顶点行非零元素的个数是顶

16、点vi的的的出度。的出度。c.c.第第j列非零元素的个数是顶点列非零元素的个数是顶点vj的的的入度。的入度。有向图邻接矩阵的几个特点有向图邻接矩阵的几个特点 返回返回v0v1v2v3v4v1v2v3v4v0(2)无向图的邻接矩阵无向图的邻接矩阵 0110110111110100110111010a.无向图的邻接矩阵是个对称矩阵无向图的邻接矩阵是个对称矩阵;b.第第i行非零元素的个数是顶点行非零元素的个数是顶点vi的度。的度。12304G2无向图邻接矩阵的几个特点无向图邻接矩阵的几个特点 返回返回v0v1v2v3v4v1v2v3v4v0(3)有向网的邻接矩阵有向网的邻接矩阵 9635810234

17、3 38 86 65 59 9有向网有向网返回返回一个图的邻接矩阵是唯一的一个图的邻接矩阵是唯一的 返回返回邻接矩阵的类型定义邻接矩阵的类型定义const INT_MAX=32767;const MAX_V=20;typedef int VRType;typedef int InforType;typedef int VertexType;typedef enum DG,DN,AG,AN GraphKind;typedef struct VRType adj;InforType*info;ArcCell,AdjMatrixMAX_VMAX_V;typedef struct VertexType

18、 vexMAX_V;AdjMatrix arcs;int vexnum,arcnum;GraphKind kind;MGraph;/设置设置“无穷大无穷大”值值/最大顶点数目最大顶点数目/图的种类图的种类/邻接矩阵类型邻接矩阵类型/顶点关系类型顶点关系类型/指向边或弧信息指向边或弧信息(如权值如权值)的指针的指针/顶点信息数组顶点信息数组(如顶点编号等如顶点编号等)/图的邻接矩阵图的邻接矩阵/图的顶点数和边图的顶点数和边(弧弧)的数目的数目/图的种类标志图的种类标志返回返回7.2.2 图的邻接表存储表示图的邻接表存储表示 邻接表是一种邻接表是一种链式链式存储表示方法，它类似于树的存储表示方法，

19、它类似于树的孩子链表。孩子链表。在邻接表中在邻接表中,对图中每个顶点建立对图中每个顶点建立一个单链表一个单链表,第第i个顶点的单链表的所有结点个顶点的单链表的所有结点,表示依附于顶点表示依附于顶点vi的边的边(或或以以vi为尾的弧为尾的弧)。每个单链表上附设一个表头结点。表。每个单链表上附设一个表头结点。表结点和表头结点的结构如下：结点和表头结点的结构如下：返回返回 (1)表结点的三个域表结点的三个域 adjvex 是个整形变量是个整形变量,指示与顶点指示与顶点vi邻接的顶点在邻接的顶点在表头数组中的存储位置表头数组中的存储位置(下标下标);nextarc 是指针型变量是指针型变量,指向下一条

20、边或弧的结点指向下一条边或弧的结点;Info存储与边或弧相关的信息存储与边或弧相关的信息,如权值等如权值等;(2)表头结点的两个域表头结点的两个域 data 存储顶点存储顶点vi的名称或编号等信息的名称或编号等信息;firstarc指向链表中第一个结点。指向链表中第一个结点。adjvexnextarcinfodatafirstarc表结点表结点表头结点表头结点返回返回adjvexnextarcinfodatafirstarc表结点表结点表头结点表头结点typedef struct ArcNode int adjvex;struct ArcNode*nextarc;InfoType*info;A

21、rcNode;typedef struct VertexType data;ArcNode*firstarc;VNode,AdjListMAX_V;typedef struct/图的邻接表类型图的邻接表类型 AdjList vertices;/存储图中所有顶点的数组存储图中所有顶点的数组 int vexnum,arcnum;/存储图的顶点数目和边存储图的顶点数目和边(弧弧)的数目的数目 int kind;/图的种类标志图的种类标志 ALGraph;返回返回typedef struct ArcNode int adjvex;struct ArcNode*nextarc;InfoType*info

22、;ArcNode;typedef struct VertexType data;ArcNode*firstarc;VNode,AdjListMAX_V;typedef struct AdjList vertices;int vexnum,arcnum;int kind;ALGraph;ALGraph G;01MAX_V-1.G.verticesG.vexnumG.arcnumG.kinddata firstarc返回返回24 13 有向图的邻接表存储示意图有向图的邻接表存储示意图 01234ABCDE56FGMAX_V-1.有向图有向图G1ABCDFEG05123466 1 245 有向图有向

23、图G1的邻接表的邻接表注意：图的邻接表不注意：图的邻接表不是唯一的，因为与一是唯一的，因为与一个顶点相邻的边的顺个顶点相邻的边的顺序没有明确规定。序没有明确规定。在此规定：边的顺序在此规定：边的顺序号按相关顶点的顺序号按相关顶点的顺序号由小到大排定。号由小到大排定。返回返回042112 01234ABCDE56FGMAX_V-1.有向图有向图G1ABCDFEG05123461 3 5 有向图有向图G G的的逆逆邻接表邻接表表结点指表结点指针域链接针域链接的不是出的不是出边而是入边而是入边边.返回返回有向网有向网G3有向网的邻接表有向网的邻接表BACDE386591835 23 46 29 01

24、234ABCDEMAX_V-1.12034有向网有向网G3的邻接表的邻接表返回返回算法算法7.1 建立无向图的邻接表存储结构建立无向图的邻接表存储结构void CreateUDG(ALGraph&G)int i,j,k,IncInfo,v1,v2;ArcNode*pi,*pj;cin G.vexnum G.arcnum;/IncInfo;for(i=0;i G.verticesi.data;G.verticesi.firstarc=NULL;for(k=0;k v1 v2;i=LocateVex(G,v1);j=LocateVex(G,v2);pi=new ArcNode;pi-adjvex=

25、j;pi-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=pi;pj=new ArcNode;pj-adjvex=i;pj-nextarc=G.verticesj.firstarc;G.verticesj.firstarc=pj;/if(IncInfo)cin pj-info;pi-info=pj-info;/输入边的起、止顶点名称值输入边的起、止顶点名称值/确定确定v1,v2下标下标/输入顶点名称值输入顶点名称值/用头插法插入用头插法插入v1的相邻结点的相邻结点/用头插法插入用头插法插入v2的相邻结点的相邻结点返回返回typedef str

26、uct ArcNode int adjvex;struct ArcNode*nextarc;InfoType*info;ArcNode,*ArcNodeP;typedef struct VertexType data;ArcNode*firstarc;VNode,AdjListMAX_V;typedef struct AdjList vertices;int vexnum,arcnum;int kind;ALGraph;返回返回/算法算法 7.1的改进算法的改进算法(用尾插法建立无向图的邻接表用尾插法建立无向图的邻接表)void CreateUDG(ALGraph&G)int i,j,k;Ar

27、cNode*pi,*pj,*qi,*qj;VertexType vi,vj;cin G.vexnum G.arcnum;for(i=0;i G.verticesi.data;G.verticesi.firstarc=NULL;qi=new ArcNodePG.vexnum;qj=qi;for(i=0;iG.vexnum;i+)qii=NULL;for(k=0;kvivj;i=LocateVex(G,vi);j=LocateVex(G,vj);pi=new ArcNode;pi-adjvex=j;if(G.verticesi.firstarc=NULL)pi-nextarc=G.vertices

28、i.firstarc;G.verticesi.firstarc=pi;else pi-nextarc=qii-nextarc;qii-nextarc=pi;qii=pi;pj=new ArcNode;pj-adjvex=i;if(G.verticesj.firstarc=NULL)pj-nextarc=G.verticesj.firstarc;G.verticesj.firstarc=pj;else pj-nextarc=qjj-nextarc;qjj-nextarc=pj;qjj=pj;/for/CreateUDG返回返回/算法算法 7.1的改进算法的改进算法(用尾插法建立无向图的邻接表用尾

29、插法建立无向图的邻接表)void CreateUDG(ALGraph&G)int i,j,k;ArcNode*pi,*pj,*qi,*qj;VertexType vi,vj;cin G.vexnum G.arcnum;for(i=0;i G.verticesi.data;G.verticesi.firstarc=NULL;qi=new ArcNodePG.vexnum;qj=qi;for(i=0;iG.vexnum;i+)qii=NULL;.返回返回/算法算法 7.1的改进算法的改进算法(用尾插法建立无向图的邻接表用尾插法建立无向图的邻接表)void CreateUDG(ALGraph&G).

30、for(k=0;kvivj;/输入一条边的始点输入一条边的始点vi和终点和终点vj的名称值的名称值 i=LocateVex(G,vi);/确定确定vi的下标的下标 j=LocateVex(G,vj);/确定确定vj的下标的下标 pi=new ArcNode;pi-adjvex=j;if(G.verticesi.firstarc=NULL)pi-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=pi;else pi-nextarc=qii-nextarc;qii-nextarc=pi;qii=pi;.返回返回/算法算法 7.1的改进算法的改进算法

31、(用尾插法建立无向图的邻接表用尾插法建立无向图的邻接表)void CreateUDG(ALGraph&G).for(k=0;kadjvex=i;if(G.verticesj.firstarc=NULL)pj-nextarc=G.verticesj.firstarc;G.verticesj.firstarc=pj;else pj-nextarc=qjj-nextarc;qjj-nextarc=pj;qjj=pj;/for/CreateUDG返回返回/补充算法补充算法 7.1-1 确定顶点名称值为确定顶点名称值为v的存储下标的存储下标int LocateVex(ALGraph G,VertexTy

32、pe v)int i;for(i=0;i=G.vexnum)ErrorMessage(顶点名称值有错！顶点名称值有错！);return i;返回返回/补充算法补充算法 7.1-2 输出图的邻接表输出图的邻接表void DisplayGraph(ALGraph G)int i;ArcNode*p;cout当前图的邻接表为：当前图的邻接表为：endl;for(i=0;iG.vexnum;i+)couti“:”G.verticesi.data;/输出表头输出表头 p=G.verticesi.firstarc;while(p!=NULL)/输出与顶点输出与顶点i相邻的结点单链表相邻的结点单链表 cou

33、tadjvex;p=p-nextarc;cout1-2-31:2-0-2-32:3-0-1-53:4-0-1-84:5-5-6-75:6-2-46:7-4-77:8-4-68:9-3Press any key to continue无向图无向图G39231465870123456MAX_V-178.123456789123 023 015 018 567 24 47 67 3 返回返回7.3 图的遍历图的遍历(Graph Traversal)从给定图中某个指定的顶点从给定图中某个指定的顶点(称为初始点称为初始点)出发出发,沿着图的某条路径对图中其余顶点进行访问沿着图的某条路径对图中其余顶点进行

34、访问,且使每且使每个顶点仅被访问一次个顶点仅被访问一次,这一过程称为图的遍历这一过程称为图的遍历(graph traversal)。图的遍历方法有两种：图的遍历方法有两种：(1)深度优先搜索深度优先搜索(Depth First Search-DFS)(2)广度优先搜索广度优先搜索(Breadth First Search-BFS)。返回返回7.3.2 深度优先搜索遍历图深度优先搜索遍历图 图的深度优先搜索图的深度优先搜索(depth first search)类似于树的类似于树的先根遍历的推广，搜索过程是：先根遍历的推广，搜索过程是：(1)从图中某个初始顶点从图中某个初始顶点v出发出发,首先访

35、问该顶点首先访问该顶点v;(2)依次从它的各个未被访问的邻接顶点出发依次从它的各个未被访问的邻接顶点出发深度深度优先遍历图优先遍历图,直至图中所有和直至图中所有和v有路径相通的顶点都有路径相通的顶点都被访问到被访问到;(3)若尚有其它顶点未被访问若尚有其它顶点未被访问,则另选一个未被访则另选一个未被访问的邻接点作起始顶点问的邻接点作起始顶点;(4)重复上述过程重复上述过程,直到图中所有顶点都被访问到直到图中所有顶点都被访问到为止。为止。显然显然,遍历过程是个递归过程。遍历过程是个递归过程。BFS返回返回/算法算法 7.4 从邻接表头下标为从邻接表头下标为v的顶点从发的顶点从发,递归地深度递归地

36、深度/优先遍历图优先遍历图G。void DFS(ALGraph G,int v)int w;ArcNode*p;visitedv=true;coutG.verticesv.datanextarc)w=p-adjvex;if(!visitedw)DFS(G,w);/对对v的未访问的邻接顶点的未访问的邻接顶点w进行进行DFS /DFS返回返回/主函数调用实例主函数调用实例int i;ALGraph G;CreateUDG(G);visited=new boolG.vexnum;for(i=0;iG.vexnum;i+)visitedi=false;DisplayGraph(G);cout深度优先搜

37、索的顶点序列为深度优先搜索的顶点序列为1-2-31:2-0-2-32:3-0-1-53:4-0-1-84:5-5-6-75:6-2-46:7-4-77:8-4-68:9-3深度优先搜索的顶点序列为深度优先搜索的顶点序列为3,1,2,4,9,6,5,7,8,Press any key to continue注意注意 课本课本P209正数第四行正数第四行给出的给出的DFS结果有误！结果有误！返回返回无向图无向图G3无向图的深度优先搜索手工操作过程举例无向图的深度优先搜索手工操作过程举例1 923146587v3v1v2v4v9v6v5v7v8注：课本注：课本P209正数第正数第4行给出行给出的的D

38、FS遍历序列不正确。遍历序列不正确。返回返回无向图的深度优先搜索手工操作过程举例无向图的深度优先搜索手工操作过程举例2 A无向图无向图G2ACBEDFBCDEF 程序验证程序验证 6个顶点的输入次序为个顶点的输入次序为:A,B,C,D,E,F 9条边的输入次序为条边的输入次序为:A-B,A-C,B-C,B-E,B-F,C-D,C-E,C-F,E-F 算法运行结果如下算法运行结果如下返回返回输入顶点数目和边的数目输入顶点数目和边的数目:6 9输入第输入第1个顶点的值个顶点的值:A.输入第输入第6个顶点的值个顶点的值:F请输入第请输入第1条边的起止顶点值条边的起止顶点值:A B.请输入第请输入第9

39、条边的起止顶点值条边的起止顶点值:E F当前图的邻接表为：当前图的邻接表为：0:A-1-21:B-0-2-4-52:C-0-1-3-4-53:D-24:E-1-2-55:F-1-2-4深度优先搜索的顶点序列为深度优先搜索的顶点序列为A,B,C,D,E,F,Press any key to continue无向图无向图G2ACBEDF返回返回有向图的深度优先搜索过程有向图的深度优先搜索过程 v0v1v2v4v3得到的遍历序列得到的遍历序列:结束结束以以v0为初始顶点为初始顶点有向图有向图10234返回返回7.3.2 广度优先搜索广度优先搜索(BFS)遍历图遍历图 广度优先搜索广度优先搜索(bre

40、adth first search)的基本思想是：的基本思想是：从图中某顶点从图中某顶点v出发出发,在访问了在访问了v之后依次访问之后依次访问v的各个的各个未曾访问过的未曾访问过的邻接点邻接点,然后分别从这些然后分别从这些邻接点出发邻接点出发依次访依次访问它们的问它们的邻接点邻接点,并使得并使得“先被访问的顶点的邻接点先被访问的顶点的邻接点”先先于于“后被访问的顶点的邻接点后被访问的顶点的邻接点”被访问被访问,直至图中所有已直至图中所有已被访问的顶点的邻接点都被访问到。被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问若此时图中尚有顶点未被访问,则需则需另选另选一个未曾被一个未曾被访问

41、的顶点作为访问的顶点作为新的起始点新的起始点,重复上述过程重复上述过程,直至图中所有直至图中所有顶点都被访问到为止。顶点都被访问到为止。为存储已被访问过的顶点为存储已被访问过的顶点,需附设一个队列。需附设一个队列。BFS过程类似于树的按层次遍历过程类似于树的按层次遍历,返回返回fv1fif(!visitedv)visitedv=TRUE;VisitFunc(G.vexsv);EnQueue_Sq(Q,v);while(!QueueEmpty_Sq(Q)DeQueue_Sq(Q,u);for(w=0;wG.vexnum;w+;)if(G.arcsu,w.adj&!visitedw)visited

42、w=TRUE;VisitFunc(w);EnQueue_Sq(Q,w);/if /while /if923146587rv3v3ru=v3w=0frv11v2rv22 3 45v6rv6v1v4rv4ffv5rv5fv9rv9fv7rv7v8rv8fff队列为空，遍历结束队列为空，遍历结束返回返回fv1f923146587rv3v3rfrv1v2rv2v6rv6v4rv4ffv5rv5fv9rv9fv7rv7v8rv8fff队列为空，遍历结束队列为空，遍历结束返回返回12304无向图无向图无向图的广度优先搜索遍历过程无向图的广度优先搜索遍历过程 2 1 304得到的遍历序列得到的遍历序列:以为

43、以为v2初始顶点初始顶点134rf0队列队列队列为空，遍历结束队列为空，遍历结束返回返回有向图的广度优先搜索遍历过程有向图的广度优先搜索遍历过程 0 1 342得到的遍历序列得到的遍历序列:以以v0为初始顶点为初始顶点132rf4队列队列有向图有向图10234rrfrfrff队列为空，遍历结束队列为空，遍历结束返回返回7.4 连通网的最小生成树连通网的最小生成树 1.生成树生成树(Spanning Tree)在一个含有在一个含有n个顶点的连通图中个顶点的连通图中,必能选出必能选出n-1条边条边构成一个构成一个极小连通子图极小连通子图,它含有图中全部它含有图中全部n个顶点个顶点,但只但只有足以构

44、成一棵树的有足以构成一棵树的n-1条边条边,称这颗树为连通图的生称这颗树为连通图的生成树。成树。极小连通子图极小连通子图:若删除极小连通子图的任意一条边若删除极小连通子图的任意一条边,该图就成为非连通图该图就成为非连通图,若在极小连通子图中增加一条边若在极小连通子图中增加一条边,必定构成一个环。必定构成一个环。对一个连通图进行一次深度优先搜索或广度优先对一个连通图进行一次深度优先搜索或广度优先搜索得到的顶点集合及相关边的集合就构成图搜索得到的顶点集合及相关边的集合就构成图G的一的一个生成树个生成树(DFS生成树或生成树或BFS生成树生成树)一个连通图的生成树不是唯一的。一个连通图的生成树不是唯

45、一的。返回返回bacdefg1012167653428914(a)连通网连通网bacdefg1676329(b)权值总和为权值总和为43的生成树的生成树bacdefg1273428(c)权值总和为权值总和为36的生成树的生成树bacdefg10121642814(d)权值总和为权值总和为64的生成树的生成树 一个连通网的所有生成树中一个连通网的所有生成树中,具有权值总和最小的具有权值总和最小的生成树称为连通网的生成树称为连通网的最小生成树最小生成树返回返回 如何构造一个带权无向连通图的最小生成如何构造一个带权无向连通图的最小生成树？树？1.克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法 2.普

46、里姆普里姆(Prim)算法。算法。问题问题返回返回 1.克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法 克鲁斯卡尔算法的基本思想为：克鲁斯卡尔算法的基本思想为：为使生成树上的总权为使生成树上的总权值之和达最小值之和达最小,应使每一条边的上的仅值尽可能小应使每一条边的上的仅值尽可能小,自然应自然应从权值最小的边选起从权值最小的边选起,直至选出直至选出n-1条权值最小的边为止。条权值最小的边为止。然而这然而这n-1条边必须不构成回路。因此并非每一条居条边必须不构成回路。因此并非每一条居当前权值最小的边都可选。当前权值最小的边都可选。返回返回 首先构造只含首先构造只含n个个顶点的森林顶点的森林,然后

47、依权值从小到大从连通网中选择边加入然后依权值从小到大从连通网中选择边加入到森林中去到森林中去,并使森林中不产生回路并使森林中不产生回路,直至森林变成一颗树直至森林变成一颗树为止。为止。1287421012167653428914 1.克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法 克鲁斯卡尔算法的具体做法如下：克鲁斯卡尔算法的具体做法如下：bacdefgbacdefg3克鲁斯卡尔算法构造的最小生成树克鲁斯卡尔算法构造的最小生成树返回返回54321 首先构造只含首先构造只含n个个顶点的森林顶点的森林,然后依权值从小到大从连通网中选择边加入然后依权值从小到大从连通网中选择边加入到森林中去到森林中去

48、,并使森林中不产生回路并使森林中不产生回路,直至森林变成一颗树直至森林变成一颗树为止。为止。1.克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法 克鲁斯卡尔算法的具体做法如下：克鲁斯卡尔算法的具体做法如下：0615636135425524013542返回返回 首先选取图中任意一个顶首先选取图中任意一个顶点点v作为生成树的根作为生成树的根,之后继续往生成树中添加顶点之后继续往生成树中添加顶点w,则在则在顶点顶点w和和v之间必须有边之间必须有边,且该边上的权值应在所有和且该边上的权值应在所有和v相邻相邻接的边中属最小接的边中属最小.2.普里姆普里姆(Prim)算法算法 普里姆算法的基本思想为：普里姆

49、算法的基本思想为：返回返回 2.普里姆普里姆(Prim)算法算法 普里姆算法的具体做法如下：普里姆算法的具体做法如下：从具有从具有n个顶点的连通网个顶点的连通网G=(V,E)中找出最小生成树中找出最小生成树T=(U,TE)的步骤如下：的步骤如下：1.选选G中任一顶点中任一顶点v为起点为起点,初始化初始化U=v,将将v与与V-U中所有相邻顶点构成的边加入候选边集中所有相邻顶点构成的边加入候选边集E,重复以下步骤重复以下步骤,直到全部直到全部n个顶点都加入到个顶点都加入到U中为止。中为止。将将E中中最小最小权值的边加入权值的边加入TE,并将该边在并将该边在V-U中的中的顶点顶点vk加入加入U中中,

50、同时将同时将vk从从V-U中删除。中删除。考查考查vk与与V-U中所有相邻顶点构成的边中所有相邻顶点构成的边,若边若边(vk,vj)的权小于的权小于E中边中边(vu,vj)的权的权,则用则用(vk,vj)取而代之取而代之;若若E不不存在与存在与vj关联的边关联的边,则将则将(vk,vj)加入加入E中中。返回返回2,g1012167653428914bacdefgU=V=V-U=E(候选边直接在原图中标出候选边直接在原图中标出)a,b,c,d,e,f,ga b,c,d,e,f,g(a,b):12,bV-U=(b,f):7,fg(f,e):2,eg,dg,c(e,d):4(d,c):3g(e,g)