图论中搜索算法讲座

图论中搜索算法讲座第1页，共57页，2023年，2月20日，星期六图论中搜索算法和最短路径算法2第2页，共57页，2023年，2月20日，星期六ReadEuler,readEuler,heisthemasterofusall.

P.-S.deLaplace3第3页，共57页，2023年，2月20日，星期六4第4页，共57页，2023年，2月20日，星期六5第5页，共57页，2023年，2月20日，星期六§1图_基本概念§2图的存储结构

§4最短路径§3图的遍历算法内容6第6页，共57页，2023年，2月20日，星期六图是一种较线性表和树更为复杂的数据结构。线性表:

线性结构树:

层次结构图:

结点之间的关系可以是任意的，即图中任意两个数据元素之间都可能相关。如：

ABCDE第一节:图的基本概念7第7页，共57页，2023年，2月20日，星期六1图的定义和基本术语图G

是由两个集合—顶点集V(G)

和边集E(G)

组成的，记作G=(V(G)，E(G))，简称G=(V，E)。ABCDEABCDEABCDEV是顶点的有穷非空集合

E是两个顶点之间的关系，即边的有穷集合

8第8页，共57页，2023年，2月20日，星期六无向图和有向图无向图:

边是顶点的无序对，即边没有方向性。v1v2v3v5v4上面无向图可以表示为：G=(V,E),其中V={v1,v2,v3,v4,v5}E={(v1,v2)

,(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}(v1,v2)表示顶点v1和v2之间的边，(v1,v2)=(v2,v1)。9第9页，共57页，2023年，2月20日，星期六有向图:

其边是顶点的有序对，即边有方向性。v1v2v4v3V={v1,v2,v3,v4}E={<v1,v2>

,<v1,v3>,<v3,v4>,<v4,v1>,<v2,v1>}在有向图中，通常边称为弧，<v1,v2>表示顶点v1到v2的弧。称v1为弧尾，称v2为弧头。<v1,v2>≠<v2,v1>上面有向图可以表示为：G=(V,E),其中10第10页，共57页，2023年，2月20日，星期六带权无向图(无向网)和带权有向图(有向网)有时对图的边或弧赋予相关的数值，这种与图的边或弧相关的数值叫做权。

这种带权的图通常称为网。

带权的有向图称为有向网。带权的无向图称为无向网。ABCDE53821497这些权可以表示从一个顶点到另一个顶点的距离。可以表示从一个顶点到另一个顶点的耗费。11第11页，共57页，2023年，2月20日，星期六子图假设有两个图

G=(V,E)和

G’=(V’,E’)，如果

V’V，且

E’E，则称

G’

为

G

的子图。

v1v2v4v3求子图v1v1v3v1v4v3v1v2v4v3v1v2v4v312第12页，共57页，2023年，2月20日，星期六邻接与关联对于无向图

G=(V,E)，如果边

(v,v’)∈E，则称顶点

v和

v’互为邻接点，即

v

和

v’

相邻接。

边

(v,v’)依附于顶点

v和

v’，或者说

(v,v’)

与顶点

v

和

v’

相关联。

对于有向图

G=(V,E)，如果弧

<v,v’>∈E，则称顶点

v邻接到顶点

v’，顶点

v’邻接自顶点

v。

vv’vv’弧<v,v’>

和顶点v,v’

相关联。13第13页，共57页，2023年，2月20日，星期六顶点的度对于无向图，顶点

v的度是和

v相关联的边的数目，记做TD(v)。

v1v2v3v5v4顶点v3的度为

3对于有向图，顶点

v的度

TD(V)分为两部分——出度、入度。

以顶点

v为头的弧的数目称为

v的入度，记为ID(v)

；以顶点

v为尾的弧的数目称为

v的出度，记为OD(v)；

顶点

v的度为TD(v)=ID(v)+OD(v)。

14第14页，共57页，2023年，2月20日，星期六v1v2v4v3顶点v1

的出度为2顶点v1

的入度为1顶点v1

的度为315第15页，共57页，2023年，2月20日，星期六路径、链、简单路径、回路(环)、简单回路无向图G中若存在一条有穷非空序列w=v0e1

v1e2

v2

ek

vk

，其中vi和ei分别为顶点和边，则称w

是从顶点v0到vk的一条路径。…顶点v0和vk分别称为路径

w

的起点和终点。路径的长度是路径上的边的数目。v0v1v2vk-1vk...e1e2ek起点和终点相同的路径称为回路(环)。16第16页，共57页，2023年，2月20日，星期六若路径w的边e1,e2,,ek

互不相同，则称w为链。…若路径w的顶点v0,v1,,vk

互不相同，则称w为简单路径。…v0v1v2vk-1vk...e1e2ek链是否为简单路径?简单路径是否为链?不一定一定e1e2e3e4e5除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路(简单环)。17第17页，共57页，2023年，2月20日，星期六例157324G26路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，118第18页，共57页，2023年，2月20日，星期六有向图G中若存在一条有穷非空序列w=v0e1

v1e2

v2

ek

vk

，其中vi和ei分别为顶点和弧，则称w

是从顶点v0到vk的一条路径。…v0v1v2vk-1vk...e1e2ek链简单路径回路简单回路19第19页，共57页，2023年，2月20日，星期六例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，320第20页，共57页，2023年，2月20日，星期六连通、连通图无向图G，如果从顶点

v

到顶点

v’

有路径，则称

v

和

v’

是连通的。

如果对于无向图

G

中任意两个顶点

vi,vj

∈V,vi和

vj都是连通的，则称

G是连通图。

v1v2v3v5v4是否为连通图21第21页，共57页，2023年，2月20日，星期六第2节图的存储结构顺序存储邻接矩阵链式存储邻接表邻接多重表十字链表如何表达顶点之间存在的联系？v1v2v4v322第22页，共57页，2023年，2月20日，星期六2.1邻接矩阵设图G=(V，E)具有n(n≥1)个顶点v1,v2,,vn

和m

条边或弧e1,e2,,em

，则G的邻接矩阵是n×n

阶矩阵，记为A(G)

。……其每一个元素aij

定义为:邻接矩阵存放n

个顶点信息和n2

条边或弧信息。aij=01顶点vi与vj不相邻接顶点vi与vj相邻接v1v2v4v3例有向图GA(G)=12341234011000000001100023第23页，共57页，2023年，2月20日，星期六v1v2v3v5v4例无向图G0101010101010111010001100A(G)=1234512345优点:1.容易判断任意两个顶点之间是否有边或弧。2.容易求取各个顶点的度。24第24页，共57页，2023年，2月20日，星期六无向图，顶点vi

的度是邻接矩阵中第

i行或第

i列的元素之和。例G中，v1

的度为2。v1v2v3v5v4例无向图G0101010101010111010001100A(G)=123451234525第25页，共57页，2023年，2月20日，星期六v1v2v4v3例有向图GA(G)=123412340110000000011000有向图，顶点vi

的出度是邻接矩阵中第

i行的元素之和。顶点vi

的入度是邻接矩阵中第

i列的元素之和。例v1

的出度为2；入度为1。26第26页，共57页，2023年，2月20日，星期六无向图的邻接矩阵都是对称矩阵。有向图的邻接矩阵一般不对称。12341234011000000001100001010101010101110100011001234512345故无向图可以采用压缩存储方式无向图有向图27第27页，共57页，2023年，2月20日，星期六带权图(网)的邻接矩阵v1v2v3v5v4v65487935651aij=

wij∞顶点vi与vj相邻接顶点vi与vj不相邻接∞5∞7∞∞∞∞4∞∞∞

8∞∞∞∞9∞∞5∞∞6∞∞∞5∞∞A=

123456123456

3∞∞∞1∞28第28页，共57页，2023年，2月20日，星期六邻接矩阵存储的缺点：这种存贮方式的空间复杂度正比于图的结点个数的平方，所以，当图中结点很多但边却很少时，采用这种结构会造成很大的浪费。29第29页，共57页，2023年，2月20日，星期六2.2邻接表对图中每一个顶点建立一个单链表，指示与该顶点关联的边或出弧。vexinfofirstarcadjvexnextarcarcinfo表结点头结点adjvex:邻接顶点位置arcinfo:边的信息nextarc

:下一条关联边结点vexinfo:顶点的信息firstarc:第一条关联边结点v1v2v3v5v4v6548793565130第30页，共57页，2023年，2月20日，星期六v1v2v3v5v4例无向图Ge1e2e3e4e5e612345v1v2v3v4v54e22e1∧5e43e31e1∧5e64e52e3∧3e51e2∧3e62e4∧如何获取顶点的度？顶点vi

的度为第i条链表中的结点数。需要多少存储空间？n+2e31第31页，共57页，2023年，2月20日，星期六v1v2v4v3例有向图Ge1e2e3e41234v1v2v3v43e22e1∧∧4e3∧1e4∧32第32页，共57页，2023年，2月20日，星期六邻接矩阵与邻接表存储空间求顶点的度求顶点的邻接顶点邻接表省一样一样判断两个顶点是否关联邻接矩阵方便0101010101010111010001100123451234512345v1v2v3v4v54e22e1∧5e43e31e1∧5e64e52e3∧3e51e2∧3e62e4∧33第33页，共57页，2023年，2月20日，星期六3图的遍历与树的遍历类似，如果从图中某一顶点出发访遍图中所有顶点，且使每一个顶点仅被访问一次，这一过程称为图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。通常有两条遍历图的路径:深度优先搜索、广度优先搜索。图的遍历相对复杂，为了避免同一个顶点被访问多次，增设一个辅助的布尔数组visited[0..n-1]

指示顶点是否已被访问过。34第34页，共57页，2023年，2月20日，星期六3.1深度优先搜索深度优先搜索是类似于树的一种先序遍历v1v2v3v5v4v6v7v8图可分为三部分:基结点第一个邻接结点导出的子图其它邻接顶点导出的子图深度优先搜索顺序:v1v2v4v8v5v3v6v735第35页，共57页，2023年，2月20日，星期六1.从图中某个顶点v

出发，访问此顶点；2.然后依次从v

的未被访问的邻接点出发进行深度优先遍历；3.直至图中所有和v

有路径相通的顶点都被访问到。4.若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点做起始点，重复上述过程，直至图中所有顶点都被访问到。算法描述:36第36页，共57页，2023年，2月20日，星期六深度优先遍历算法(DFS)递归算法开始访问V0,置标志求V0邻接点有邻接点w求下一邻接点wV0W访问过结束NYNYDFS开始标志数组初始化Vi=1Vi访问过DFSVi=Vi+1Vi==Vexnums结束NNYY37第37页，共57页，2023年，2月20日，星期六visited[v]=TRUE

；printf(v)；//访问此顶点for(w=FirstAdjVex(G,v)；w>=0；w=NextAdjVex(G,v,w))if(!visited[w])DFSTraverse(G,w)

；returnOK；voidDFSTraverse(GraphG，intv){//visited[0..n-1]初始为0；v指示顶点在数组中的位置；}38第38页，共57页，2023年，2月20日，星期六v1v2v3v5v4v6v7v8过程分析v1v2v3v4v6v8v5v7深度优先搜索顺序:v1v2v4v8v5v3v6v739第39页，共57页，2023年，2月20日，星期六栈实现深度优先搜索v1v2v3v4v6v8v5v7深度优先搜索顺序:v1v2v4v8v5v3v6v7v1v2v4v8v5v3v6v7总是从栈顶出发搜索！40第40页，共57页，2023年，2月20日，星期六initstack(S)；visited[v]=TRUE；Push(S,v)；printf(v)；Gettop(S,v)

；for(w=FirstAdjVex(G,v)；w>=0；w=NextAdjVex(G,v,w))if(!visited[w]){visited[w]=TRUE；Push(S,w)；printf(w)；Gettop(S,v)；}Pop(S)

；while(!StackEmpty(S)){}voidDFSTraverse(GraphG，intv){}41第41页，共57页，2023年，2月20日，星期六深度优先搜索的C语言实现：typedefstructnode{intadjvex;//邻接点域，存放与Vi邻接的点在表头数组中的位置structnode*next;//链域，指示下一条边或弧}JD;//表头接点：typedefstructtnode{intvexdata;//存放顶点信息structnode*firstarc;//指示第一个邻接点}TD;TDga[M];//ga[0]不用v1v2v3v5v4e1e2e3e4e5e642第42页，共57页，2023年，2月20日，星期六voidtraver(TDg[],intn){inti;staticintvisited[M];for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]==0) dfs(g,i,visited);}43第43页，共57页，2023年，2月20日，星期六voiddfs(TDg[],intv,intvisited[]){JD*w;inti;printf("%d",v);visited[v]=1;w=g[v].firstarc;while(w!=NULL){i=w->adjvex;if(visited[i]==0) dfs(g,i,visited);w=w->next;}}44第44页，共57页，2023年，2月20日，星期六3.2广度优先搜索广度优先搜索类似于树的层次遍历，广度优先搜索顺序:v1v2v3v4v5v6v7v8v1v2v3v5v4v6v7v8只有父辈结点被访问后才会访问子孙结点！把图人为的分层，按层遍历。45第45页，共57页，2023年，2月20日，星期六1.从图中某个顶点v

出发，访问此顶点；2.然后依次访问v

的各个未曾访问的邻接点；4.直至图中所有和v

有路径相通的顶点都被访问到。5.若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点做起始点，重复上述过程，直至图中所有顶点都被访问到。3.然后依次从这些邻接点出发再依次访问它们的邻接点；算法描述:46第46页，共57页，2023年，2月20日，星期六v1v2v3v5v4v6v7v8过程分析广度优先搜索顺序:v1v2v3v4v6v5v7v8v1v2v3v4v5v6v7v847第47页，共57页，2023年，2月20日，星期六广度优先遍历算法开始标志数组初始化Vi=1Vi访问过BFSVi=Vi+1Vi==Vexnums结束NNYY48第48页，共57页，2023年，2月20日，星期六开始访问V0,置标志求V邻接点ww存在吗V下一邻接点ww访问过结束NYNYBFS初始化队列V0入队队列空吗队头V出队访问w,置标志w入队NaaY49第49页，共57页，2023年，2月20日，星期六队列实现广度优先搜索算法InitQueue(Q)；visited[v]=TRUE；EnQueue(Q,v)

；printf(v)；DeQueue(Q,u)

；while(!QueueEmpty(Q)){}voidBFSTraverse(GraphG，intv){//visited[0..n-1]初始均为0；v指示顶点在数组中的位置；}for(w=FirstAdjVex(G,u)；w>=0；w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=TRUE；EnQueue(Q,w)；printf(w)；}//其邻接顶点均送入队列50第50页，共57页，2023年，2月20日，星期六4最短路径ABCGFED旅客希望停靠站越少越好，则应选择A——B——C——G旅客考虑的是旅程越短越好，1120920720210540340640190A——D——E——F——G51第51页，共57页，2023年，2月20日，星期六带权图的最短路径计算问题通常在实际中，航运、铁路、船行都具有有向性，故我们以带权有向图为例介绍最短路径算法。带权无向图的最短路径算法也通用。从单个源点到其余各顶点的最短路径算法。52第52页，共57页，2023年，2月20日，星期六4.1从单个源点到其余各顶点的最短路径算法——Dijkstra算法思想:贪心算法(局部最优)，按路径长度递增的次序产生最短路径。贪心算法:利用局部最优来计算全局最优。利用已得到的顶点的最短路径来计算其它顶点的最短路径。例，v5v0v1v4v3601005v21030201050求从v0

到其余各顶点的最短路径。1.初始，D[i]

的值为v0

到vi

的弧的权值D[i]

表示v0

到vi

的最短路径的长度显然，D[i]中的最小值D[2]

便是v0到v2

的最短路径的长度，Path[2]=(v0,v2)Path[i]表示v0

到vi

的最短路径53第53页，共57页，2023年，2月20日，星期六设下一条最短路径的终点是vk

，则这条最短路径或者是(v0,vk)、或者是v0经过v2

或v4到达vk

的路径；2.如何寻找下一条最短路径？例，v5v0v1v4v3601005v21030201050设下一条最短路径的终点是vj

，则这条最短路径或者是(v0,vj)

、或者是

v0经过v2到达vj

的路径；其中取D[i](D[2]除外)

中的最小值得到v4，Path[4]=(v0,v4)。3.如何寻找下一条最短路径？取D[i](D[2]、D[4]除外)

中的最小值得到v3

，Path[3]=(v0,v4