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

数据结构

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(\ visit[v]=1; }

for(p=head[v];p;p=p->link){ if(visit[p->data]==0) s[++top]=p->data; } }

printf(\}

7_12

9

数据结构

题目：

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

1 2

3 4 5

6 7

分析：

根据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生成树：

1 3 6 1 3 6 4 4 2 5 7 2 5 7 10