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

对于图题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开始进行深度优先搜索。这个过程进行到所有顶点都被访问过，或从任何一个已访问过的顶点出发，再也无法到达未曾访问过的顶点，则搜索过程就结束。

   另一方面，先建立一个相应的具有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  {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 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("\\n");

}

输出结果：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,再依次访问与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  {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 bfs(int u,L_NODE *head[],int visit[])

{typedef struct queuetype{int qa;

                          int qe;

              int item[MAXN];

             }QTYPE;

int v,w;L_NODE *t;

QTYPE queue;

printf("%4d",u);

visit[u]=1;

queue.qa=0;

queue.qe=0;

queue.item[0]=u;

while(queue.qa<=queue.qe)

{v=queue.item[queue.qa++];

 t=head[v];

 while(t!=NULL)

{w=t->ver;

  if(visit[w]==0)

  {printf("%4d",w);

   visit[w]=1;

   queue.item[++queue.qe]=w;

  }

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);

bfs(1,head,visit);

printf("\\n");

}

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

7_3 

对于图题7.3的有向图，给出：

（1）表示该图的邻接矩阵。

（2）表示该图的邻接表。

（3）图中每个顶点的入度和出度。

  解：（1） 邻接矩阵如下：

                          0 1 0 1 0 0 0                          图题7.3

                          0 0 0 0 1 0 0

                          1 0 0 0 0 0 0

                          0 0 0 0 1 1 0

                          0 0 0 0 0 0 1

                          0 0 1 0 0 0 0

                          0 0 0 0 0 1 0

(2)邻接表如下：   

r1=1,c1=2

r2=1,c2=1

r3=1,c3=1

r4=1,c4=2

r5=2,c5=1

r6=2,c6=1

r7=1,c7=1

7_4

对于图题7.3的有向图，给出：

（1）从顶点1出发，按深度优先搜索法遍历图时的所得的顶点序列。

（2）从顶点1出发，按广度优先搜索法遍历图时的所得的定点序列。

解：（1）  1－2－5－7－6－3－4

（2）    1－2－4－5－6－7－3

7_5 

对于图题7.1的无向图，试问它是（1）连通图吗？（2）完全图吗？

12

3           4           5

67

（1）该图是连通图。判断无向图是否为连通图，即判断该图中是否每对顶点之间都有路径。

（2）该图不是完全图。判断无向图是否为完全图，即判断图中是否每对顶点之间都有边。

7_6

 对于图题 7.3的有向图，试问它是（1）弱连通图吗？（2）强连通图吗？

12

3            4           5

67

(1)该图是弱连通图。判断有向图是否为弱连通图，即需判断图中是否每对顶点v和w之间有一个由不同顶点组成的顶点序列（v0,v1,……vk），其中v0=v，vk=w，且（vi，vi+1）或（vi+1，vi）属于图的边集。

(2)该图是强连通图。判断有向图是否为强连通图，即需判断图中是否每对顶点之间有一条路径。

7_7

图题7-7是有向图，试问其中哪个图是

（1）弱连通的？

（2）强连通的？

    (a)                                          (b)

[解]（1）(b) 图是弱连通的。

   （2）( a) 图是强连通的。

7_8

具有N个顶点的连通无向图至少有几条边？

[解]具有N个顶点的连通无向图至少应有N—1条边。

7_9

具有N个顶点的强连通有向图至少有几条边？ 2N条边。

7_10

分别写出用深度和广度优先搜索法遍历具有六个顶点的完全无向图的顶点序列。（假设都以顶点1出发）。

深度优先：1，2，3，4，5，6

广度优先：1，2，3，4，5，6

7_11

题目：

改写以深度优先搜索法遍历给定的连通图的dfs程序，要求不用递归方法，而用一个栈来实现。

算法分析：

用栈保存由结点V出发可到达的结点，并作上标记，以使下次遇到时不会重复输出。当一路结点访问完后，向前回溯（利用出栈）并访问其他结点，直到所有结点均已遍历。

程序的流程：结点进栈结点出栈访问并标记结点相联结点进栈……。（相联结点进栈后，执行相同的步骤）当栈空时，遍历完成。

程序：

#define MAXN 50

typedef struct node{

    int data;

    struct node* link;

};

void dfs(NODE *head[],int ver,int v)

{

 int s[MAXN],visit[MAXN];

 int top,i;

 for(i=1;i<=ver;i++)    visit[i]=0;

 s[0]=v;

 top=0;

while(top>=0){

    v=s[top--];

    if(visit[v]==0){

        printf("%d\",v);

        visit[v]=1;

    }

for(p=head[v];p;p=p->link){

        if(visit[p->data]==0)

            s[++top]=p->data;

    }

 }

 printf("\\n");

}

7_12

题目：

在图题7.1中，从顶点1出发，分别画出其dfs生成树和bfs生成树。

分析：

根据dfs遍历和bfs遍历的顺序，记录所得到的点和边的集合，即可得到生成树和生成树。

dfs遍历：（1，2，4，3，6，7，5），边分别为：（1，2），（2，4），（4，3），（3，6），（6，7），（7，5）。

bfs遍历：（1，2，3，4，5，6，7），边分别为：（1，2），（1，3），（1，4），（2，5），（3，6），（4，7）。

解答：

dfs生成树：

bfs生成树：