广度优先遍历BFS课件

图的类型定义n(n≥0)个元素的有限集合图的类型定义n(n≥0)个元素的有限集合基本术语基本术语

图是由一个顶点集V和一个弧集VR构成的数据结构Graph=(V,{VR})其中:VR＝{<v,w>|v,w∈V且P(v,w)}<v,w>表示从v到w的一条弧，并称v为弧尾，w为弧头谓词P(v,w)

定义了弧<v,w>的意义或信息图是由一个顶点集V和一个弧集VR构成的数据结

由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图

ABECD

例如:

G1=(V1,{VR1})其中:V1={A,B,C,D,E}VR1={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}由于“弧”是有方向的，因此称由若有<v,w>VR,必有<w,v>VR,则称(v,w)为顶点v和顶点w之间存在一条边

BCADFE由顶点集和边集构成的图称作无向图例如:

G2=(V2,{VR2})V2={A,B,C,D,E,F}VR2={<A,B>,<A,E>,<B,E>,<C,D>,<D,F>,<B,F>,<C,F>}若有<v,w>VR,必B名词和术语网、子图

完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林关节点、重连通图重连通分量、连通度名词和术语网、子图完全图、稀疏图、稠密图邻接点、AEFBBC设图G=(V,VR)和图G=(V,VR),且VV,VRVR,则称

G为G的子图ABECF1597211132弧或边带权的图分别称作有向网或无向网AEFBBC设图G=(V,VR)和ABECF159721假设图中有

n

个顶点，e

条边，则

含有

e=n(n-1)/2条边的无向图称作无向完全图

含有

e=n(n-1)条弧的有向图称作有向完全图

若边或弧的个数

e<nlogn，则称作稀疏图，否则称作稠密图假设图中有n个顶点，e条边，则含有e=n(n

假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点，边(v,w)

ID(B)=3ID(A)=2和顶点v和w相关联和顶点v关联的边的数目定义为顶点的度ACDFEB假若顶点v和顶点w之间存在一条边，则称顶点v和w顶点的出度:以顶点v为弧尾的弧的数目ABECF有向图顶点的入度:以顶点v为弧头的弧的数目顶点的度(TD)=出度(OD)+入度(ID)ID(B)=2OD(B)=1TD(B)=3顶点的出度:以顶点v为弧尾的弧的数目ABECF有向图顶点的设图G=(V,{VR})中的一个顶点序列{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)VR1≤j≤m,则称从顶点u到顶点w之间存在一条路径。路径上边的数目称作路径长度ABECF长度为3的路径{A,B,C,F}设图G=(V,{VR})中的一个顶点序列ABECF长度为3的ABECF简单路径:序列中顶点不重复出现的路径简单回路:序列中第一个顶点和最后一个顶点相同的路径ABECF简单路径:序列中顶点不重复出现的路径简单回路:序列若图G中任意两个顶点之间都有路径相通，则称此图为连通图若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量BACDFEBACDFE若图G中任意两个顶点之间都有路径相通，则称此图为连通图若无向

若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图,ABECFABECF对有向图，

否则，其各个强连通子图称作它的强连通分量若任假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林BACDFE假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点

没有关节点的连通图被称为重连通图

若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点没有关节点的连通图被称为重连

一个连通图G如果不是重连通图，那么它可以包括几个重连通分量若依次删除一个连通图中的

1,2,…,k-1个顶点后,该图仍连通,删除第k个顶点后该图成为不连通的,则称该图的连通度为k一个连通图G如果不是重连通图，结构的建立和销毁插入或删除顶点对邻接点的操作对顶点的访问操作顶点的遍历插入和删除弧基本操作结构的建立和销毁插入或删除顶点对邻接点的操作对顶点的访问操作CreatGraph(&G,V,VR)://按定义(V,VR)构造图DestroyGraph(&G)://销毁图结构的建立和销毁CreatGraph(&G,V,VR):DestroyG对顶点的访问操作LocateVex(G,u);

//若G中存在顶点u，则返回该顶点在

//图中“位置”；否则返回其它信息GetVex(G,v);

//返回v的值PutVex(&G,v,value);//对v赋值value对顶点的访问操作LocateVex(G,u);GetV对邻接点的操作FirstAdjVex(G,v);

//返回v的“第一个邻接点”。若该顶点

//在G中没有邻接点，则返回“空”NextAdjVex(G,v,w);

//返回v的（相对于w的）“下一个邻接

//点”。若w是v的最后一个邻接点，则

//返回“空”对邻接点的操作FirstAdjVex(G,v);Next插入或删除顶点InsertVex(&G,v);

//在图G中增添新顶点vDeleteVex(&G,v);//删除G中顶点v及其相关的弧插入或删除顶点InsertVex(&G,v);Delet插入和删除弧InsertArc(&G,v,w);

//在G中增添弧<v,w>，若G是无向的，

//则还增添对称弧<w,v>DeleteArc(&G,v,w);

//在G中删除弧<v,w>，若G是无向的，

//则还删除对称弧<w,v>插入和删除弧InsertArc(&G,v,w);Del遍历DFSTraverse(G,v,Visit());

//从顶点v起深度优先遍历图G，并对每

//个顶点调用函数Visit一次且仅一次BFSTraverse(G,v,Visit());

//从顶点v起广度优先遍历图G，并对每

//个顶点调用函数Visit一次且仅一次遍历DFSTraverse(G,v,Visit图的存储表示一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示四、有向图的十字链表存储表示五、无向图的邻接多重表存储表示三、图的逆邻接表存储表示图的存储表示一、图的数组(邻接矩阵)存储表示二、图的邻接表存Aij={0(i,j)VR1(i,j)VR图的数组(邻接矩阵)存储表示BACDFE定义:矩阵的元素为无向图的邻接矩阵是对称矩阵Aij={0(i,j)VR1(i,j)VR图的数有向图的邻接矩阵为非对称矩阵ABECD有向图的邻接矩阵为非对称矩阵ABECD在有向图中,统计第i

行

1的个数可得顶点i

的出度，统计第j列

1的个数可得顶点j

的入度在无向图中,统计第i行(列)1的个数可得顶点i的度在有向图中,统计第i行1的个网（边或弧带权值的图）的数组(邻接矩阵)存储表示如下网（边或弧带权值的图）的数组0A141B0452C353D254E015F123BACDFE图的邻接表存储表示0A14BACDFE图的邻接01234有向图的邻接表1423012ABCDEABECD可见，在有向图的邻接表中不易找到指向该顶点的弧01234有向图的邻接表1ABECD在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧图的逆邻接表存储表示ABCDE033420012341ABECD在有向图的图的逆邻接表存储表示A0334有向图的十字链表存储表示

弧的结点结构弧尾顶点位置弧头顶点位置弧的相关信息指向下一个有相同弧头的结点指向下一个有相同弧尾的结点typedefstructArcBox{//弧的结构表示

inttailvex,headvex;InfoType*info;structArcBox*hlink,*tlink;

}VexNode;有向图的十字链表存储表示弧的结点结构弧尾顶点位置弧头顶点顶点的结点结构顶点信息数据指向该顶点的第一条入弧指向该顶点的第一条出弧typedefstructVexNode{//顶点的结构表示

VertexTypedata;ArcBox*firstin,*firstout;}VexNode;顶点的结点结构顶点信息数据指向该顶点typedefstruct{VexNodexlist[MAX_VERTEX_NUM];//顶点结点(表头向量)

intvexnum,arcnum;//有向图的当前顶点数和弧数}OLGraph;有向图的结构表示(十字链表)typedefstruct{有向图的结构表示(十字链表对右边所示的有向图G,十字链表表示如下:对右边所示的有向图G,十字链表表示如下:无向图的邻接多重表存储表示typedefstructEbox{VisitIfmark;//访问标记

intivex,jvex;//该边依附的两个顶点的位置

structEBox*ilink,*jlink;InfoType*info;//该边信息指针}EBox;边的结构表示无向图的邻接多重表存储表示typedefstructEbtypedefstruct{//邻接多重表

VexBoxadjmulist[MAX_VERTEX_NUM];

intvexnum,edgenum;

}AMLGraph;顶点的结构表示typedefstructVexBox{VertexTypedata;EBox*firstedge;//指向第一条依附该顶点的边}VexBox;无向图的结构表示typedefstruct{//邻接多重表顶点的结对右边所示的无向图G,邻接多重表表示如下:对右边所示的无向图G,邻接多重表表示如下:图的遍历深度优先遍历DFS(DepthFirstSearch)

广度优先遍历BFS(BreadthFirstSearch)广度优先遍历BFS课件深度优先遍历DFS(DepthFirstSearch)深度优先遍历的示例前进回退ACDEGBFIHACDEGBFIH123456789123456789深度优先遍历过程深度优先生成树深度优先遍历DFS(DepthFirstSearch)深广度优先遍历BFS(BreadthFirstSearch)广度优先遍历的示例ACDEGBFIHACDEGBFH123456789123456789广度优先遍历过程广度优先生成树I广度优先遍历BFS(BreadthFirstSearchvoidtraverse(intn,Graphg){for(v=0;v<n;v++)visited[v]=false;for(v=0;v<n;v++)if(!visited[v])dfs(v,g)或bfs(v,g);}voidtraverse(intn,Graphgvoiddfs(intv,Graphg){cout<<GetVex(g,v);visited[v]=true;

for(w=FirstAdjVex(g,v);w>=0;w=NextAdjVex(g,v,w)){ if(!visited[w])dfs(w,g)}}voiddfs(intv,Graphg){voidbfs(intv,Graphg){cout<<GetVex(g,v);InitQueue(q);EnQueue(q,v);visited[v]=true;while(!Empty(q)){DeQueue(q,v);

for(w=FirstAdjVex(g,v);w>=0;w=NextAdjVex(g,v,w)){ if(!visited[w]){cout<<GetVex(g,w);EnQueue(q,w);visited[w]=true;}}};voidbfs(intv,Graphg){最小代价生成树

(minimumcostspanningtree)最小代价生成树

(minimumcostspanning

假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建

n-1条线路，如何在最节省经费的前提下建立这个通讯网？问题假设要在n个城市之间建立通讯联络网，则连通

构造网的一棵最小生成树，即：在e

条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小该问题等价于构造网的一棵最小生成树，即：在e构造最小生成树的准则必须使用且仅使用该网络中的n-1

条边来联结网络中的n

个顶点不能使用产生回路的边各边上的权值的总和达到最小构造最小生成树的准则算法二：克鲁斯卡尔算法

(Kruskal)

算法一：普里姆算法

(Prim)算法二：克鲁斯卡尔算法算法一：普里姆算法普里姆算法的基本思想广度优先遍历BFS课件

1.取图中任意一个顶点v作为生成树的根，之后往生成树上添加新的顶点w1.取图中任意一个顶点v作为

2.在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集U

和尚未落在生成树上的顶点集V-U

，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边(v,w)这里v属于V，w属于UUV-U2.在生成树的构造过程中，图中n个顶

3.之后继续往生成树上添加顶点，直至生成树上含有n-1

个顶点为止3.之后继续往生成树上添加顶abcdegf195141827168213ae12dcbgf7148531621所得生成树权值和=14+8+3+5+16+21=67abcdegf195141827168213ae12dcbg252510504613228102514242216185046132504613210原图(a)(b)504613210(c)(d)(e)(f)50461321022125046121025142216123252212252510504613228102514242216185克鲁斯卡尔算法的基本思想广度优先遍历BFS课件具体做法:先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小具体做法:先构造一个只含n个顶点的子图SG，然后从权abcdegf195141827168213ae12dcbgf71485316217121819abcdegf195141827168213ae12dcbg10504613228102514242216181250461325046132原图(a)(b)1050461322810251424221618125041012504613228102514242216181250461325046132101412原图(c)(d)504613210141612(e)(f)(g)504613210142216125046121025142216123101250461322810251424221618125活动网络

(ActivityNetwork)用顶点表示活动的网络(AOV网络)(ActivityOnVertices)用边表示活动的网络(AOE网络)(ActivityOnEdges)有向无环图活动网络

(ActivityNetwork)用顶点表

C1

高等数学

C2

程序设计基础

C3

离散数学C1,C2

C4

数据结构C3,C2C5

高级语言程序设计C2C6

编译方法C5,C4C7

操作系统C4,C9C8

普通物理C1C9

计算机原理

C8

课程代号课程名称先修课程C1学生课程学习工程图C8C3C5C4C9C6C7C1C2学生课程学习工程图C8C3C5C4C9C6C7C1C2拓扑排序(TopologicalSort)

按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系

由此所得顶点的线性序列称之为拓扑有序序列拓扑排序(TopologicalSort)例如：对于下列有向图BDAC可求得拓扑有序序列：

ABCD

或

ACBD例如：对于下列有向图BDAC可求得拓扑有序序列：BDAC反之，对于下列有向图不能求得它的拓扑有序序列。因为图中存在一个回路

{B,C,D}BDAC反之，对于下列有向图不能求得它的拓扑有序序列。因为图进行拓扑排序的步骤一、从有向图中选取一个没有前驱的顶点，并输出之

重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止二、从有向图中删去此顶点以及所有以它为尾的弧进行拓扑排序的步骤一、从有向图中选取一个没有前驱abcghdfeabhcdgfeabcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念

没有前驱的顶点

入度为零的顶点

删除顶点及以它为尾的弧

弧头顶点的入度减1在算法中需要用定量的描述替代定性的概念没有前驱的顶点

对学生选课工程图进行拓扑排序,得到的拓扑有序序列为

C1,C2,C3,C4,C5,C6,C8,C9,C7

或

C1,C8,C9,C2,C5,C3,C4,C7,C6C8C3C5C4C9C6C7C1C2对学生选课工程图进行拓扑排序,得到C0C1C2C3C4C5(a)有向无环图C2C5C1C0C3(b)输出顶点C4C1C2C5C3(c)输出顶点C0C4C0C2C5C1C3(d)输出顶点C3C0C1C2C3C4C5(a)有向无环图C2C5C1C0CC4,C0,C3,C2,C1,C5

C1C2C5(e)输出顶点C2C5C1(f)输出顶点C1C5(g)输出顶点C5(h)拓扑排序完成C4,C0,C3,C2,C1,C5C1

在算法中,使用一个堆栈或队列存放入度为零的顶点,供选择和输出无前驱的顶点在算法中,使用一AOV网邻接表表示012345C0C1C2C3C4C5C0C1C2C30C4C50countdataadj

1301031

destlink3051500150AOV网邻0C0C1C2C3C4C5C0countda

在算法中,使用一个堆栈或队列存放入度为零的顶点,供选择和输出无前驱的顶点在算法中,使用一拓扑排序算法描述广度优先遍历BFS课件建立入度为零的顶点栈当入度为零的栈不空时,重复执行

从栈中退出一个顶点,并输出之从AOV网中删去这个顶点和它发出的边,边的终点入度减一如果边的终点入度减至0,则该顶点进入入度为零的顶点栈

如果输出顶点个数少于AOV网的顶点个数,则报告网络中存在有向环广度优先遍历BFS课件建立入度为零的顶点队当入度为零的队不空时,重复执行

从队中退出一个顶点,并输出之从AOV网中删去这个顶点和它发出的边,边的终点入度减一如果边的终点入度减至0,则该顶点进入入度为零的顶点队

如果输出顶点个数少于AOV网的顶点个数,则报告网络中存在有向环广度优先遍历BFS课件

在算法实现时,为了建立入度为零的顶点栈,可以不另外分配存储空间,直接利用入度为零的顶点的count[]数组元素。设立一个栈顶指针top,指示当前栈顶位置,即某一个入度为零的顶点。栈初始化时置top

=-1在算法实现时,为了建立入度为零的顶点栈,可以不另外分配将顶点i

进栈时执行以下指针的修改：

count[i]=top;top=i;

//top指向新栈顶i,原栈顶元素在count[i]中退栈操作可以写成：

j=top;top=count[top];

//位于栈顶的顶点记于

j,top退到次栈顶将顶点i进栈时执行以下指针的修改：拓扑排序时入度为零的顶点栈在count[]中的变化C0C1C2C3C4C513010313-112322-112221-1222012345012345012345012345toptoptoptop建栈toptop顶点4出栈toptop顶点0出栈拓扑排序时入度为零的顶点栈在count[]中的变化C0C1C顶点3出栈拓扑排序时入度为零的顶点栈在count[]中的变化C0C1C2C3C4C521-12222-1-12212-1-122-12-1-122-1012345012345012345012345toptoptoptoptop顶点1出栈top顶点5出栈顶点2出栈顶点3拓扑排序时入度为零的顶点栈在count[]中的变化C0拓扑排序的算法广度优先遍历BFS课件voidGraph::TopologicalSort(){

inttop=-1;

//入度为零的顶点栈初始化

for(inti=0;i<n;i++)

//入度为零顶点

if(count[i]==0)//进栈

{count[i]=top;top=i;}for(i=0;i<n;i++)//期望输出n个顶点

if(top==-1)

//中途栈空,转出

{cout<<“网络中有回路！"<<endl; return;};

voidGraph::TopologicalSort

else

//继续拓扑排序

{int

j=top;top=count[top];

//退栈

cout<<j<<endl;//输出

Edge*p=NodeTable[j].adj;while(p!=NULL)

//扫描出边表

{intk=p->dest;

//另一顶点else

if(--count[k]==0)

//顶点入度减一

{count[k]=top;top=k;}

//顶点的入度减至零,进栈

p=p->link;

}}}if(--count[k]==分析此拓扑排序算法可知，如果AOV网络有n

个顶点，e条边，在拓扑排序的过程中，搜索入度为零的顶点，建立链式栈所需要的时间是O(n)。在正常的情况下，有向图有

n

个顶点，每个顶点进一次栈，出一次栈，共输出n次。顶点入度减一的运算共执行了e次。所以总的时间复杂度为O(n+e)分析此拓扑排序算法可知，如果AOV网关键路径(CriticalPath)问题:假设以有向网表示一个施工流程图，弧上的权值表示完成该项子工程所需时间。

问：哪些子工程项是“关键工程”？

即：哪些子工程项将影响整个工程的完成期限关键路径(CriticalPath)问题:假设以有向abcdefghk64521187244例如:整个工程完成的时间为：从有向图的源点到汇点的最长路径源点汇点6174abcdefghk64521187244例如:整个工程完成的

用有向边表示一个工程中的活动(Activity),

用边上权值表示活动持续时间(Duration),

用顶点表示事件(Event)“关键活动”指的是：该弧上的权值增加

将使有向图上的最长路径的长度增加用有向边表示一个工程中的活动(Activ

完成整个工程所需的时间取决于从源点到汇点的最长路径长度,

即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径完成整个工程所需的时间取决于从源点到汇点的最长路径长度

如何求关键活动？

假设第i

条弧为<j,k>对第j

个顶点而言“事件(顶点)”的最早发生时间ve(j)“事件(顶点)”的最迟发生时间vl(j)对第i

项活动而言“活动(弧)”的最早开始时间ee(i)“活动(弧)”的最迟开始时间el(i)

假设第i条弧为<j,k>ve(源点)=0；ve(k)=Max{ve(j)+dut(<j,k>)}(2<=k<=n,<j,k>属于所有以k为

头的弧的集合)vl(汇点)=ve(汇点)；vl(j)=Min{vl(k)–dut(<j,k>)}(1<=j<=n-1,<j,k>属于所有以j为

尾的弧的集合)ve(源点)=0；附注“事件(顶点)”的最早发生时间ve(j)ve(j)=从源点到顶点j的最长路径长度；“事件(顶点)”的最迟发生时间vl(k)vl(k)=从源点到汇点的最长路径长度-

从顶点k到汇点的最长路径长度。附注“事件(顶点)”的最早发生时间ve(j)“事件(顶ee(i)=ve(j)el(i)=vl(k)–dut(<j,k>)ve(源点)=vl(源点)=0vl(汇点)=ve(汇点)关键活动:el(i)=ee(i)ee(i)=ve(j)

这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行广度优先遍历BFS课件abcdefghk6452118724400000000064571157151418181818181818181818161486610807拓扑有序序列:a-d-f-c-b-e-h-g-kabcdefghk6452118724400000000060645771514181814161078660000645777151414160236688710064577151418181416107866000064显然求ve的顺序应该是按拓扑有序的

次序

而求vl的顺序应该是按拓扑逆序的

次序因为拓扑逆序序列即为拓扑有序序列的逆序列因此应该在拓扑排序的过程中，另设一个“栈”记下拓扑有序序列显然求ve的顺序应该是按拓扑有序的而求

要找出关键路径，必须找出关键活动,即不按期完成就会影响整个工程完成的活动关键路径上的所有活动都是关键活动

因此,只要找到了关键活动,就可以找到关键路径要找出关键路径，必须找出关键活最短路径

(ShortestPath)最短路径

(ShortestPath)最短路径问题如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小最短路径问题问题解法边上权值非负情形的单源最短路径问题

—Dijkstra算法所有顶点之间的最短路径

—Floyd算法问题解法

为求得这些最短路径,Dijkstra提出按路径长度的递增次序,逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止为求得这些最短路径,Dijkstra

依最短路径的长度递增的次序求得各条路径源点v1…

其中，从源点到顶点v的最短路径是所有最短路径中长度最短者v2依最短路径的长度递增的次序求得各条路径源点v

在这条路径上，必定只含一条弧，并且这条弧的权值最小。下一条路径长度次短(第1次)的最短路径的特点：路径长度最短(第0次)的最短路径的特点：

它只可能有两种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。在这条路径上，必定只含一条弧，并且这条弧的权值最小。其余最短路径(第k次)的特点：再下一条路径长度次短(第2次)的最短路径的特点:

它可能有两种情况：或者是从源点不经过v2到该点；或者是从源点到顶点v2，再到达该顶点。

它或者是从源点不经过vk到该点；或者是从源点到vk，再到达该顶点。其余最短路径(第k次)的特点：再下一条路径长度次短(第2次)求最短路径的迪杰斯特拉算法：

设置辅助数组Dist，其中每个分量Dist[k]表示

当前所求得的从源点到其余各顶点k的最短路径。求最短路径的迪杰斯特拉算法：设置辅助数组Dist，其中每1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。2）修改其它各顶点的Dist[k]值。假设求得最短路径的顶点为u，若Dist[u]+G.arcs[u][k]<Dist[k]则将Dist[k]改为Dist[u]+G.arcs[u][k]。V0和k之间存在弧V0和k之间不存在弧其中的最小值即为最短路径的长度。1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最求每一对顶点之间的最短路径弗洛伊德算法的基本思想是：

从vi

到vj

的所有可能存在的路径中，选出一条长度最短的路径求每一对顶点之间的最短路径弗洛伊德算法的基本思想是：顶点集为V={v1,v2,...vn}第0步:若<vi,vj>存在,则存在路径{vi,vj}//路径中不含其它顶点,相当于中间点集U={}A0[i][j]=G.arcs[i][j](编程序时不写上标，即为A[i][j]=G.arcs[i][j])第1步:若<vi,v1>,<v1,vj>存在，则存在路径{vi,v1,vj}//路径中所含顶点序号不大于1,相当于中间点集U={v1}A1[i][j]=MIN{A0[i][j],A0[i][1]+A0[1][j]}第2步:若{vi,…,v2},{v2,…,vj}存在，则存在一条路径{vi,…,v2,…vj}//路径中所含顶点序号不大于2号,相当于中间点集U={v1,vn}A1[i][j]=MIN{A0[i][j],A0[i][1]+A0[1][j]}…第n步:若{vi,…,vn},{vn,…,vj}存在，则存在一条路径{vi,…,vn,…vj}//路径中所含顶点序号不大于n号,相当于中间点集U=V,为最短路径An[i][j]=MIN{An-1[i][j],An-1[i][n]+An-1[n][j]}顶点集为V={v1,v2,...vn}图的类型定义n(n≥0)个元素的有限集合图的类型定义n(n≥0)个元素的有限集合基本术语基本术语

图是由一个顶点集V和一个弧集VR构成的数据结构Graph=(V,{VR})其中:VR＝{<v,w>|v,w∈V且P(v,w)}<v,w>表示从v到w的一条弧，并称v为弧尾，w为弧头谓词P(v,w)

定义了弧<v,w>的意义或信息图是由一个顶点集V和一个弧集VR构成的数据结

由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图

ABECD

例如:

G1=(V1,{VR1})其中:V1={A,B,C,D,E}VR1={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}由于“弧”是有方向的，因此称由若有<v,w>VR,必有<w,v>VR,则称(v,w)为顶点v和顶点w之间存在一条边

BCADFE由顶点集和边集构成的图称作无向图例如:

G2=(V2,{VR2})V2={A,B,C,D,E,F}VR2={<A,B>,<A,E>,<B,E>,<C,D>,<D,F>,<B,F>,<C,F>}若有<v,w>VR,必B名词和术语网、子图

完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林关节点、重连通图重连通分量、连通度名词和术语网、子图完全图、稀疏图、稠密图邻接点、AEFBBC设图G=(V,VR)和图G=(V,VR),且VV,VRVR,则称

G为G的子图ABECF1597211132弧或边带权的图分别称作有向网或无向网AEFBBC设图G=(V,VR)和ABECF159721假设图中有

n

个顶点，e

条边，则

含有

e=n(n-1)/2条边的无向图称作无向完全图

含有

e=n(n-1)条弧的有向图称作有向完全图

若边或弧的个数

e<nlogn，则称作稀疏图，否则称作稠密图假设图中有n个顶点，e条边，则含有e=n(n

假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点，边(v,w)

ID(B)=3ID(A)=2和顶点v和w相关联和顶点v关联的边的数目定义为顶点的度ACDFEB假若顶点v和顶点w之间存在一条边，则称顶点v和w顶点的出度:以顶点v为弧尾的弧的数目ABECF有向图顶点的入度:以顶点v为弧头的弧的数目顶点的度(TD)=出度(OD)+入度(ID)ID(B)=2OD(B)=1TD(B)=3顶点的出度:以顶点v为弧尾的弧的数目ABECF有向图顶点的设图G=(V,{VR})中的一个顶点序列{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)VR1≤j≤m,则称从顶点u到顶点w之间存在一条路径。路径上边的数目称作路径长度ABECF长度为3的路径{A,B,C,F}设图G=(V,{VR})中的一个顶点序列ABECF长度为3的ABECF简单路径:序列中顶点不重复出现的路径简单回路:序列中第一个顶点和最后一个顶点相同的路径ABECF简单路径:序列中顶点不重复出现的路径简单回路:序列若图G中任意两个顶点之间都有路径相通，则称此图为连通图若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量BACDFEBACDFE若图G中任意两个顶点之间都有路径相通，则称此图为连通图若无向

若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图,ABECFABECF对有向图，

否则，其各个强连通子图称作它的强连通分量若任假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林BACDFE假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点

没有关节点的连通图被称为重连通图

若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点没有关节点的连通图被称为重连

一个连通图G如果不是重连通图，那么它可以包括几个重连通分量若依次删除一个连通图中的

1,2,…,k-1个顶点后,该图仍连通,删除第k个顶点后该图成为不连通的,则称该图的连通度为k一个连通图G如果不是重连通图，结构的建立和销毁插入或删除顶点对邻接点的操作对顶点的访问操作顶点的遍历插入和删除弧基本操作结构的建立和销毁插入或删除顶点对邻接点的操作对顶点的访问操作CreatGraph(&G,V,VR)://按定义(V,VR)构造图DestroyGraph(&G)://销毁图结构的建立和销毁CreatGraph(&G,V,VR):DestroyG对顶点的访问操作LocateVex(G,u);

//若G中存在顶点u，则返回该顶点在

//图中“位置”；否则返回其它信息GetVex(G,v);

//返回v的值PutVex(&G,v,value);//对v赋值value对顶点的访问操作LocateVex(G,u);GetV对邻接点的操作FirstAdjVex(G,v);

//返回v的“第一个邻接点”。若该顶点

//在G中没有邻接点，则返回“空”NextAdjVex(G,v,w);

//返回v的（相对于w的）“下一个邻接

//点”。若w是v的最后一个邻接点，则

//返回“空”对邻接点的操作FirstAdjVex(G,v);Next插入或删除顶点InsertVex(&G,v);

//在图G中增添新顶点vDeleteVex(&G,v);//删除G中顶点v及其相关的弧插入或删除顶点InsertVex(&G,v);Delet插入和删除弧InsertArc(&G,v,w);

//在G中增添弧<v,w>，若G是无向的，

//则还增添对称弧<w,v>DeleteArc(&G,v,w);

//在G中删除弧<v,w>，若G是无向的，

//则还删除对称弧<w,v>插入和删除弧InsertArc(&G,v,w);Del遍历DFSTraverse(G,v,Visit());

//从顶点v起深度优先遍历图G，并对每

//个顶点调用函数Visit一次且仅一次BFSTraverse(G,v,Visit());

//从顶点v起广度优先遍历图G，并对每

//个顶点调用函数Visit一次且仅一次遍历DFSTraverse(G,v,Visit图的存储表示一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示四、有向图的十字链表存储表示五、无向图的邻接多重表存储表示三、图的逆邻接表存储表示图的存储表示一、图的数组(邻接矩阵)存储表示二、图的邻接表存Aij={0(i,j)VR1(i,j)VR图的数组(邻接矩阵)存储表示BACDFE定义:矩阵的元素为无向图的邻接矩阵是对称矩阵Aij={0(i,j)VR1(i,j)VR图的数有向图的邻接矩阵为非对称矩阵ABECD有向图的邻接矩阵为非对称矩阵ABECD在有向图中,统计第i

行

1的个数可得顶点i

的出度，统计第j列

1的个数可得顶点j

的入度在无向图中,统计第i行(列)1的个数可得顶点i的度在有向图中,统计第i行1的个网（边或弧带权值的图）的数组(邻接矩阵)存储表示如下网（边或弧带权值的图）的数组0A141B0452C353D254E015F123BACDFE图的邻接表存储表示0A14BACDFE图的邻接01234有向图的邻接表1423012ABCDEABECD可见，在有向图的邻接表中不易找到指向该顶点的弧01234有向图的邻接表1ABECD在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧图的逆邻接表存储表示ABCDE033420012341ABECD在有向图的图的逆邻接表存储表示A0334有向图的十字链表存储表示

弧的结点结构弧尾顶点位置弧头顶点位置弧的相关信息指向下一个有相同弧头的结点指向下一个有相同弧尾的结点typedefstructArcBox{//弧的结构表示

inttailvex,headvex;InfoType*info;structArcBox*hlink,*tlink;

}VexNode;有向图的十字链表存储表示弧的结点结构弧尾顶点位置弧头顶点顶点的结点结构顶点信息数据指向该顶点的第一条入弧指向该顶点的第一条出弧typedefstructVexNode{//顶点的结构表示

VertexTypedata;ArcBox*firstin,*firstout;}VexNode;顶点的结点结构顶点信息数据指向该顶点typedefstruct{VexNodexlist[MAX_VERTEX_NUM];//顶点结点(表头向量)

intvexnum,arcnum;//有向图的当前顶点数和弧数}OLGraph;有向图的结构表示(十字链表)typedefstruct{有向图的结构表示(十字链表对右边所示的有向图G,十字链表表示如下:对右边所示的有向图G,十字链表表示如下:无向图的邻接多重表存储表示typedefstructEbox{VisitIfmark;//访问标记

intivex,jvex;//该边依附的两个顶点的位置

structEBox*ilink,*jlink;InfoType*info;//该边信息指针}EBox;边的结构表示无向图的邻接多重表存储表示typedefstructEbtypedefstruct{//邻接多重表

VexBoxadjmulist[MAX_VERTEX_NUM];

intvexnum,edgenum;

}AMLGraph;顶点的结构表示typedefstructVexBox{VertexTypedata;EBox*firstedge;//指向第一条依附该顶点的边}VexBox;无向图的结构表示typedefstruct{//邻接多重表顶点的结对右边所示的无向图G,邻接多重表表示如下:对右边所示的无向图G,邻接多重表表示如下:图的遍历深度优先遍历DFS(DepthFirstSearch)

广度优先遍历BFS(BreadthFirstSearch)广度优先遍历BFS课件深度优先遍历DFS(DepthFirstSearch)深度优先遍历的示例前进回退ACDEGBFIHACDEGBFIH123456789123456789深度优先遍历过程深度优先生成树深度优先遍历DFS(DepthFirstSearch)深广度优先遍历BFS(BreadthFirstSearch)广度优先遍历的示例ACDEGBFIHACDEGBFH123456789123456789广度优先遍历过程广度优先生成树I广度优先遍历BFS(BreadthFirstSearchvoidtraverse(intn,Graphg){for(v=0;v<n;v++)visited[v]=false;for(v=0;v<n;v++)if(!visited[v])dfs(v,g)或bfs(v,g);}voidtraverse(intn,Graphgvoiddfs(intv,Graphg){cout<<GetVex(g,v);visited[v]=true;

for(w=FirstAdjVex(g,v);w>=0;w=NextAdjVex(g,v,w)){ if(!visited[w])dfs(w,g)}}voiddfs(intv,Graphg){voidbfs(intv,Graphg){cout<<GetVex(g,v);InitQueue(q);EnQueue(q,v);visited[v]=true;while(!Empty(q)){DeQueue(q,v);

for(w=FirstAdjVex(g,v);w>=0;w=NextAdjVex(g,v,w)){ if(!visited[w]){cout<<GetVex(g,w);EnQueue(q,w);visited[w]=true;}}};voidbfs(intv,Graphg){最小代价生成树

(minimumcostspanningtree)最小代价生成树

(minimumcostspanning

假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建

n-1条线路，如何在最节省经费的前提下建立这个通讯网？问题假设要在n个城市之间建立通讯联络网，则连通

构造网的一棵最小生成树，即：在e

条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小该问题等价于构造网的一棵最小生成树，即：在e构造最小生成树的准则必须使用且仅使用该网络中的n-1

条边来联结网络中的n

个顶点不能使用产生回路的边各边上的权值的总和达到最小构造最小生成树的准则算法二：克鲁斯卡尔算法

(Kruskal)

算法一：普里姆算法

(Prim)算法二：克鲁斯卡尔算法算法一：普里姆算法普里姆算法的基本思想广度优先遍历BFS课件

1.取图中任意一个顶点v作为生成树的根，之后往生成树上添加新的顶点w1.取图中任意一个顶点v作为

2.在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集U

和尚未落在生成树上的顶点集V-U

，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边(v,w)这里v属于V，w属于UUV-U2.在生成树的构造过程中，图中n个顶

3.之后继续往生成树上添加顶点，直至生成树上含有n-1

个顶点为止3.之后继续往生成树上添加顶abcdegf195141827168213ae12dcbgf7148531621所得生成树权值和=14+8+3+5+16+21=67abcdegf195141827168213ae12dcbg252510504613228102514242216185046132504613210原图(a)