 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
7 数据结构作业答案第7章作业答案
下载积分：100
内容提示：7 数据结构作业答案第7章作业答案
文档格式：PDF|
浏览次数：851|
上传日期： 05:49:37|
文档星级：
全文阅读已结束，如果下载本文需要使用
 100 积分
下载此文档
该用户还上传了这些文档
7 数据结构作业答案第7章作业答案
官方公共微信8.5&求无向图的深度优先生成树和广度优先生成树
#include&stdio.h&
#include&malloc.h&
#define MAXV 100
int visited[MAXV];
//以下定义邻接矩阵类型
typedef struct
&&&&&&&&&&
//顶点编号
//顶点其余的信息 &
typedef struct
edges[MAXV][MAXV];&& //邻接矩阵
n,e;&&&&&&&&&&&&&&&&
//顶点数，弧数
&VertexType
vexs[MAXV];&& //存放顶点信息
//一下定义邻接表类型
typedef struct
ANode&&&&&
//弧的节点结构类型
//该弧的终点位置
&struct ANode *
&&&&&&&&&&&
//弧的相关信息
typedef struct
Vnode&&&&&&
//邻接表头结点类型
&&&&&&&&&&&
//顶点信息
*&& //指向第一条弧
typedef VNode& AdjList[MAXV];
typedef struct
void MatToList(MGraph g,ALGraph
*&G)&&&&&&&
//将邻接矩阵 g 转换为邻接表 G
&int i,j,n=g.n;
&ArcNode *p;
&G=(ALGraph *)malloc(sizeof(ALGraph));
&for(i=0;i&n;i++)
G-&adjlist[i].firstarc=NULL;
for(i=0;i&n;i++)
for(j=n-1;j&=0;j--)
if(g.edges[i][j])
&p=(ArcNode *)malloc(sizeof(ArcNode));
&p-&adjvex=j;
&p-&info=g.edges[i][j];
&p-&nextarc=G-&adjlist[i].
&G-&adjlist[i].firstarc=p;
void DispAdj(ALGraph
//输出邻接表
&ArcNode *p;
&for(i=0;i&G-&n;i++)
&&p=G-&adjlist[i].
printf("%3d:",i);
&&while(p)
&&&printf("%3d",p-&adjvex);
&&printf("\n");
//深度优先生成树
void DFS(ALGraph *G,int v)
&ArcNode *p;
&visited[v]=1;
&p=G-&adjlist[v].
&&if(visited[p-&adjvex]==0)
&&&printf("&%d,%d&
",v,p-&adjvex);
&&&DFS(G,p-&adjvex);
//广度优先生成树
void BFS(ALGraph *G,int v)
&ArcNode *p;
&int queue[MAXV],front=0,rear=0;
&for(i=0;i&G-&n;i++)
visited[i]=0;
visited[v]=1;
rear=(rear+1)%MAXV;
queue[rear]=v;
while(front!=rear)
&front=(front+1)%MAXV;
&w=queue[front];
&p=G-&adjlist[w].
&if(visited[p-&adjvex]==0)
&&printf("&%d,%d&
",w,p-&adjvex);
&&visited[p-&adjvex]=1;
&&rear=(rear+1)%MAXV;
&&queue[rear]=p-&&&&&
printf("\n");
int main()
&ALGraph *G;
&int A[MAXV][11];
&g.n=11;g.e=13;
&for(i=0;i&g.n;i++)
for(j=0;j&g.n;j++)
A[i][j]=0;
A[0][3]=1;A[0][2]=1;A[0][1]=1;A[1][5]=1;A[1][4]=1;
A[2][6]=1;A[2][5]=1;A[2][3]=1;A[3][7]=1;A[6][9]=1;
A[6][8]=1;A[6][7]=1;A[7][10]=1;
for(i=0;i&g.n;i++)
for(j=0;j&g.n;j++)
A[j][i]=A[i][j];
for(i=0;i&g.n;i++)
for(j=0;j&g.n;j++)
g.edges[i][j]=A[i][j];
&&& G=(ALGraph
*)malloc(sizeof(ALGraph));
MatToList(g,G);
printf("\n");
printf("图G的邻接表：\n");
DispAdj(G);
printf("\n");
for(i=0;i&g.n;i++)
visited[i]=0;
printf("深度优先生成树：");
&DFS(G,3);printf("\n");
&for(i=0;i&g.n;i++)
visited[i]=0;
&printf("广度优先生成树：");
&BFS(G,3);printf("\n");
&return 0;
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。广度优先搜索&深度优先搜索（Breadth First Search & Depth First Search）
BFS优缺点：
同一层的所有节点都会加入队列，所以耗用大量空间；
仅能非递归实现；
相比DFS较快，空间换时间；
适合广度大的图；
空间复杂度：邻接矩阵O（N^2）；邻接表O（N+E）；
时间复杂度：O（V+E）；
DFS优缺点：
无论是系统栈还是用户栈保存的节点数都只是树的深度，所以空间耗用小；
有递归和非递归实现；
由于有大量栈操作（特别是递归实现时候的系统调用），执行速度较BFS慢；
适合深度大的图；
空间复杂度：邻接矩阵O（N^2）；邻接表O（N+E）；
时间复杂度：O（V+E）；
1 //BFS只能非递归实现，将queue替换成stack之后就是DFS
2 procedure BFS(G,v):
create a queue Q
enqueue v onto Q
while Q is not empty:
t & Q.dequeue()
if t is what we are looking for:
for all edges e in G.incidentEdges(t) do //遍历所有与t直接相连的边e
o & G.opposite(t,e) //通过边e与t相连的顶点o
if o is not marked:
enqueue o onto Q
16 //DFS递归实现
17 procedure DFS(G,v):
label v as explored
for all edges e in G.incidentEdges(v) do
if edge e is unexplored then
w & G.opposite(v,e)
if vertex w is unexplored then
label e as a discovery edge
recursively call DFS(G,w) //递归调用没有访问的顶点w
label e as a back edge
最小生成树算法（Minimum Spanning Tree Algorithm, eg: Kruskal, Prim）
Kruskal Algorithm
Kruskal属于贪心算法BFS策略，适用于稀疏图，使用并查集实现可具有较好性能，时间复杂度为O(ElogV)，空间复杂度为O(V)；
首先对于一个含有N个顶点的连通图，Kruskal首先构造一个含有N个独立顶点的图，也就是N棵只有一个顶点的树；然后从带有权值的边集合E中选择当前 权值最小的边e，如果e连接的顶点属于不同的树i和j，则使用e连接数i和j，并将e从边集合E中删除；然后从边集合E中选择下一个具有最小权值的边e， 直到左右的边都选择完毕；最终所有的N棵子树将合并成一棵树；
Prim Algorithm
时间复杂度：使用邻接矩阵实现为O(V^2)；使用二叉堆和邻接表实现为O(ElogV)；使用斐波那契堆实现为O(E+VlogV)；Prim与 Kruskal的不同点在于，Prim从头到尾都只维护一棵树，通过从树的最远顶点相连的还未在树中的顶点中选择边权值最小的顶点进行扩展。
1 MST-PRIM(G,w,r)
Q&V[G] //将G的所有节点记录到Q
for 每个包含于Q的u
do key[u]&& //初始化每个节点的key，表示到根节点r的最短距离
key[r]&0 //处理根节点
while Q&空集
do u&EXTRACT-MIN(Q) //根据节点的key值选取一个最小的节点
for 每个包含于Adj[u]的节点v
do if v包含于Q and w(u,v)&key[v]
then p[v]&u
key[v]&w(u,v) //使用节点间的距离赋值节点v的最短距离
阅读(...) 评论()}