数据结构中出图的二种遍历，写出算法与思想，谢谢

Question

如题所述

Answer 1

BFS，广度优先搜索
先遍历离起点近的，再到远的，直至全图。先遍历所有与起点距离为1的点，再到所有距离为2的点……
具体实现，需要一个队列进行辅助存储。
举个例，S为起点，S到A,B,C3个点相邻。A又与A1,A2相邻，B与B1,B2相邻，C没有与其他点相邻。对于遍历A发生的事情，就是“发现”了A1,A2。但是，这是不能立即遍历A1,A2，这与BFS宗旨违背，必须先遍历B,C。而又由于B,C肯定是比A1,A2先“发现”，这就体现了一种“先进先出”的性质，因而需要队列对为扩展的结点进行暂存
BFS()
{
queue q;
q.push(s);//一开始的s点
while(q非空)
{
从q中取一元素
将该元素“发现”，而又未被进过q的结点入队
}
}

DFS，深度优先搜索
先选定一条路径，对路径上的点进行遍历。然后，从路径的尽头开始，逐步回退，在每个分支再遍历其他路径及其上面的点。
具体实现，常写作递归，故可理解为通过栈辅助存储。
还是上面的距离，DFS出来的其中一种序列是S,A,A1,A2,B,B1,B2,C。路径S,A,A1为第一选取的路径，然后回退，逐步选取其他分支，在A选取了A2作为第二路径，以此类推。由于这样对每个点所做的操作就是“发现”，“遍历”与“回退”，操作种类相同，故常写作递归。。。
DFS(int target)
{
for(target的每个发现点)
{
DFS(该发现点)
}
//结束函数实际上就是回退的过程
}

Answer 2

这位同学，我感觉数据结构里就是树和图比较简单了，这都不会吗？？？？劝你夺取看看书！！！