DFS,BFS(拓扑排序)的简单应用,

DFS:

1:用来确定在互联网中从一个结点到另一个结点(一个网络到其他网络的网关)的最佳路径。一种建模方法是采用无向图,其中顶点表示网络结点,边代表结点之间的联接。使用这种模型,可以采用广度优先搜索来帮助确定结点间的最小跳数

2:棋盘问题,要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列。

3:八皇后求解。等问题

搜索全部的解,进行试探搜索,也是回溯算法:把所有可能进行尝试,找出解。

BFS:

 

1:最短路径求解。

2:有时候,我们必须根据各种事物间的依赖关系来确定一种可接受的执行顺序。比如,在大学里必须满足一些先决条件才能选的课程,或者一个复杂的项目,其中某个特定的阶段必须在其他阶段开始之前完成。要为这一类问题建模,可以采用优先级图,其采用的是有向图的思路在优先级图中,顶点代表任务,而边代表任务之间的依赖关系以必须先完成的任务为起点,以依赖于此任务的其他任务为终点,画一条边即可。

 

3:拓扑排序:

 拓扑排序可能是唯一的又有可能是不唯一的。(存在环)。。。。比如

DFS,BFS(拓扑排序)的简单应用,