数据结构第七章后习题答案.doc
文本预览下载声明
7_1
对于图题7.1（P235）的无向图，给出：
表示该图的邻接矩阵。
表示该图的邻接表。
图中每个顶点的度。
解：
邻接矩阵：
0111000
1001100
1001010
1110111
0101001
0011001
0001110
邻接表：
1：2----3----4----NULL;
2: 1----4----5----NULL;
3: 1----4----6----NULL;
4: 1----2----3----5----6----7----NULL;
5: 2----4----7----NULL;
6: 3----4----7----NULL;
7: 4----5----6----NULL;
图中每个顶点的度分别为：3，3，3，6，3，3，3。
7_2
对于图题7.1的无向图，给出：
（1）从顶点1出发，按深度优先搜索法遍历图时所得到的顶点序
（2）从顶点1出发，按广度优先法搜索法遍历图时所得到的顶点序列。
（1）DFS法：
存储结构：
本题采用邻接表作为图的存储结构，邻接表中的各个链表的结点形式由类型L_NODE规定，而各个链表的头指针存放在数组head中。
数组e中的元素e[0],e[1],…..,e[m-1]给出图中的m条边，e中结点形式由类型E_NODE规定。visit[i]数组用来表示顶点i是否被访问过。遍历前置visit各元素为0，若顶点i被访问过,则置visit[i]为1.
算法分析：
首先访问出发顶点v.接着，选择一个与v相邻接且未被访问过的的顶点w访问之，再从w开始进行深度优先搜索。每当到达一个其所有相邻接的顶点都被访问过的顶点，就从最后访问的顶点开始，依次退回到尚有邻接顶点未曾访问过的顶点u,并从u开始进行深度优先搜索。这个过程进行到所有顶点都被访问过，或从任何一个已访问过的顶点出发，再也无法到达未曾访问过的顶点，则搜索过程就结束。
另一方面，先建立一个相应的具有n个顶点,m条边的无向图的邻接表。初始化visit数组，使其各个元素置为0，表示图中每个顶点都没被访问过。
下面给出程序：
#includestdio.h
#define MAXN 50
#define MAXM 100
typedef struct l_node{int ver;
struct l_node *link;
}L_NODE;
typedef struct e_node{int ver1;
int ver2;
}E_NODE;
void creat_adj_list(L_NODE *head[],int n,E_NODE e[],int m)
{int i,u,v;
L_NODE *p,*q;
for(i=1;i=n;i++)
head[i]=NULL;
for(i=0;im;i++)
{u=e[i].ver1;
v=e[i].ver2;
p=(L_NODE*)malloc(sizeof(L_NODE));
p-ver=v;
p-link=NULL;
if(head[u]==NULL) head[u]=p;
else {q=head[u];
while(q-link!=NULL) q=q-link;
q-link=p;}
p=(L_NODE*)malloc(sizeof(L_NODE));
p-ver=u;
p-link=NULL;
if(head[v]==NULL) head[v]=p;
else {q=head[v];
while(q-link!=NULL) q=q-link;
q-link=p;}
}
}
void init(int visit[],int n)
{int i;
for(i=1;i=n;i++)
visit[i]=0;
}
void dfs(int u,L_NODE *head[],int visit[])
{L_NODE *t;
visit[u]=1;
printf(%4d,u);
t=head[u];
while(t!=NULL)
{if(visit[t-ver]==0) dfs(t-ver,head,visit);
t=t-link;}
}
测试报告：
void
显示全部