数据结构与算法-图

7图2/107主要内容图的基本概念图的抽象数据类型图的存储结构图的周游最短路径问题最小生成树3/107图是一种较线性表和树更为复杂的数据结构。线性表:

线性结构树:

层次结构图:

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

ABCDE图的基本概念4/107图G是由两个集合顶点集V(G)和边集E(G)组成的，记作G=(V(G)，E(G))，简称G=(V，E)。ABCDEABCDEABCDEV(vertex)是顶点的有穷非空集合

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

图的定义和基本术语5/107无向图:边是顶点的无序对，即边没有方向性。v1v2v3v5v4V={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)。无向图6/107有向图:其边是顶点的有序对，即边有方向性。v1v2v4v3V={v1,v2,v3,v4}E={<v1,v2>

,<v1,v3>,<v3,v4>,<v4,v1>}通常边称为弧，<v1,v2>表示顶点v1到v2的弧。称v1为弧尾，称v2为弧头。<v1,v2>≠<v2,v1>有向图7/107有时对图的边或弧赋予相关的数值，这种与图的边或弧相关的数值叫做权。

ABCDE53821497这些权可以表示从一个顶点到另一个顶点的距离。可以表示从一个顶点到另一个顶点的耗费。带权图8/107性质:若用n表示图中顶点数目，用e表示边或弧的数目，若在图中不存在顶点到自身的边或弧，则对于无向图，0≤e≤n(n-1)12对于有向图，0≤e≤n(n-1)证明:0≤e

显然成立对有向图来说，每个顶点至多可发出n-1条弧，共n个顶点，故至多有n(n-1)

条弧，即e≤n(n-1)；对无向图来说，由于边无方向，则任一两个顶点v1和v2，都有(v1,v2)=(v2,v1)，故至多有n(n-1)

条边；12基本性质9/107有

n(n-1)条边的无向图称为完全图。

12v1v2v4v3有

n(n-1)条弧的有向图称为有向完全图。

v1v2v3有很少条边或弧的图称为稀疏图。

反之称为稠密图。

完全图、稀疏图、稠密图10/107假设有两个图G=(V,E)和G’=(V’,E’)，如果V’

V，且E’

E，则称G’为G的子图。v1v2v4v3求子图v1v1v3v1v4v3v1v2v4v3v1v2v4v3子图11/107v1v2v3v5v4子图有v1v2v3v5v1v2v5v4v1v2v3v5v4子图12/107对于无向图

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/107对于无向图，顶点

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/107v1v2v4v3顶点v1

的出度为2顶点v1

的入度为1顶点v1

的度为3性质:对于一个图(无向图、有向图)，如果顶点vi

的度为TD(vi)，那么具有n

个顶点、e

条边或弧的图，必满足如下关系e=TD(vi)12∑i=1n无向图、有向图的边或弧均计算两遍。顶点的度15/107图（无向图、有向图）G中若存在一条有穷非空序列w=v0

e1

v1e2

v2…

ek

vk

，其中vi

和ei

分别为顶点和边（或弧），则称w

是从顶点v0

到vk

的一条路径。顶点v0和vk

分别称为路径w

的起点和终点。路径的长度是路径上的边的数目。w的长度为k起点和终点相同的路径称为回路(环)。图的其它术语v0v1v2vk-1vk...e1e2ek16/107若路径w的顶点

v0,v1,,vk

，除v0

和vk可以相同之外，其他顶点互不相同，则称w为简单路径。如果构成回路的路径是简单路径，称此回路为简单回路。不带回路的图称为无环图。不带回路的有向图称为有向无环图。…图的其它术语v0v1v2vk-1vk...e1e2ekv0v1v2vk-1vk...e1e2ek17/107无向图G，如果从顶点

v

到顶点

v’

有路径，则称

v

和

v’

是连通的。

如果对于无向图

G中任意两个顶点

vi,vj

∈V,vi和

vj

都是连通的，则称

G是连通图。

v1v2v3v5v4是否为连通图连通、连通图、连通分量、强连通图、强连通分量18/107连通分量指的是无向图中的最大连通子图。

ABCLHDEFGH非连通图连通分量为ABCLHDEFGH连通、连通图、连通分量、强连通图、强连通分量19/107有向图G，如果从顶点

v

到顶点

v’

有路径

或

从顶点

v’

到顶点

v

有路径，则称

v

和

v’

是连通的。

在有向图

G

中，如果对于每一对

vi,vj

∈V，vi≠vj

，从

vi到

vj

和

从vj

到

vi都存在路径，则称

G是强连通图。

v1v2v4v3是否为强连通图连通、连通图、连通分量、强连通图、强连通分量20/107有向图中的最大强连通子图称作有向图的强连通分量。

v1v2v4v3非强连通图强连通分量v2v1v4v3连通、连通图、连通分量、强连通图、强连通分量21/107网络、自由树网络带权的连通图。自由树（freetree）不带有简单回路的无向图，它是连通的，并且具有|V|-1条边。22/107图的抽象数据类型classGraph{//图的ADTpublic:

int

VerticesNum();//返回图的顶点个数

int

EdgesNum();//返回图的边数

//返回与顶点oneVertex相关联的第一条边

EdgeFirstEdge(int

oneVertex);

//返回与边PreEdge有相同关联顶点oneVertex的下一条边

EdgeNextEdge(Edge

preEdge);23/107图的抽象数据类型（续）//添加一条边

bool

setEdge(int

fromVertex,int

toVertex,intweight);//删一条边

bool

delEdge(int

fromVertex,int

toVertex);//如果oneEdge是边则返回TRUE，否则返回FALSE

bool

IsEdge(Edge

oneEdge);//返回边oneEdge的始点

int

FromVertex(Edge

oneEdge);//返回边oneEdge的终点

int

ToVertex(Edge

oneEdge);//返回边oneEdge的权

int

Weight(Edge

oneEdge); };24/107顺序存储邻接矩阵链式存储邻接表邻接多重表如何表达顶点之间存在的联系？多重链表，如何设计结点结构？图的存储结构25/107习惯性约定为每一个顶点设定一个序号，表示“顶点在图中的位置”。1235426/107设图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)=123412340110000000011000邻接矩阵(adjacencymatrix)27/107v1v2v3v5v4例无向图G0101010101010111010001100A(G)=1234512345优点:1.容易判断任意两个顶点之间是否有边或弧。2.容易求取各个顶点的度。邻接矩阵28/107无向图，顶点vi的度是邻接矩阵中第i

行或第

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

的度为2。v1v2v3v5v4例无向图G0101010101010111010001100A(G)=1234512345邻接矩阵29/107v1v2v4v3例有向图GA(G)=123412340110000000011000有向图，顶点vi

的出度是邻接矩阵中第i

行的元素之和。顶点vi的入度是邻接矩阵中第i

列的元素之和。例v1

的出度为2；入度为1。邻接矩阵30/107无向图的邻接矩阵都是对称矩阵。有向图的邻接矩阵一般不对称。12341234011000000001100001010101010101110100011001234512345故无向图可以采用压缩存储方式无向图有向图邻接矩阵31/107v1v2v3v5v4v65487935651aij

=wij∞顶点vi与vj

相邻接顶点vi与vj

不相邻接∞5∞7∞∞∞∞4∞∞∞

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

123456123456

3∞∞∞1∞带权图(网)的邻接矩阵32/107【代码7.2】图的基类classEdge{ //边类public:

intfrom,to,weight;//from是边的始点,to是终点,weight是边的权

Edge(){ //缺省构造函数

from=-1;to=-1;weight=0; }

Edge(int

f,int

t,intw){ //给定参数的构造函数

from=f;to=t;weight=w; }};33/107【代码7.2】图的基类classGraph{public:

int

numVertex; //图中顶点的个数

int

numEdge; //图中边的条数

int*Mark; //标记图的顶点是否被访问过

int*Indegree; //存放图中顶点的入度

Graph(int

numVert){ //图的构造函数

numVertex=numVert;

numEdge=0;

Indegree=newint[numVertex]; Mark=newint[numVertex]; for(inti=0;i<numVertex;i++){

Mark[i]=UNVISITED;//标志位设为UNVISITED

Indegree[i]=0; //入度设为0 } }34/107 ~Graph(){ //析构函数

delete[]Mark; //释放Mark数组

delete[]Indegree; //释放Indegree数组

}

int

VerticesNum(){ //返回图中顶点的个数

returnnumVertex; }

bool

IsEdge(Edge

oneEdge){//oneEdge是否是边

if(oneEdge.weight>0&&

oneEdge.weight<INFINITY&&

oneEdge.to>=0) returntrue; elsereturnfalse; }};35/107[代码7.3]用相邻矩阵表示图classGraphm:publicGraph{private:

int**matrix; //指向相邻矩阵的指针 public:

Graphm(int

numVert):Graph(numVert){ //构造函数

int

i,j;//i,j作为for循环中的计数器

matrix=(int**)newint*[numVertex]; //申请matrix数组行向量数组

for(i=0;i<numVertex;i++)//申请matrix数组行的存储空间

matrix[i]=newint[numVertex]; for(i=0;i<numVertex;i++) //相邻矩阵的所有元素都初始化为0 for(j=0;j<numVertex;j++)

matrix[i][j]=0;}36/107EdgeFirstEdge(int

oneVertex){ //返回顶点oneVertex的第一条边

EdgemyEdge;

myEdge.from=oneVertex; //将顶点oneVertex作为边的始点

//寻找第一个使得matrix[oneVertex][i]不为0的i值

for(inti=0;i<numVertex;i++){ if(matrix[oneVertex][i]!=0){

myEdge.to=i;

myEdge.weight=matrix[oneVertex][i]; break; //找到了顶点oneVertex的第一条边

} } returnmyEdge; }37/107EdgeNextEdge(Edge

preEdge){//返回与边有相同关联顶点的下一条边 EdgemyEdge; //myEdge的初始成员变量to为-1

myEdge.from=preEdge.from;//置边的始点为与上一条边preEdge相同

if(preEdge.to<numVertex){

//如果preEdge.to+1>=numVertex,那么就不存在下一条边了

for(inti=preEdge.to+1;i<numVertex;i++){

//寻找下一个使得matrix[preEdge.from][i]不为0的i值，即下一条边 if(matrix[preEdge.from][i]!=0){

myEdge.to=i;

myEdge.weight=matrix[preEdge.from][i]; break;//找到下一条边，跳出循环 } } }returnmyEdge;}38/1077.3.2邻接表当图中的边数较少时，相邻矩阵就会出现大量的零元素，存储这些零元素将耗费大量的存储空间。对于稀疏图，可以采用邻接表存储法。邻接表(adjacencylist)表示法是一种链式存储结构，由一个顺序存储的顶点表和n个链接存储的边表组成。顶点表目有两个域：顶点数据域和指向此顶点边表指针域边表把依附于同一个顶点vi的边（即相邻矩阵中同一行的非0元素）组织成一个单链表。边表中的每一个表目都代表一条边，由两个主要的域组成：与顶点vi邻接的另一顶点的序号指向边表中下一个边表目的指针39/1077.3.2邻接表

假设（vi，vj）是无向图中的一条边，在顶点vi的边表里存储有边（vi，vj）对应的边结点，在顶点vj的边表里还需存放（vj，vi）对应的边结点。因此，对于无向图，同一条边在邻接表中出现两次。图7.12无向图G1的邻接表表示需要多少存储空间？n+2e40/1077.3.2邻接表图7.13有向图G2的邻接表和逆邻接表表示41/1077.3.2邻接表图7.14带权图G4的邻接表表示

42/1077.3.2邻接表若图中有n个顶点和e条边，如果该图是无向图，则需要用到n个顶点结点和2e个边结点；若是有向图时，不考虑逆邻接表，只需要n个顶点结点和e个边结点。当边数e很小时，可以节省大量的存储空间。边表中表目顺序往往按照顶点编号从小到大排列。43/107[代码7.4]用邻接表存储图struct

listUnit{ //邻接表表目中数据部分的结构定义

intvertex;

//边的终点

intweight; //边的权};template<classElem>classLink{

//链表元素public: Elemelement; //表目的数据 Link*next; //表目指针，指向下一个表目

Link(constElem&elemval,Link*nextval=NULL){//构造函数

element=elemval;

next=nextval;

}

Link(Link*nextval=NULL){ //构造函数

next=nextval;

}};44/107template<classElem>classLList{ //链表类public: Link<Elem>*head;

//head保存一个虚的头结点，以方便操作

LList(){ //构造函数 head=newLink<Elem>(); }};45/107classGraphl:publicGraph{private:

LList<listUnit>*graList; //保存所有边表的数组public:

Graphl(int

numVert):Graph(numVert){ //构造函数

graList=newLList<listUnit>[numVertex];

//为边表graList数组申请空间 } EdgeFirstEdge(int

oneVertex){//返回顶点oneVertex的第一条边 EdgemyEdge;

//myEdge的初始成员变量to为-1

myEdge.from=oneVertex;//将顶点oneVertex作为边myEdge的始点

Link<listUnit>*temp=graList[oneVertex].head; if(temp->next!=NULL){//顶点oneVertex边表非空

myEdge.to=temp->next->element.vertex;

//边表第一个表目的顶点

myEdge.weight=temp->next->element.weight; }

returnmyEdge;

//如果没有找到第一条边，myEdge.to=-1 }46/107EdgeNextEdge(Edge

preEdge){//返回与边有相同关联顶点的下一条边

EdgemyEdge;

//myEdge的初始成员变量to为-1

myEdge.from=preEdge.from;//将边的始点置为与上一条边的相同

Link<listUnit>*temp=graList[preEdge.from].head;

//temp指向边表头一个

while(temp->next!=NULL&&

temp->next->element.vertex<=preEdge.to)

temp=temp->next;

//确定边preEdge的位置

if(temp->next!=NULL){

//边preEdge的下一条边存在

myEdge.to=temp->next->element.vertex;

myEdge.weight=temp->next->element.weight;

}

returnmyEdge; }47/107voidsetEdge(int

from,int

to,intweight){ //为图设定一条边

Link<listUnit>*temp=graList[from].head; //temp指向边表头一个

while(temp->next!=NULL&&temp->next->element.vertex<to)

temp=temp->next;

//确定边(from,to)在边表中的位置

if(temp->next==NULL){ //边(from,to)在边表中不存在

temp->next=newLink<listUnit>; //在边表最后加入这条新边

temp->next->element.vertex=to;

temp->next->element.weight=weight;

numEdge++;

Indegree[to]++;

return;

}

if(temp->next->element.vertex==to){ //边(from,to)在边表中已存在

temp->next->element.weight=weight;

//只需要改变边的权值

return;

}

if(temp->next->element.vertex>to){ //边(from,to)在边表中不存在

Link<listUnit>*other=temp->next;

temp->next=newLink<listUnit>;

temp->next->element.vertex=to;

temp->next->element.weight=weight;

temp->next->next=other; //连接边表中其后的其他边

numEdge++;

Indegree[to]++;

return;

}}48/107voiddelEdge(int

from,intto){ //删掉图的一条边

Link<listUnit>*temp=graList[from].head;//temp指向边表头一个

while(temp->next!=NULL&&temp->next->element.vertex<to)

temp=temp->next; //确定边(from,to)在边表中的位置

if(temp->next==NULL)

return; //边(from,to)在边表中不存在，直接返回

if(temp->next->element.vertex>to)

return; //边(from,to)在边表中不存在，直接返回

if(temp->next->element.vertex==to){//边(from,to)在边表中存在

Link<listUnit>*other=temp->next->next;

deletetemp->next; //从边表中将其删掉

temp->next=other; //其他表目挂接

numEdge--; //边数减1

Indegree[to]--; //终点的入度减1

return;

}}};49/1077.3.3十字链表十字链表（OrthogonalList）是有向图的另一种链式存储结构，可以看成是邻接表和逆邻接表的结合表中对应于有向图的每一条弧有一个表目，共有5个域：头(headvex)和尾(tailvex)分别表示弧头（终点）和弧尾（始点）顶点序号；tailnextarc链接指针指向下一条顶点以tailvex为弧尾的弧；headnextarc指针指向下一条以顶点headvex为弧头的弧；此外还有一个表示弧权值等信息的info域顶点表目由3个域组成：data域存放顶点的相关信息；firstinarc链接指针指向第一条以该顶点为终点的弧；firstoutarc链接指针指向第一条以该顶点为始点的弧。所有的顶点也可以放在顺序存储结构中50/107十字链表图7.15有向图G2的十字链表示例51/107十字链表在十字链表中，很容易找到以vi为始点和终点的弧。从顶点结点vi的firstoutarc出发，由tailnextarc域链接起来的链表，正好是原来的邻接表结构。统计这个链表中的表目个数，可以得到顶点vi的出度。如果从顶点结点vi的firstinarc出发，由headnextarc域链接起来的链表，恰好是原来的逆邻接表结构。统计这个链表中的表目个数，可以求出顶点vi的入度。52/1077.4图的周游图的周游（graphtraversal）给出一个图G和其中任意一个顶点V0，从V0出发系统地访问G中所有的顶点，每个顶点访问一次，这叫做图的周游。深度优先搜索广度优先搜索53/1077.4图的周游7.4.1深度优先周游7.4.2广度优先周游7.4.3拓扑排序54/1077.4.1深度优先搜索深度优先搜索（depth-firstsearch，简称DFS）基本思想访问一个顶点V，然后访问该顶点邻接到的未被访问过的顶点V’，再从V’出发递归地按照深度优先的方式周游，当遇到一个所有邻接于它的顶点都被访问过了的顶点U时，则回到已访问顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，再从W出发递归地按照深度优先的方式周游，最后，当任何已被访问过的顶点都没有未被访问的相邻顶点时，则周游结束。55/107深度优先搜索是类似于树的一种先序遍历v1v2v3v5v4v6v7v8图可分为三部分:基结点第一个邻接结点导出的子图其它邻接顶点导出的子图深度优先搜索顺序:v1v2v4v8v5v3v6v77.4.1深度优先搜索深度优先搜索树（depth-firstsearchtree）56/1077.4.1深度优先搜索（续）深度优先搜索的顺序是a，b，c，f，d，e，g57/1077.4.1深度优先周游【算法7.5】

图的深度优先周游(DFS)算法voidDFS(Graph&G,intv){ //深度优先搜索的递规实现

G.Mark[v]=VISITED; //将标记位设置为VISITED

Visit(G,v); //访问顶点v for(Edgee=G.FirstEdge(v);G.IsEdge(e);e=G.NextEdge(e))if(G.Mark[G.ToVertex(e)]==UNVISITED)

DFS(G,G.ToVertex(e));}58/1077.4.1深度优先周游周游图的过程实质上是搜索每个顶点的邻接点的过程，时间主要耗费在从该顶点出发搜索它的所有邻接点上分析上述算法，对于具有n个顶点和e条边的无向图或有向图，深度优先周游算法对图中每顶点至多调用一次DFS函数用相邻矩阵表示图时，共需检查n2个矩阵元素，所需时间为O(n2)用邻接表表示图时，找邻接点需将邻接表中所有边结点检查一遍，需要时间O(e)，对应的深度优先搜索算法的时间复杂度为O(n+e)59/1077.4.2广度优先搜索广度优先搜索（breadth-firstsearch，简称BFS）它的基本思想是访问顶点V0，然后访问V0邻接到的所有未被访问过的顶点V01，V02，…V0i，再依次访问V01，V02，…V0i邻接到的所有未被访问的顶点，如此进行下去，直到访问遍所有的顶点。60/107深度优先搜索类似于树的层次遍历，广度优先搜索顺序:

v1v2v3v4v5v6v7v8v1v2v3v5v4v6v7v8只有父辈结点被访问后才会访问子孙结点！把图人为的分层，按层遍历。广度优先搜索广度优先搜索树（breadth-firstsearchtree）61/107v1v2v3v5v4v6v7v8广度优先搜索顺序:v1v2v3v4v6v5v7v8v1v2v3v4v5v6v7v8广度优先搜索62/1077.4.2广度优先搜索（续）广度优先搜索的顺序是a，b，d，e，f，c，g63/1077.4.2广度优先搜索（续）//广度优先搜索算法的实现voidBFS(Graph&G,intV){

//初始化广度优先周游要用到的队列

usingstd::queue;

queue<int>Q;//访问顶点V，并标记其标志位，V入队

G.Mark[V]=VISITED;

Visit(G,V);

Q.push(V);

while(!Q.empty())//如果队列仍然有元素64/1077.4.2广度优先搜索（续）{

intV=Q.front();//顶部元素

Q.pop();//出队

//将与该点相邻的每一个未访问结点都入队

for(Edgee=G.FirstEdge(V);

G.IsEdge(e);e=G.NextEdge(e)){

if(G.Mark[G.ToVertex(e)]==UNVISITED)65/1077.4.2广度优先搜索（续）

{

G.Mark[G.ToVertex(e)]=VISITED;

Visit(G,G.ToVertex(e));

//入队

Q.push(G.ToVertex(e));} }}}66/1077.4.2广度优先搜索（续）广度优先搜索算法的时间复杂度与深度优先搜索算法的时间复杂度相同67/107练习对于入图所示的有向图，试写出：（1）从顶点①出发进行深度优先搜索所得到的深度优先生成树；（2）从顶点②出发进行广度优先搜索所得到的广度优先生成树；1234568/1077.4.3拓扑排序一个无环的有向图称为有向无环图(directedacyclicgraph，简称DAG)将一个有向无环图中所有顶点在不违反先决条件关系的前提下排成线性序列的过程称为拓扑排序(topologicalsorting)拓扑排序可以解决先决条件问题，即以某种线性顺序来组织多项任务，以便能够在满足先决条件的情况下逐个完成各项任务69/1077.4.3拓扑排序拓扑序列有向无环图常用来描述一个过程或一个系统的进行过程。对于有向无环图G=<V，E>，如果顶点序列满足：如果有向无环图G中存在顶点vi到vj的一条路径，那么在序列中顶点vi必在顶点vj之前，顶点集合V的这种线性序列称作一个拓扑序列(topologicalorder)70/1077.4.3拓扑排序（续）课程编号课程名称先决条件C1C2C3C4C5程序语言基础离散数学数据结构微机原理编译原理C6操作系统C1C1,C2C3C3,C4表示课程之间优先关系的有向图C1C2C3C5C4C6拓扑排序可以为:C1C2C3C5C4C6C4C1C2C3C5C671/1077.4.3拓扑排序（续）任何无环有向图，其顶点都可以排在一个拓扑序列里，其拓扑排序的方法是：（1）从图中选择一个入度为0的顶点且输出之。（2）从图中删掉此顶点及其所有的出边。（3）回到第（1）步继续执行。72/1077.4.3拓扑排序不断重复上述两个步骤，会出现两种情形：要么有向图中顶点全部被输出，要么当前图中不存在没有前驱的顶点。当图中的顶点全部输出时，就完成了有向无环图的拓扑排序；当图中还有顶点没有输出时，说明有向图中含有环。可见拓扑排序可以检查有向图是否存在环。73/107例，v1v2v4v3v6v5拓扑排序v1v6v4v3v2v574/107v1v2v4v3v6v5例，拓扑排序v1v3v2存在环75/1077.4.3拓扑排序（续）//队列方式实现的拓扑排序voidTopsortbyQueue(Graph&G){

for(inti=0;i<G.VerticesNum();i++)

G.Mark[i]=UNVISITED;//初始化标记数组

usingstd::queue;

queue<int>Q;//初始化队列

for(i=0;i<G.VerticesNum();i++){

if(G.Indegree[i]==0)

Q.push(i);//图中入度为0的顶点入队

}

while(!Q.empty()){//如果队列中还有图的顶点

76/1077.4.3拓扑排序（续）

intV=Q.front();//顶部元素

Q.pop();//一个顶点出队

Visit(G,V);//访问该顶点

G.Mark[V]=VISITED; //边e的终点的入度值减1

for(Edgee=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e)){

G.Indegree[G.ToVertex(e)]--;

if(G.Indegree[G.ToVertex(e)]==0)

Q.push(G.ToVertex(e));//入度为0的顶点入队

}}77/1077.4.3拓扑排序（续）

for(i=0;i<G.VerticesNum();i++){

if(G.Mark[i]==UNVISITED){ Print(“图有环”);//图有环

break;}}}78/1077.4.3拓扑排序对于有n个顶点和e条边的图，若其存储结构用邻接表表示，实现拓扑排序开始时建立入度为0的顶点队列需要检查所有顶点一次，需要时间O(n)，然后排序中每个顶点输出一次，更新顶点的入度需要检查每条边总计e次，故执行时间为O(n+e)。79/1077.5最短路径7.5.1单源最短路径7.5.2每对顶点之间的最短路径80/1077.5.1单源最短路径给定一个带权图G=<V，E>，其中每条边（vi，vj）上的权W[vi，vj]是一个非负实数。另外，给定V中的一个顶点s充当源点。现在要计算从源点s到所有其他各顶点的最短路径，这个问题通常称为单源最短路径(single-sourceshortestpaths)问题。图7.19单源最短路径的示例81/1077.5.1单源最短路径解决单源最短路径问题的一个常用算法是Dijkstra算法，它是由E.W.Dijkstra提出的一种按路径长度递增的次序产生到各顶点最短路径的贪心算法。E.W.Dijkstra[Dijkstra中的j不发音,

dɛɪkstra]：1930年5月11日出身于theNetherlandsRotterdam.1972年获得图灵奖（对开发ALGOL做出了重要贡献）提出不要使用goto语句去世于2002年8月6日于Nuenen,theNetherlands.82/107EDSGERWYBEDIJKSTRA

"ComputerScienceisnomoreaboutcomputersthanastronomyisabouttelescopes."

83/107Dijkstra算法基本思想把图的顶点集合化分成两个集合S和V-S。第一个集合S表示最短距离已经确定的顶点集，即一个顶点如果属于集合S当且仅当从源点s到该顶点的最短路径已知其余的顶点放在另一个集合V-S中。初始时，集合S只包含源点，即S={s}，这时只有源点到自己的最短距离是已知的。设v是V中的某个顶点，把从源点s到顶点v且中间只经过集合S中顶点的路径称为从源点到v的特殊路径，并用数组D来记录当前所找到的从源点s到每个顶点的最短特殊路径长度从尚未确定最短路径长度的集合V-S中取出一个最短特殊路径长度最小的顶点u，将u加入集合S，同时修改数组D中由s可达的最短路径长度84/107Dijkstra算法基本步骤D的初始状态为：如果从源点s到顶点v有弧则D[v]记为弧的权值；否则将D[v]置为无穷大。每次从尚未确定最短路径长度的集合V-S中取出一个最短特殊路径长度最小的顶点u，将u加入集合S，同时修改数组D中由s可达的最短路径长度：若加进u做中间顶点，使得vi的最短特殊路径长度变短，则修改vi的距离值（即当D[u]+W[u,vi]<D[vi]时，令D[vi]=D[u]+W[u,vi]）。然后重复上述操作，一旦S包含了所有V中的顶点，D中各顶点的距离值就记录了从源点s到该顶点的最短路径长度。85/107例，v5v0v1v4v3601005v21030201050带权邻接矩阵∞∞10

∞

30100012345∞∞5

∞∞∞∞∞∞

50∞∞∞∞∞

∞∞10∞∞∞

20∞60∞∞∞

∞∞∞012345{v2}∞10∞30100v0v2v210∞6030100v0v4v430{v2,v4}∞50

90v0v4v3v350{v2,v4,v3}∞

60v0v4v3v5v560{v2,v4,v3,v5}∞

v1∞v1v2v3v4v5最短路径新顶点S顶点路径长度每次修改都用的是最新加入集合S的顶点86/107推导最短路径距离数组中还可以设立一个域来记录从源点到顶点v的最短路径上v前面经过的一个顶点，这样就可以推导出最短路径。初始时，对所有的v≠s，均设置其前一个顶点为s在Dijkstra算法更新最短路径长度时，只要D[u]+W[u,v]<D[v]，就设置v的前一个顶点为u，否则不做修改。当Dijkstra算法终止时就可以找到源点s到顶点v的最短路径上每个顶点的前一个顶点，从而找到源点s到顶点v的最短路径。87/107迭代步数sv0v1v2v3v4初始状态{v0}Length:0pre:0length:10pre:0length:∞pre:0length:30pre:0length:100pre:01{v0,v1}Length:0pre:0length:10pre:0length:60pre:1length:30pre:0length:100pre:02{v0,v1,v3}Length:0pre:0length:10pre:0length:50pre:3length:30pre:0length:90pre:33{v0,v1,v3,v2}length:0pre:0length:10pre:0length:50pre:3length:30pre:0length:60pre:24{v0,v1,v3,v2,v4}length:0pre:0length:10pre:0length:50pre:3length:30pre:0length:60pre:2Pre记录从源点到顶点v的最短路径上v前面经过的一个顶点88/107单源最短路径【代码7.8】Dijkstra算法

classDist{ //Dist类，Dijkstra和Floyd算法用于保存最短路径信息public:

intindex; //顶点的索引值，仅Dijkstra算法用到

intlength; //当前最短路径长度

intpre; //路径最后经过的顶点};89/107单源最短路径//Dijkstra算法voidDijkstra(Graph&G,ints,Dist*&D){D=newDist[G.VerticesNum()];//初始化Mark数组、D数组

for(inti=0;i<G.VerticesNum();i++){

G.Mark[i]=UNVISITED;

D[i].index=i;

D[i].length=INFINITY;

D[i].pre=s;}

D[s].length=0;//源点到自身的路径长度设置为0

MinHeap<Dist>H(G.EdgesNum());//最小堆用于找出最短路径

H.insert(D[s]);90/107单源最短路径

for(i=0;i<G.VerticesNum();i++){

boolFOUND=falseDistd;

while(!H.isEmpty){d=H.removeMin()//获得到s路径长度最小的顶点

if(G.Mark[d.index]==UNVISITED){//如果未访问过则跳出循环

FOUND=true;break;}}if(!FOUND)//若没有符合条件的最短路径则跳出本次循环

break;

intv=d.index;

G.Mark[v]=VISITED; //将该顶点的标记位设置为VISITED

//加入v以后需要刷新D中v的邻接点的最短路径长度

for(Edgee=G.FirstEdge(v);

G.IsEdge(e);e=G.NextEdge(e)){91/107单源最短路径

if(D[G.ToVertex(e)].length>(D[v].length+G.Weight(e))){

D[G.ToVertex(e)].length=D[v].length+G.Weight(e);

D[G.ToVertex(e)].pre=v;H.Insert(D[G.ToVertex(e)]);}}}92/107算法复杂度对于n个顶点e条边的图，图中的任何一条边都可能在最短路径中出现，因此最短路径算法对每条边至少都要检查一次代码7.8采用最小堆来选择权值最小的边，那么每次改变最短特殊路径长度时需要对堆进行一次重排，此时的时间复杂度为O((n+e)loge)，适合于稀疏图如果像算法7.10介绍的Prim算法那样，通过直接比较D数组元素，确定代价最小的边就需要总时间O(n2)；取出最短特殊路径长度最小的顶点后，修改最短特殊路径长度共需要时间O(e)，因此共需要花费O(n2)的时间，这种方法适合于稠密图93/107算法正确性这种算法为什么得到的就是最短路径呢？事实上，如果存在一条从源点到u且长度比D[u]更短的路径，假设这条路径经过第二个集合的某些顶点（不妨设为x）才到达u。在这条路径上分别用d(s，x)，d(x，u)和d(s，u)表示源点s到顶点x、顶点x到顶点u和源点s到顶点u的距离，那么有d(s，u)=d(s，x)+d(x，u)<D[u]，且D[x]≤d(s，x)。由边的权值的非负性，推得D[x]<D[u]。这与u是第二个集合中距离值最小的顶点矛盾，所以每次加入第一个集合的u的距离值就是从s到u的最短路径长度。94/107练习以下图为例，按Dijkstra算法计算得到的从顶点A到其他各个顶点的最短路径和最短路径长度。A

B

C

D

E1018

5522295/1077.5.2每对顶点之间的最短路径找出从任意顶点vi到顶点vj的最短路径，这个问题通常称为带权图的所有顶点对之间的最短路径(all-pairsshortestpaths)问题。解决这一问题可以每次以一个顶点为源点，重复执行Dijkstra算法n次，这样就可以求得所有的顶点对之间的最短路径及其最短路径长度，其时间复杂度为O(n3)。96/1077.5.2每对顶点之间的最短路径Floyd算法是典型的动态规划法，自底向上分别求解子问题的解，然后由这些子问题的解得到原问题的解。这个算法的时间复杂度也是O(n3)，但形式上比较简单。RobertW.Floyd:1936年6月8日生于纽约，“自学成才”斯坦福大学计算机科学系教授1978年图灵奖获得者97/107Floyd算法Floyd算法算法思想：假设用相邻矩阵adj表示图Floyd算法递归地产生一个矩阵序列adj(0)，adj(1)，…，adj(k)

，…，adj(n)adj(k)[i，j]等于从顶点Vi到顶点Vj中间顶点序号不大于k的最短路径长度

98/107Floyd算法假设已求得矩阵adj(k-1)，那么从顶点Vi到顶点Vj中间顶点的序号不大于k的最短路径有两种情况：一种是中间不经过顶点Vk，那么就有

adj(k)[i，j]=adj(k-1)[i，j]另一种是中间经过顶点Vk，那么adj(k)[i，j]<adj(k-1)[i，j]，且adj(k)[i，j]=adj(k-1)[i，k]+adj(k-1)[k，j]ViVjVkShortestPathusingintermediatevertices{V1,...Vk-1}Shortestpathusingintermediatevertices

{V1,...Vk

}99/107每对顶点间的最短路径100/107每对顶点间的最短路径//Floyd算法voidFloyd(Graph&G,Dist**&D){

int

i,j,v;//i,j,v作为计数器

D=new Dist*[G.VerticesNum()];

for(i=0;;i<G.VerticesNum();i++){

D[i]=newDist[G.VerticesNum()];} //初始化D数组

for(i=0;i<G.VerticesNum();i++)

for(j=0;j<G.VerticesNum();j++)101/107每对顶点间的最短路径

if(i==j){

D[i][j].length=0;

D[i][j].pre=i;}else{

D[i][j]=INFINITY;

D[i][j].pre=-1;}

for(v=0;v<G.VerticesNum();v++)

for(Edgee=G.FirstEdge(v);

G.IsEdge(e);e=G.NextEdge(e)){

D[v][G.ToVertex(e)].length=G.Weight(e);

D[v][G.ToVertex(e)].pre=v;}102/107每对顶点间的最短路径//如果两个顶点间的最短路径经过顶点v，则有//D[i][j].length>(D[i][v].length+D[v][j].length

for(v=0;v<G.VerticesNum();v++)

for(i=0;i<G.VerticesNum();i++)

for(j=0;j<G.VerticesNum();j++)

if(D[i][j].length>(D[i][v].length

+D[v][j].length)){

D[i][j].length=D[i][v].length

+D[v][j].length;

D[i][j].pre=D[v][j].pre;}}103/107每对顶点间的最短路径

注：其中Dist类型与Dijkstra算法用到的Dist类型一致。因为Floyd算法的时间复杂度主要在于三重for循环，所以很明显，其复杂度是O(n×n×n).104/1077.6最小生成树最小生成树的概念连通图的最小生成树生成树应用举例最小生成树的构造算法Prim算法Kruskal算法105/107生成树的概念连通图的生成树复习：图的所有顶点加上周游过程中经过的边所构成的子图称作图的生成树一般说，一个连通无向图的生成树不一定是唯一的（除非这个图本身就是树）对于n个结点的图，其生成树中必定有n-1条边106/107性质:一个有n个顶点的连通图的生成树有且仅有n-1条边。1.如果一棵生成树有n个顶点和小于n-1条边，则为非连通图。2.如果一棵支撑树有n个顶点和多于n-1条边，则一定有环。构成一棵n顶点支撑树需要n-1条边，少于n