图的存储遍历及最小生成树.docx

图的存储遍历及最小生成树.docx

《图的存储遍历及最小生成树.docx》由会员分享，可在线阅读，更多相关《图的存储遍历及最小生成树.docx（20页珍藏版）》请在冰点文库上搜索。

图的存储遍历及最小生成树

图的存储、遍历及最小生成树

图的定义

图（Graph）是由一个用线或边连接在一起的顶点或节点的集合。

是一种比线性表和树更为复杂的非线性数据结构，可称为图状结构或网状结构，前面讨论的线性表和树都可以看成是图的简单情况。

   　图G由两个集合V和E组成，记为：

       G=（V，E）

　　其中：

　　V是顶点的有穷非空集合，

　　E是V中顶点偶对（称为边）的有穷集。

   　通常，也将图G的顶点集和边集分别记为V（G）和E（G）。

E（G）可以是空集。

若E（G）为空，则图G只有顶点而没有边。

有向图和无向图

1．有向图

   　如图7.1G2所示每条边都是有方向的，则称G为有向图（Digraph）。

（1）有向边的表示

   　有向边又称为弧，通常用尖括弧表示一条有向边，表示从顶点v到w的一段弧，v称为边的始点（或尾顶点），w称为边的终点，（或头顶点），和代表两条不同的弧。

 【例】表示一条有向边，vi是边的始点（起点），vj是边的终点。

注意:

和是两条不同的有向边。

（2）有向图的表示

 【例】上面7.1图中G2是一个有向图。

图中边的方向是用从始点指向终点的箭头表示的，该图的顶点集和边集分别为：

顶点集V={v1,v2,v3}

弧集E={,,,}。

注意:

与表示两条不同的边。

2．无向图

   　如图7.1G1中所示的每条边都是没有方向的，则称G为无向图（Undigraph）。

（1）无向边的表示

   　通常用圆括号表示无向边，（v,w）表示顶点v和w间相连的边。

在无向图中（v,w）和（w,v）表示同一条边，如果顶点v,w之间有边（v,w），则v,w互称为邻接点。

 【例】无序对（vi，vj）和（vj，vi）表示同一条边。

（2）无向图的表示

 【例】上面7.1图中的G1是无向图，它们的顶点集和边集分别为：

顶点集：

V={v1,v2,v3,v4}

边集：

E={（v1,v2）,（v1,v3）,（v1,v4）,（v2,v3）,（v3,v4）}

注意:

（v2,v1）与（v1,v2）表示同一条边，（v2,v3）与（v3,v2）也表示同一条边，等等。

3．图G的顶点数n和边数e的关系

（1）若G是无向图，则0≤e≤n（n-1）/2

   　恰有n（n-1）/2条边的无向图称无向完全图（Undireet-edCompleteGraph）

（2）若G是有向图，则0≤e≤n（n-1）。

   　恰有n（n-1）条边的有向图称为有向完全图（DirectedCompleteGraph）。

 注意：

   　完全图具有最多的边数。

任意一对顶点间均有边相连。

4.对图的讨论中我们对图作一些限制：

第一，图中不能有从顶点自身到自身的边（即自身环），就是说不应有形如（vx,vx）的边或的弧。

第二，两个顶点vt和vu之相关联的边不能多于一条。

图的邻接矩阵

1．图的邻接矩阵表示法

   　在图的邻接矩阵表示法中：

　①用邻接矩阵表示顶点间的相邻关系

　②用一个顺序表来存储顶点信息

2．图的邻接矩阵（AdacencyMatrix）

   　设G=（V，E）是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：

【例】下图中无向图G5和有向图G6的邻接矩阵分别为Al和A2。

从图的邻接矩阵表示法中可以得到如下结论：

（1）对于n个顶点的无向图，有A（i，i）=0，1≤i≤n。

（2）无向图的邻接矩阵是对称的，即A（i，j）=A（j，i），1≤i≤n，1≤j≤n。

（3）有向图的邻接矩阵不一定对称的。

因此用邻接矩阵来表示一个具有n个顶点的有向图时需要n2个单位来存储邻接矩阵；对有n个顶点的无向图则需存入上（下）三角形，故只需n（n+1）/2个单位。

（4）无向图的邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度TD（vi）。

（5）有向图的邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的出度OD（vi）[或入度ID（vi）]。

3．网（带权值的图）的邻接矩阵

   　若G是网络，则邻接矩阵可定义为：

   其中：

     wij表示边上的权值；

     ∞表示一个计算机允许的、大于所有边上权值的数。

【例】下面（a）是一个带权图，（b）是对应的邻接矩阵的存储结构

       （a）带权图                       （b）邻接矩阵

4．邻接矩阵的图类

constintMaxVertices=10;

constintMaxWeight=32767;

classAdjMWGraph

 {private:

  intVertices[10];      //顶点信息的数组

  intEdge[MaxVertices][MaxVertices];    //边的权值信息的矩阵

  intnumE;      //当前的边数

  intnumV;      //当前的顶点数

  public:

………;     //公有函数

  private:

………;     //私有函数

 }

 注意：

　   ①在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点表及顶点数等均可省略）。

   　②当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeTyPe可定义为值为0和1的枚举类型。

   　③无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可压缩存储。

   　④邻接矩阵表示法的空间复杂度S（n）=0（n2）。

图的邻接链表

邻接链表（AdjacencyList）是图的一种链式存储结构，与树型结构中的孩子链表相似。

通常邻接链表也称邻接表。

1．邻接表的结点结构

边结点结构

   　邻接表中每个表结点均有两个域:

　①邻接点域adjvex

　　存放与vi相邻接的顶点vj的序号j。

　②链域next

　　将邻接表的所有表结点链在一起。

 注意：

　   如果带权图，则在表结点中还应增加一个保存权值等相关信息info。

2．邻接表的表示

   　对于无向图，vi的邻接表中每个表结点都对应于与vi相关联的一条边。

因此，将邻接表的表头向量称为顶点表。

将无向图的邻接表称为边表。

 注意：

n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。

   　对于有向图，vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。

因此，将有向图的邻接表称为出边表。

 注意：

n个顶点e条边的有向图，它的邻接表表示中有n个顶点表结点和e个边表结点。

4．有向图的逆邻接表

   在有向图中，为图中每个顶点vi建立一个入边表的方法称逆邻接表表示法。

   入边表中的每个表结点均对应一条以vi为终点（即射入vi）的边。

【例】

注意：

n个顶点e条边的有向图，它的接表表示中有n个顶点表结点和e个边表结点。

图的遍历

从图中某一顶点出发，按某种搜索方法访遍其余顶点，且使每一顶点仅被访问一次。

这一过程称为图的遍历。

　　遍历图的基本搜索方法有两种：

深度优先搜索DFS（DepthFirstSearch）和广度优先搜索BFS（BroadFirstSearch）。

这两种方法都适用于有向图和无向图。

图的遍历算法设计需要考虑3个问题：

（1）图的特点没有首尾之分，所以算法的参考要指定访问的第一个顶点。

（2）对图的遍历路径有可能构成一个回路，从而造成死循环，所以算法设计要考虑遍历路径可能的回路问题。

  （3）一个顶点可能和若干个顶点都是想邻顶点，要使一个顶点的所有想邻顶点按照某种次序被访问。

　　对于连通图，从初始顶点出发一定存在路径和图中的所有其他顶点相连，所以对于连通图从初始顶点出发一定可以遍历该图。

图的深度优先遍历

　　图的深度优先遍历DFS算法是每次在访问完当前顶点后，首先访问当前顶点的一个未被访问过的邻接顶点，然后去访问这个邻接点的一个未被访问过的邻接点，这样的算法是一个递归算法。

1.连通图的深度优先遍历算法思想。

（1）访问初始顶点v并标记顶点v已访问。

（2）查找顶点v的第一个邻接顶点w。

（3）若顶点v的邻接顶点w存在，则继续执行；否则回溯到v，再找v的另外一个未访问过的邻接点。

（4）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。

（5）继续查找顶点w的下一个邻接顶点wi，如果v取值wi转到步骤（3）。

直到连通图中所有顶点全部访问过为止。

【例】现以图7.9（a）为例说明深度过优先搜索过程。

假定v1是出发点，首先访问v1。

因v1有两个邻接点v2、v3均未被访问过，可以选择v2作为新的出发点，访问v2之后，再找v2的未访问过的邻接点。

同v2邻接的有v1、v4、v5，其中v1已被访问过，而v4、v5尚未被访问过，可以v4选择作为新的出发点。

重复上述搜索过程，继续依次访问v8、v5。

访问v5之后，由于与v5相邻的顶点均已被访问过，搜索退回到v8。

由于v8、v4、v2都是已被访问的邻接点，所以搜索过程连续地从v8退回到v4，再退回到v2，最后退回到v1。

这时选择v1的未被访问过的邻接点v3，继续往下搜索，依次访问v3、v6、v7，从而遍历了图中全部顶点。

在这个过程中得到的顶点的访问序列为：

具体算法演示请点击查看

2.深度优先遍历算法

（1）邻接矩阵的深度优先遍历算法：

【算法7.1】

voidAdjMWGraph:

:

Depth（intv,intvisited[]）

{cout<<""\n顶点"<

"<

visited[v]=1;

for（intcol=0;col

{if（Edge[v][col]==0||Edge[v][col]==MaxWeight）continue;

if（!

visited[col]）Delpth（col,visited）;

}

}

　　故用邻接矩阵表示图时，搜索一个顶点的所有邻接点需花费O（n）时间，则从n个顶点出发搜索的时间应为O（n2），即DFS算法的时间复杂度是（n2）。

（2）邻接链表的深度优先遍历算法：

【算法7.2】

VoidAdjTWGraph:

:

DepthFirst（intv,intvisited[]）

{intvj;Edge*p;

cout<

visited[v]=1;

p=Vertices[v].adj;//取v的邻接边结点

while（p!

=NULL）

{vj=p->dest;//取v的邻接点编号

if（visited[vj]==0）DepthFirst（vj,visited）;

p=p->next;//取下一个邻接边结点

}

}

　　使用邻接链表来表示图时，其DFS算法的时间复杂度为O（n+e），此处e为无向图中边的数目或有向图中弧的数目。

图的广度优先遍历

　　图的广度优先遍历BFS算法是一个分层搜索的过程，和树的层序遍历算法类同，它也需要一个队列以保持遍历过的顶点顺序，以便按出队的顺序再去访问这些顶点的邻接顶点。

1.连通图的广度优先遍历算法思想。

（1）顶点v入队列。

（2）当队列非空时则继续执行，否则算法结束。

（3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。

（4）查找顶点v的第一个邻接顶点col。

（5）若v的邻接顶点col未被访问过的，则col入队列。

（6）继续查找顶点v的另一个新的邻接顶点col，转到步骤（5）。

直到顶点v的所有未被访问过的邻接点处理完。

转到步骤

（2）。

【例】下面以图（a）为例说明广度优先搜索的过程。

首先从起点v1出发访问v1。

v1有两个未曾访问的邻接点v2和v3。

先访问v2，再访问v3。

然后再先访问v2的未曾访问过的邻接点v4、v5及v3的未曾访问过的邻接v6和v7，最后访问v4的未曾访问过的邻接点v8。

至此图中所有顶点均已被访问过。

得到的顶点访问序列为：

具体算法演示请点击查看

2.广度优先遍历算法

（1）邻接矩阵的广度优先遍历算法：

【算法7.1】

voidAdjMWGraph:

:

Depth（intv,intvisited[]）

 { sqQueue< int>q;    //定义队列queue

  q.EnQueue（v）;    //顶点v入队列

  while（!

q.IsEmpty（））    //当队列非空时循环

    { v=q.DeQueue（）;    //出队列得到队头顶点u

     cout<

"<

     visited[col]=1;//标记顶点v已访问

     for（intcol=0;col

     if（Edge[v][col]>0;&&Edge[v][col]

     q.EnQueue（col）;

  }

  cout<

"<<"endl;

 };

　　邻接矩阵表示图时，搜索一个顶点的所有邻接点需花费O（n）时间，则从n个顶点出发搜索的时间应为O（n2），即BFS算法的时间复杂度是（n2）。

（2）邻接链表的深度优先遍历算法：

【算法7.2】

voidAdjTWGraph:

:

BroadFirst（intv,intvisited[]）

 { intvj; Edge*p; SqQueueQ;Q.EnQueue（v）;

  while（!

Q.IsEmpty（））       //队列不空，循环

   { v=Q.DeQueue（）;    //出队并且访问顶点v

   cout<

   p=Vertices[v].adj;      //取v的邻接边结点

  while（p!

=NULL） {vj=p->dest;  //取v的邻接点编号vj

   if（visited[vj]==0）Q.EnQueue（vj）;      //vj未访问，入队

    p=p->next;      //取下一个邻接边结点

  }

  }

 }

　　使用邻接链表来表示图时，其BFS算法的时间复杂度为O（n+e），此处e为无向图中边的数目或有向图中弧的数目。

图的最小生成树

1、生成树的定义

   若从图的某顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图，称作该图的生成树。

（此定义不仅仅适用于无向图，对有向图同样适用。

）

（1）若G是强连通的有向图，则从其中任一顶点v出发，都可以访问遍G中的所有顶点，从而得到以v为根的生成树。

（2）若G是有根的有向图，设根为v，则从根v出发可以完成对G的遍历，得到G的以v为根的生成树。

【例】下图中（a）图是以v0为根的有向图，它的DFS生成树和BPS生成树分别如图（b）和（c）所示。

（3）若G是非连通的无向图，则要若干次从外部调用DFS（或BFS）算法，才能完成对G的遍历。

每一次外部调用，只能访问到G的一个连通分量的顶点集，这些顶点和遍历时所经过的边构成了该连通分量的一棵DFS（或BPS）生成树。

G的各个连通分量的DFS（或BFS）生成树组成了G的DFS（或BFS）生成森林。

（4）若G是非强连通的有向图，且源点又不是有向图的根，则遍历时一般也只能得到该有向图的生成森林。

【例】对图7.9中的图G，当按深度和广度优先搜索法进行遍历就可以得到图7.10所示的两种不同的生成树，并分别称为深度优先生成树和广度优先生成树。

2.最小生成树

如果连通图是一个网络，称该网络中所有生成树中权值总和最小的生成树为最小生成树（也称最小代价生成树）。

图7.12给出图7.11（a）的几棵生成树。

其中（a）的权为26，（b）的权为16，（c）的权为15，可以证明（c）为一棵最小生成树。

3、最小生成树性质（MST性质）

（1）MST性质

   　最小生成树性质：

设G=（V，E）是一个连通网络，U是顶点集V的一个真子集。

若（u，v）是G中所有的一个端点在U（u∈U）里、另一个端点不在U（即v∈V-U）里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边（u，v）。

（2）MST性质的证明

   　为方便说明，先作以下约定：

①将集合U中的顶点看作是红色顶点，②而V-U中的顶点看作是蓝色顶点，③连接红点和蓝点的边看作是紫色边，④权最小的紫边称为轻边（即权重最"轻"的边）。

于是，MST性质中所述的边（u，v）就可简称为轻边。

用反证法证明MST性质：

　　假设G中任何一棵MST都不含轻边（u，v）。

则若T是G的一棵MST，则它不含此轻边。

   由于T是包含了G中所有顶点的连通图，所以T中必有一条从红点u到蓝点v的路径P，且P上必有一条紫边（u'，v'）连接红点集和蓝点集，否则u和v不连通。

当把轻边（u，v）加入树T时，该轻边和P必构成了一个回路。

删去紫边（u'，v'）后回路亦消除，由此可得另一生成树T'。

   　T'和T的差别仅在于T'用轻边（u，v）取代了T中权重可能更大的紫边（u'，v'）。

因为w（u，v）≤w（u'，v'），所以

   w（T'）=w（T）+w（u，v）-w（u'，v'）≤w（T）

故T'亦是G的MST，它包含边（u，v），这与假设矛盾。

   　所以，MST性质成立。

4、普里姆（Prim）算法

（1）算法思想

   　T=（U，TE）是存放MST的集合。

　　①T的初值是（{r}，￠）

　　 即最小生成树初始时只有一个红点r，没有红边。

　　②T经过n-1次如下步骤操作，最后得到一棵含n个顶点，n-1条边的最小生成树

   　⒈选择紫边集中一条轻边并扩充进T

　　⒉将轻边连接的蓝点改红点

　　⒊将轻边改红边

   　⒋修改紫边集

（2）较小紫边集的构造

   　若当前形成的T中有k个顶点，|U|=k，|V-u|=n-k，故可能的紫边数目是k（n-k）。

从如此大的紫边集中选择轻边是低效的。

因此，必须构造较小的紫边集。

   　对于每个蓝点v∈V-U，从v到各红点的紫边中，只有最短的那一条才有可能是轻边。

因此，只须保留所有n-k个蓝点所关联的最短紫边作为轻边的候选集即可。

（3）候选紫边集合的修改

   　当把轻边（u，v）扩充到T时，因为v由蓝变红，故对每个剩余的蓝点j，边（v，j）就由非紫边变为紫边，这条新紫边的长度可能小于蓝点j原来所关联的最短紫边的长度。

因此，用长度更小的新紫边取代那些原有的最短紫边。

（4）算法的执行过程

注意：

若候选轻边集中的轻边不止一条，可任选其中的一条扩充到T中。

连通网的最小生成树不一定是惟一的，但它们的权相等。

【例】在上图（e）中，若选取的轻边是（2，4）而不是（2，1）时，则得到如图（h）所示的另一棵MST。

 （5）算法特点

   　该算法的特点是当前形成的集合T始终是一棵树。

将T中U和TE分别看作红点和红边集，V-U看作蓝点集。

算法的每一步均是在连接红、蓝点集的紫边中选择一条轻边扩充进T中。

MST性质保证了此边是安全的。

T从任意的根r开始，并逐渐生长直至U=V，即T包含了C中所有的顶点为止。

MST性质确保此时的T是G的一棵MST。

因为每次添加的边是使树中的权尽可能小，因此这是一种"贪心"的策略。

（7）算法分析

   　该算法的时间复杂度为O（n2）。

与图中边数无关，该算法适合于稠密图。

5、克鲁斯卡尔（Kruskal）算法

（1）算法思想

　　①T的初始状态

   　  只有n个顶点而无边的森林T=（V，￠）

　　②按边长递增的顺序选择E中的n-1安全边（u，v）并加入T，生成MST

注意：

   　安全边指两个端点分别是森林T里两棵树中的顶点的边。

加入安全边，可将森林中的两棵树连接成一棵更大的树

   　因为每一次添加到T中的边均是当前权值最小的安全边，MST性质也能保证最终的T是一棵最小生成树。

（2）算法特点

   　该算法的特点是：

当前形成的集合T除最后的结果外，始终是一个森林。

（3）Kruskal算法简单描述

T=（V,Φ）；

While（T中所有边数

{从E中选取当前最短边（u,v）；

从E中删去边（u,v）；

If（（u,v）并入T之后不产生回路）将（u,v）并入T中；

}

具体算法演示请点击查看【算法演示】

（4）用Kruskal算法构造最小生成树的过程

（5）算法分析

　该算法的时间复杂度为O（elge）。

Kruskal算法的时间主要取决于边数。

它较适合于稀疏图。