数据结构第七章概况.docx
《数据结构第七章概况.docx》由会员分享，可在线阅读，更多相关《数据结构第七章概况.docx（24页珍藏版）》请在冰点文库上搜索。
数据结构第七章概况
第七章图
7.1图的概念
图的定义：
图G=（V,E）
V是顶点的有穷非空集合。
E是偶对（边）有穷集合。
相关术语：
顶点、弧、弧头、弧尾、有向图、无向图、无向完全图、有向完全图、稀疏图、稠密图、权、网络、邻接点、度、入度、出度、子图、路径、路径长度、连通图、强连通图、连通分量、强连通分量、生成树。
7.2图的存储
1.邻接矩阵表示法
邻接矩阵：
表示顶点之间相互关系的矩阵。
设G=（V,E），具有n个顶点，则：
|1（Vi,Vj）或是边
A[i,j]=|
|0（Vi,Vj）或不是边
若G是网络，则
|wij（Vi,Vj）或是边
A[i,j]=|
|0,∞（Vi,Vj）或不是边
存储结构：
typedefstruct
{charvexs[n];
adjvexarcs[n][n];
}graph;
无向图（网络）是对称的，可采用压缩存储方法，仅存下三角矩阵（不包括对角线）。
创建网络：
CREATGRAPH（graph*ga）
{inti,j,k;
floatw;
for（i=0;iga->vexs[i]=getchar（）;
for（i=0;ifor（j=0;jga->arcs[n][n]=0;
for（k=0;k{scanf（%d%d%f,&i,&j,&w）;
ga->arcs[i][j]=w;
ga->arcs[j][i]=w;
}
}
显然，邻接矩阵的时间复杂度T（n）=O（n2）。
显然，邻接矩阵的空间复杂度T（n）=O（n2）。
2.邻接表表示法
邻接表：
对G中每个顶点Vi，把所有邻接于Vi的顶点Vj拉成一个链表，此表称Vi的邻接表。
结点结构：
边表adjvex|next
结点序号指针
顶点表vertex|link
顶点信息指针
边表：
无向图的邻接表。
出边表：
有向图的邻接表。
入边表：
逆邻接表。
顶点表：
邻接表的表头向量。
结点定义：
typedefstructnode
{intadjvex;
structnode*next;
}edgenode;
typedefstructnode
{vextypevertex;
edgenode*link;
}vexnode;
vexnodega[n];
建邻接表：
CREATADJLIST（vexnodega[]）
{
inti,j,k;
edgenode*s;
for（i=0;i{ga->vextex=getchar（）;
ga[i].link=NULL;
}
for（k=0;k{
scanf（%d%d,&i,&j）;
s=malloc（sizeof（edgenode））;//头插法
s->adjvex=j;
s->next=ga[i].link;
ga[i].link=s;
s=malloc（sizeof（edgenode））;//头插法
s->adjvex=i;
s->next=ga[j].link;
ga[j].link=s;
}
}
简单结论：
①一个图的邻接矩阵是唯一的，而邻接表不唯一。
②每个边表对应矩阵的一行或一列，结点个数为非0元素的个数。
③若G是无向图，有2e个边表结点。
若G是有向图，有e个边表结点（入边表或出边表）。
3.十字链表
4.多重链表
7.3图的遍历
图的遍历：
从某个顶点出发，沿着某条路径对图中每个顶点各做一次访问。
对于连通图，可一次访问到所有顶点，而非连通图，则需多次遍历。
为避免重复访问一个结点，可设一布尔向量visited[n]标记是否访问过。
1.深度优先搜索DFS
深度优先搜索类似于树的前序遍历。
首先，从初态Vi出发，访问Vi，标记已访问。
然后，从Vi出发搜索Vi的每一个邻接点Vj，若Vj未访问，则以Vj为新出发点继续搜索。
显然，上述定义是递归的，特点是尽可能对纵深方向搜索。
遍历所得到的顶点序列称深度优先搜索（DFS）序列。
遍历算法：
//基于邻接矩阵的DFS
intvisited[n];
graphg;
voidDFS（inti）
{intj;
print（%c,g.vexs[i]）;
visited[i]=TRUE;
for（j=0;jif（（g.arcs[i][j]==1）&&（!
visited[j]））
DFS[j];
}
//基于邻接表上的DFSL
vexnodeg1[n];
voidDFS（inti）
{intj;
edgenode*p;
print（%c,g1.vertex）
visited[i]=TRUE;
p=g1[i].link;
while（p）
{if（!
visited[p->adjvex]）
DFSL（p->adjvex）;
p=p->next;
}
}
算法分析：
DFS算法----T（n）=O（n2）
DFSL算法---T（n）=O（n+e）
算法DFS和DFSL所用的辅助空间是标志数组和实现递归所用的栈，因此，S（n）=O（n）。
图的邻接矩阵是唯一的，所以DFS序列是唯一的。
图的邻接表不是唯一的，所以DFSL序列不唯一。
2.广度优先搜索BFS
广度优先搜索类似于树的按层遍历。
首先，从初态Vi出发，访问Vi，标记已访问。
然后，从Vi出发搜索Vi的所有邻接点W1,W2,……Wt，然后，依次访问与W1,W2,……Wt邻接的未访问过的顶点。
依此类推……
显然，上述方法的特点是尽可能横向搜索因此称广度优先搜索（BFS）。
遍历所得到的顶点序列称广度优先搜索（BFS）序列。
遍历算法：
需引入一个队列保存已访问过的结点（W1,W2,……Wt）。
//基于邻接矩阵的BFS
voidBFS（intk）
{inti,j;
SETNULL（Q）;
print（%c\n,g.vexs[k]）
visited[k]=TRUE;
ENQUEUE（Q,k）;
while（!
EMPTY（Q））
{i=DEQUEUE（Q）;
for（j=0;jif（（g.arcs[i][j]==1）&&（!
visited[j]））
{print（%c\n,g.vexs[j]）;
visited[j]=TRUE;
ENQUEUE（Q,j）;
}
}
}
//基于邻接表上的BFSL
voidBFSL（intk）
{
inti;
edgenode*p;
SETNULL（Q）;
print（%c\n,g1[k].vertex）;
visited[k]=TRUE;
ENQUEUE（Q,k）;
while（!
EMPTY（Q））
{i=DEQUEUE（Q）;
p=g1[i].link;
while（p）
{if（!
visited[p->adjvex]）
{print（%c\n,g1[p->adjvex].vertex）;
visited[p->adjvex]=TRUE;
ENQUEUE（Q,p->adjvex）;
}
p=p->next;
}
}
}
算法分析：
BFS算法----T（n）=O（n2）
BFSL算法---T（n）=O（n+e）
算法BFS和BFSL所用的辅助空间是标志数组和实现算法所需的队列，因此，S（n）=O（n）。
图的邻接矩阵是唯一的，所以BFS序列是唯一的。
图的邻接表不是唯一的，所以BFSL序列不唯一。
3.非连通图的遍历
若一个无向图是非连通图，则从图中任意一个顶点出发都不能访问到图中的所有顶点。
只能从每个连通分量中选一个顶点作为出发点进行搜索，便可访问到非连通图的所有顶点，因此，需调用前述的DFS、DFSL或BFS、BFSL算法。
//调用DFS的非连通图的遍历算法
voidTRAVER（）
{
inti;
for（i=0;ivisited[i]=FALSE;
for（i=0;i{if（!
visited[i]）
DFS（i）;
print（compend\n）;
}
}
以上讨论的遍历算法对有向图也是适用的。
7.4生成树和最小生成树
树（tree）：
在图中，树定义为无回路的连通图。
有些图看起来不是树，但若选取一个结点做根，便转化为树。
生成树：
连通图G的一个子图如果是一棵包含G的所有顶点的树，则称该子图为G的生成树。
简单结论：
①n个顶点的连通图至少有n-1条边，一定是无回路的的树。
②生成树是连通图的极小（边数最少）连通子图。
③在生成树中，去掉任何一条边则变为非连通图，添加一条边就必定出现回路。
图G=（V,E）是连通图，如何求得生成树？
在对G的遍历中，从Vi出发搜索到Vj，并访问。
这样，必经过（Vi,Vj），除起点外，对其它n-1个顶点的的访问必经过n-1条边。
由n个顶点和n-1条边所构成的极小连通子图就是一棵生成树。
在遍历算法中（DFS、DFSL、BFS、BFSL）只要将打印稍作改动就可得到生成树的算法（将打印语句改成打印边（Vi,Vj）），分别称为DFS生成树BFS生成树。
从图的遍历角度而言，生成树还可以定义为：
生成树：
从图的某个顶点出发，在遍历时所经过的边和所有顶点构成的子图，称作该图的生成树。
此定义也适用于有向图。
简单结论：
①若G是非连通图，则需多次调用遍历算法，得到多个生成树，组成G的生成森林，分别称作DFS生成森林或BFS生成森林。
②若G是非连通的有向图，且出发点又不是有向图的根，则遍历时只能得到生成森林。
③图的生成树不唯一，从不同顶点出发，可得到不同的生成树。
最小生成树：
连通网络G=（V,E）边是带权的，我们把生成树各边的权值总和称为生成树的权，并把权值最小的生成树称为G的最小生成树（MinimunSpanningTree）。
典型应用：
n个城市的通讯网络问题？
把n个城市连接起来至少要有n-1条线路。
把n个城市连接起来最多要n（n-1）/2条线路。
如果用权代表两城市之间的线路长度或造价，那么，显然要选择n-1条线路使得线路总长最短或造价最低。
这就势必要构造该图的一棵最小生成树。
构造最小生成树的普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法：
Prim算法：
设G=（V,E），T=（U,TE）
①置T为任意一个顶点U={u0}，置初始候选边集，即关联于u0的边（另一端在V里）
②while（T中顶点数{
③从候选边集中选取最短的边（u,v）；
④将（u,v）扩充到T中，v也扩充到T中；
⑤调整候选的短边集；
}
改进算法：
设T中有k个顶点，则候选边数k（n-k），不适于全部搜索。
只需将n-k个∈V的点关联的边作候选边集即可。
结论：
连通网络的最小生成树不一定是唯一的，对于权值相等的候选边，可任选一短边扩充到T中，但它们的权值总和是相等的。
Prim算法适合于求稠密网的最小生成树。
存储结构：
typedefstruct//生成树格式
{intfromvex,endvex;//起点、终点
floatlength;//权值
}edge;
floatdist[n][n];
edgeT[n-1];//生成树n-1条边
算法实现：
T（n）=O（n2）
//Prim算法求最小生成树
#include
#include
#definen6//结点数
#definee10//边数
typedefintvextype;
typedefintadjtype;
vextypevexs[n];//顶点集
adjtypearcs[n][n];//邻接矩阵
typedefstruct//生成树格式
{intfromvex,endvex;
intlength;
}edge;
edgeT[n-1];//生成树n-1条边
voidCREATGRAPH（）//建立连通网络
{inti,j,k,w;
cout<<"请输入六个结点:
"<for（i=0;icin>>vexs[i];cout<<"输入完毕"<for（i=0;ifor（j=0;jarcs[i][j]=10000;//没有权值应为无穷大
cout<<"请输入起点,终点,权值"<for（k=0;k{cin>>i>>j>>w;//无向图
arcs[i][j]=w;
arcs[j][i]=w;
}
cout<}
voidPRIM（）
{intj,k,m,v,min,max=10000;
intd;
edgef;
for（j=1;j{T[j-1].fromvex=0;
T[j-1].endvex=j;
T[j-1].length=arcs[0][j];
}
for（k=0;k{min=max;
for（j=k;jif（T[j].length{min=T[j].length;
m=j;
}
f=T[m];T[m]=T[k];T[k]=f;
v=T[k].endvex;
for（j=k+1;j{d=arcs[v][T[j].endvex];
if（d{T[j].length=d;
T[j].fromvex=v;
}
}
}
}
voidmain（）
{
CREATGRAPH（）;
PRIM（）;
for（intt=0;tcout<}
Kruskal算法：
设G=（V,E），T=（U,TE）
①置T=（V,Φ）
②将G中所有的边按递增排序。
③依次将E中的一条边（u,v）加入T中，从E中删去（u,v）。
④加入（u,v）不产生回路，则将（u,v）并入T中，否则舍弃。
⑤重复③④。
结论：
连通网络的最小生成树不一定是唯一的，对于权值相等的候选边，可任选一短边扩充到T中，但它们的权值总和是相等的。
Kruskal算法适合于求稀疏网的最小生成树。
存储结构：
typedefstruct//边的信息
{inthead,tail;//起点、终点
floatlowcost//权值
}edge;
edgeEdge[arcnum];//边集
intVexset[MVnum];//并查集
整形数组Vexset[MVnum]：
标识各个顶点所属的连通分量。
初始时Vexset[i]=i，表示各顶点自成一个连通分量。
算法思想：
①将数组Edge中的元素按权值从小到大排序。
②依次从排序好的数组Edge中选出一条边（v1,v2），在Vexset中分别查找v1和v2所在的连通分量vs1和vs2。
·如果vs1和vs2不等，表明所选的两个顶点分属不同的连通分量，输出此边，并合并vs1和vs2两个连通分量。
·如果vs1和vs2相等，表明所选的两个顶点属于同一个连通分量，舍去此边，选择下一条权值最小的边。
③重复②，直至Edge中所有的边都扫描判断完，并且所有顶点都在同一个连通分量上。
算法实现：
T（n）=O（eloge）
//Kruskal算法求最小生成树
//无向网络G以邻接矩阵存储，构造G的最小生成树T，输出T的各个条边
voidMiniSpanTree_Kruskal（AMGGraphG）
{
Sort（Edge）;//将数组Edge中的元素按权值从小到大排序
for（i=0;iVexset[i]=i;//表示各顶点自成一个连通分量
for（i=0;i{v1=Locate（G,Edge[i].Head）;//v1为边的始点Head的下标
v2=Locate（G,Edge[i].Tail）;//v2为边的终点Tail的下标
vs1=Vexset[v1];//获取边Edge[i]的始点所在的连通分量
vs2=Vexset[v2];//获取边Edge[i]的终点所在的连通分量
if（vs1!
=vs2）
{cout<//输出此边
for（i=0;iif（Vexset[i]）==vs2）Vexset[i]）=vs1;
//合并vs1和vs2两个分量，即将两个集合
//统一编号，将集合编号vs2的都改为vs1
}
}
}
其它方法：
破圈法，Solin算法，Dijkstra算法。
7.5最短路径
这里的路径长度不是路径上边的数目，而是路径上权值的总和。
习惯称开始点——源点，最后一个顶点——终点。
1.单源最短路径
对于给定的有向网络G=（V,E）及单个源点V，求从V到其余各顶点的路径。
例图：
总结：
①最短路径不一定是边数最小。
②若按长度递增的顺序生成V到其它顶点的最短路径，则当前正在生成的路径上除终点外，其余顶点的最短路径已生成。
迪杰斯特拉算法（Dijkstra）：
基本思想：
设置并逐步扩充一个集合S，存放最短路径的顶点，则尚未确定的顶点集是V-S。
①置S为仅有源点的集合
②while（S中顶点数{在V-S中选最短路径长度的K扩充到S中；
}
基本问题：
如何在蓝集中选择蓝点k来扩充红点集？
为此，需定义一个数组D[n]来存放各顶点的距离值，显然每个红点的D[n]就是该点的最短路径长度，而蓝点不一定。
可以证明：
若当前蓝点集中具有最小距离值的蓝点是k,则其D[k-1]是K的最短路径长度，并且k是最短的顶点。
算法求精：
①S={V};
②置初始蓝点集中各蓝点的距离值
③while（S中的红点数{在蓝集中选择距离最小的k;
S=S+{k};
调整剩余蓝点的距离值；
}
如何调整：
调整D[n]的值：
对蓝点集扫描检查，若某蓝点j的原距离值D[j-1]大于新路径的长度D[k-1]+边上的权，则将D[j-1]修改为此长度值。
例图：
算法描述：
D[n]-----各顶点的距离值
P[n]-----路径向量P[i-1]源点到i最短路径上的前趋
S[n]-----红点集即进入S集的顶点。
floatD[n];//顶点的距离值
intP[n],S[n];//路径、红点集
voidDIJKSTRA（floatC[][n],intv）
{inti,j,k,v1,pre;
intnin,max=6000,inf=8000;
v1=v-1;
for（i=0;i{D[i]=C[v1][i];
if（D[i]!
=max）P[i]=v;
elseP[i]=0;
}
for（i=0;iS[i]=0;
S[v1]=1;
D[v1]=0
for（i=0;i{min=inf;
for（j=0;jif（（!
S[j]）&&（D[j]{min=D[j];
k=j;
}
S[k]=1;//将k+1加入红点集
for（j=0;jif（（!
S[j]）&&（D[j]）>D[k]+C[k][j]））
{D[j]=D[k]+C[k][j];
P[j]=k+1;
}
}
for（i=0;i{print（%f\n%d,D[i],i+1）;
pre=P[i];
while（pre!
=0）
{print（%d,pre）;
pre=P[pre-1];
}
}
}
算法优化：
一旦当蓝点集中所有蓝点的距离值均为max，则表示这些蓝点的最短路径均不存在，因此无需再将它们扩充到红点集，这样，可在把K加入红点集之前判断D[k-1]或min是否等于max,若是，推出扩充红点集的循环，打印结果。
算法分析：
T（n）=O（n2）S（n）=O（n）
2.所有顶点之间的最短路径
我们可以依次把有向网络的每个顶点作为源点，重复执行D算法n次，即可求得，其T（n）=O（n3）
费洛伊德算法：
仍采用邻接矩阵C表示有向网络
当不存在时C[i-1][j-1]=max
当i==j时C[i-1][j-1]=0
T（n）=O（n3）
直观分析：
若有，则长度为C[i-1][j-1]，但并不一定最短，因为可能存在一条从i到j，但中间包含其它顶点的路径，因此我们要考察i到j是否有以顶点1,2,……,n为中间点的更短路径。
算法关键：
要保留每一步所求得的，所有顶点之间的当前最短路径，设一个nxn的方阵序列A0,A1,…,An来保存当前求得的最短路径，特别A0=C,An即最短路径长度。
基本思想：
从A0开始，递推生成序列A1,A2,…,An
递推公式：
A0[i][j]=C[i][j]
Ak+1[i][j]=min{Ak[i][j],Ak[i][k]+Ak[k][j]}
具体算法：
仅用A来保存当前最短路径长度，还须设置路径矩阵path[n][n]在k+1次送代中path[i][j]是i到j序号不大于k+1的最短路径上顶点i的后继。
intpath[n][n];
voidFLOYD（floatA[][n],floatC[][n]）//迭代矩阵、有向网络
{inti,j,k,next;
intmax=∞;
for（i=0;ifor（j=0;j{if（C[i][j]!
=max）
path[i][j]=j+1;
elsepath[i][j]=0;
A[i][j]=C[i][j];
}
for（k=0;kfor（i
升级会员 