数据结构第七章课后习题答案

数据结构

7_1

对于图题7.1（P235）的无向图，给出： （1） 表示该图的邻接矩阵。 （2） 表示该图的邻接表。 （3） 图中每个顶点的度。 解：

（1） 邻接矩阵： 0111000 1001100 1001010 1110111 0101001 0011001 0001110 （2） 邻接表：

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，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开始进行深度优先搜索。

1

数据结构

这个过程进行到所有顶点都被访问过，或从任何一个已访问过的顶点出发，再也无法到达未曾访问过的顶点，则搜索过程就结束。 另一方面，先建立一个相应的具有n个顶点,m条边的无向图的邻接表。初始化visit数组，使其各个元素置为0，表示图中每个顶点都没被访问过。 下面给出程序：

#include #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;i

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[])

2

数据结构

{L_NODE *t; visit[u]=1;

printf(\ t=head[u]; while(t!=NULL)

{if(visit[t->ver]==0) dfs(t->ver,head,visit); t=t->link;} }

测试报告： void main()

{L_NODE *head[MAXN]; int visit[MAXN],n,m,u; E_NODE e[12];

e[0].ver1=1;e[0].ver2=3; e[1].ver1=1;e[1].ver2=4; e[2].ver1=1;e[2].ver2=2; e[3].ver1=2;e[3].ver2=4; e[4].ver1=2;e[4].ver2=5; e[5].ver1=3;e[5].ver2=6; e[6].ver1=3;e[6].ver2=4; e[7].ver1=4;e[7].ver2=6; e[8].ver1=4;e[8].ver2=7; e[9].ver1=4;e[9].ver2=5; e[10].ver1=5;e[10].ver2=7; e[11].ver1=6;e[11].ver2=7; creat_adj_list(head,7,e,12); init(visit,7); dfs(head,visit,1); printf(\}

输出结果：1 3 6 4 2 5 7

（1） BFS法：

存储结构：

本题采用邻接表作为图的存储结构，邻接表中的各个链表的结点形式由类型L_NODE规定，而各个链表的头指针存放在数组head中。

数组e中的元素e[0],e[1],…..,e[m-1]给出图中的m条边，e中结点形式由类型E_NODE规定。visit[i]数组用来表示顶点i是否被访问过。遍历前置visit各元素为0，若顶点i被访问过,则置visit[i]为1.另外，使用一个队列QTYPE来存储已经访问过的顶点。

算发分析：

首先访问出发顶点v，然后访问与顶点v邻接的全部顶点w1,w2,…,wi,再依次访问与

3

数据结构

w1,w2,…,wi,邻接的全部顶点（已访问的顶点除外），再从这些已访问的顶点出发，依次与它们邻接的全部顶点（已访问的顶点除外）。依次类推，直到图中或v所在的连通分量的所有顶点都被访问到为止，广度优先搜索结束。

下面给出程序: #include #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;i

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 bfs(int u,L_NODE *head[],int visit[])

4