《数据结构》以邻接表位存储，写出连通图的深度优先搜索法。

Question

如题所述

Answer 1

深度优先搜索法遍历图

template <class T1, class T2>
void Link_GP<T1,T2> :: bfs_GP()
{ int *mark, k;
sq_Queue<int> q(nn); //建立循环队列
node<T1> *p;
mark=new int[nn]; //申请标志数组
for (k=0; k<nn; k++) mark[k]=0;
for (k=0; k<nn; k++) //对每个图结点横向优先搜索
{ if ( mark[k] == 0) //当前结点未查访过
{ mark[k] = 1; //置已查访标志
cout <<gp->data <<" "; //输出当前结点值
q.ins_sq_Queue(k); //当前结点编号入队
while (q.flag_sq_Queue()) //队列不空
{ k=q.del_sq_Queue();
//从队列中退出一个结点作为当前结点
p = (gp+k)->link; //置编号k的结点单链表指针
while (p!=NULL) //还有后件
{ k = p->num-1;
if (mark[k]==0) //该结点未查访过
{ cout <<(gp+k)->data <<" "; //输出该结点值
mark[k]=1; //置已访问标志
q.ins_sq_Queue(k); //该结点编号入队
}
p=p->next; //下一个后件
}
}
}
}
cout <<endl; delete mark;
}

Answer 2

左孩子 全部小于其根节点 右孩子全部大于根结点
所以 4
1 7
1 3 0 8
0 0 2 0 0 0 0 0
0代表无 然后中序遍历之：1 1 2 3 4 7 8 符合其定义 OVER