第七章 图Word格式.docx
《第七章 图Word格式.docx》由会员分享，可在线阅读，更多相关《第七章 图Word格式.docx（38页珍藏版）》请在冰点文库上搜索。
6F
邻接表
4
2
（出边表）
5
（入边表）
datafinfout
（3）邻接多重表（十字链表）
ijilinkjlink
01（A,B）
03（A,D）
12（B,C）
14（B,E）
25（C,F）
31（D,B）
34（D,E）
54（F,E）
8-4用邻接矩阵表示图时，若图中有1000个顶点，1000条边，则形成的邻接矩阵有多少矩阵元素？
有多少非零元素？
是否稀疏矩阵？
一个图中有1000个顶点，其邻接矩阵中的矩阵元素有10002=1000000个。
它有1000个非零元素（对于有向图）或2000个非零元素（对于无向图），因此是稀疏矩阵。
8-5用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？
与边的条数是否相关？
用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。
矩阵中非零元素的个数与边的条数有关。
8-6有n个顶点的无向连通图至少有多少条边？
有n个顶点的有向强连通图至少有多少条边？
试举例说明。
n个顶点的无向连通图至少有n-1条边，n个顶点的有向强连通图至少有n条边。
例如：
特例情况是当n=1时，此时至少有0条边。
8-7对于有n个顶点的无向图，采用邻接矩阵表示，如何判断以下问题：
图中有多少条边？
任意两个顶点i和j之间是否有边相连？
任意一个顶点的度是多少？
用邻接矩阵表示无向图时，因为是对称矩阵，对矩阵的上三角部分或下三角部分检测一遍，统计其中的非零元素个数，就是图中的边数。
如果邻接矩阵中A[i][j]不为零，说明顶点i与顶点j之间有边相连。
此外统计矩阵第i行或第i列的非零元素个数，就可得到顶点i的度数。
①
8-8对于如右图所示的有向图，试写出：
③
②
（1）从顶点①出发进行深度优先搜索所得到的深度优先生成树；
（2）从顶点②出发进行广度优先搜索所得到的广度优先生成树；
⑤
④
（1）以顶点①为根的深度优先生成树（不唯一）：
②③④⑤⑥
或
（2）以顶点②为根的广度优先生成树：
8-9试扩充深度优先搜索算法，在遍历图的过程中建立生成森林的左子女-右兄弟链表。
算法的首部为voidGraph:
:
DFS（constintv,intvisited[],TreeNode<
int>
*t）其中，指针t指向生成森林上具有图顶点v信息的根结点。
（提示：
在继续按深度方向从根v的某一未访问过的邻接顶点w向下遍历之前，建立子女结点。
但需要判断是作为根的第一个子女还是作为其子女的右兄弟链入生成树。
）
为建立生成森林，需要先给出建立生成树的算法，然后再在遍历图的过程中，通过一次次地调用这个算法，以建立生成森林。
template<
Type>
voidGraph<
:
DFS_Tree（constintv,intvisited[],TreeNode<
*t）{
//从图的顶点v出发,深度优先遍历图,建立以t（已在上层算法中建立）为根的生成树。
Visited[v]=1;
intfirst=1;
TreeNode<
*p,*q;
intw=GetFirstNeighbor（v）;
//取第一个邻接顶点
while（w!
=-1）{//若邻接顶点存在
if（vosited[w]==0）{//且该邻接结点未访问过
p=newTreeNode<
（GetValue（w））;
//建立新的生成树结点
if（first==1）//若根*t还未链入任一子女
{t->
setFirstChild（p）;
first=0;
}//新结点*p成为根*t的第一个子女
elseq->
setNextSibling（p）;
//否则新结点*p成为*q的下一个兄弟
q=p;
//指针q总指示兄弟链最后一个结点
DFS_Tree（w,visited,q）;
//从*q向下建立子树
}
w=GetNextNeighbor（v,w）;
//取顶点v排在邻接顶点w的下一个邻接顶点
}
下一个算法用于建立以左子女-右兄弟链表为存储表示的生成森林。
template<
DFS_Forest（Tree<
&
T）{
//从图的顶点v出发,深度优先遍历图,建立以左子女-右兄弟链表表示的生成森林T。
T.root=NULL;
intn=NumberOfVertices（）;
//顶点个数
TreeNode<
int*visited=newint[n];
//建立访问标记数组
for（intv=0;
v<
n;
v++）visited[v]=0;
for（v=0;
v++）//逐个顶点检测
if（visited[v]==0）{//若尚未访问过
（GetValue（v））;
//建立新结点*p
if（T.root==NULL）T.root=p;
//原来是空的生成森林,新结点成为根
setNextSibling（p）;
DFS_Tree（v,visited,p）;
//建立以*p为根的生成树
}
}
8-10用邻接表表示图时，顶点个数设为n，边的条数设为e，在邻接表上执行有关图的遍历操作时，时间代价是O（n*e）？
还是O（n+e）？
或者是O（max（n,e））？
在邻接表上执行图的遍历操作时，需要对邻接表中所有的边链表中的结点访问一次，还需要对所有的顶点访问一次，所以时间代价是O（n+e）。
⑧
⑦
⑨
8-11右图是一个连通图，请画出
⑥
⑩
（1）以顶点①为根的深度优先生成树；
（2）如果有关节点，请找出所有的关节点。
（3）
如果想把该连通图变成重连通图，至少在图中加几条边？
如何加？
（1）以顶点①为根的深度优先生成树：
（2）关节点为①,②,③,⑦,⑧
（3）至少加四条边（1,10）,（3,4）,（4,5）,（5,6）。
从③的子孙结点⑩到③的祖先结点①引一条边，从②的子孙结点④到根①的另一分支③引一条边，并将⑦的子孙结点⑤、⑥与结点④连结起来，可使其变为重连通图。
8-12试证明在一个有n个顶点的完全图中，生成树的数目至少有2n-1-1。
【证明】略
7
11
10
8
6
9
8-13编写一个完整的程序，首先定义堆和并查集的结构类型和相关操作，再定义Kruskal求连通网络的最小生成树算法的实现。
并以右图为例，写出求解过程中堆、并查集和最小生成树的变化。
求解过程的第一步是对所有的边，按其权值大小建堆：
345
127
2310
249
1311
加（1,2）,（1,3）,（2,3）
加（3,4）
加（2,4）
357
368
加（3,5）
加（3,6）
566
加（5,6）
求解过程中并查集与堆的变化：
选（5,6,6）
选（3,4,5）
选（3,5,7）
选（1,2,7）
选（2,4,9）,结束
选（3,6,8）,在同一连通分量上,不加
最后得到的生成树如下
0123456
31-6335
并查集的存储表示
完整的程序如下:
#include<
iostream.h>
template<
classType>
classMinHeap{
public:
enum{MaxHeapSize=50};
MinHeap（intMaxsize=MaxHeapSize）;
MinHeap（TypeArray[],intn）;
voidInsert（constType&
ele）;
voidRemoveMin（Type&
Min）;
voidOutput（）;
private:
voidFilterDown（intstart,intend）;
voidFilterUp（intend）;
Type*pHeap;
intHMaxSize;
intCurrentSize;
};
classUFSets{
enum{MaxUnionSize=50};
UFSets（intMaxSize=MaxUnionSize）;
~UFSets（）{delete[]m_pParent;
voidUnion（intRoot1,intRoot2）;
intFind（intx）;
private:
intm_iSize;
int*m_pParent;
classGraph{
enum{MaxVerticesNum=50};
Graph（intVertices=0）{CurrentVertices=Vertices;
InitGraph（）;
voidInitGraph（）;
voidKruskal（）;
intGetVerticesNum（）{returnCurrentVertices;
intEdge[MaxVerticesNum][MaxVerticesNum];
intCurrentVertices;
classGraphEdge{
inthead,tail;
intcost;
intoperator<
=（GraphEdge&
ed）;
GraphEdge:
operator<
ed）{
returnthis->
cost<
=ed.cost;
}
UFSets:
UFSets（intMaxSize）{
m_iSize=MaxSize;
m_pParent=newint[m_iSize];
for（inti=0;
i<
m_iSize;
i++）m_pParent[i]=-1;
voidUFSets:
Union（intRoot1,intRoot2）{
m_pParent[Root2]=Root1;
intUFSets:
Find（intx）{
while（m_pParent[x]>
=0）x=m_pParent[x];
returnx;
MinHeap<
MinHeap（intMaxsize）{
HMaxSize=Maxsize;
pHeap=newType[HMaxSize];
CurrentSize=-1;
MinHeap（TypeArray[],intn）{
HMaxSize=（n<
MaxHeapSize）?
MaxHeapSize:
i++）pHeap[i]=Array[i];
CurrentSize=n-1;
intiPos=（CurrentSize-1）/2;
while（iPos>
=0）{
FilterDown（iPos,CurrentSize）;
iPos--;
voidMinHeap<
FilterDown（intstart,intend）{
inti=start,j=2*start+1;
TypeTemp=pHeap[i];
while（j<
=end）{
if（j<
end&
&
pHeap[j+1]<
=pHeap[j]）j++;
if（Temp<
=pHeap[j]）break;
pHeap[i]=pHeap[j];
i=j;
j=2*j+1;
pHeap[i]=Temp;
FilterUp（intend）{
inti=end,j=（end-1）/2;
while（i>
0）{
if（pHeap[j]<
=Temp）break;
j=（j-1）/2;
pHeap[i]=Temp;
Insert（constType&
ele）{
CurrentSize++;
if（CurrentSize==HMaxSize）return;
pHeap[CurrentSize]=ele;
FilterUp（CurrentSize）;
RemoveMin（Type&
Min）{
if（CurrentSize<
0）return;
Min=pHeap[0];
pHeap[0]=pHeap[CurrentSize--];
FilterDown（0,CurrentSize）;
Output（）{
=CurrentSize;
i++）cout<
<
pHeap[i]<
"
;
cout<
endl;
voidGraph:
InitGraph（）{
Edge[0][0]=-1;
Edge[0][1]=28;
Edge[0][2]=-1;
Edge[0][3]=-1;
Edge[0][4]=-1;
Edge[0][5]=10;
Edge[0][6]=-1;
Edge[1][1]=-1;
Edge[1][2]=16;
Edge[1][3]=-1;
Edge[1][4]=-1;
Edge[1][5]=-1;
Edge[1][6]=14;
Edge[2][2]=-1;
Edge[2][3]=12;
Edge[2][4]=-1;
Edge[2][5]=-1;
Edge[2][6]=-1;
Edge[3][3]=-1;
Edge[3][4]=22;
Edge[3][5]=-1;
Edge[3][6]=18;
Edge[4][4]=-1;
Edge[4][5]=25;
Edge[4][6]=24;
Edge[5][5]=-1;
Edge[5][6]=-1;
Edge[6][6]=-1;
for（inti=1;
6;
i++）
for（intj=0;
j<
i;
j++）Edge[i][j]=Edge[j][i];
Kruskal（）{
GraphEdgee;
intVerticesNum=GetVerticesNum（）;
inti,j,count;
GraphEdge>
heap（VerticesNum*VerticesNum）;
UFSetsset（VerticesNum）;
for（i=0;
VerticesNum;
for（j=i+1;
j++）
if（Edge[i][j]>
0）{
e.head=i;
e.tail=j;
e.cost=Edge[i][j];
heap.Insert（e）;
count=1;
while（count<
VerticesNum）{
heap.RemoveMin（e）;
i=set.Find（e.head）;
j=set.Find（e.tail）;
if（i!
=j）{
set.Union（i,j）;
count++;
cout<
（"
<
e.head<
"
e.tail<
e.cost<
）"
8-14利用Dijkstra算法的思想，设计一个求最小生成树的算法。
计算连通网络的最小生成树的Dijkstra算法可描述如下：
将连通网络中所有的边以方便的次序逐步加入到初始为空的生成树的边集合T中。
每次选择并加入一条边时，需要判断它是否会与先前加入T的边构成回路。
如果构成了回路，则从这个回路中将权值最大的边退选。
①②③④⑤⑥
下面以邻接矩阵作为连通网络的存储表示，并以并查集作为判断是否出现回路的工具，分析算法的执行过程。
16
②③④⑤⑥
19
21
26
14
18
并查集,表明4个结点在同一连通分量上
升级会员 