你的位置:首页 > 操作系统

[操作系统]算法—12.广度优先搜索


1.具体算法

/** * Created by huazhou on 2015/12/6. */public class TestSearch {  public static void main(String[] args){    Graph G = new Graph(new In(args[0]));    int s = Integer.parseInt(args[1]);//    DepthFirstSearch search = new DepthFirstSearch(G, s);//    Paths search = new Paths(G, s);//    DepthFirstSearch search = new DepthFirstSearch(G,s);    BreadthFirstPaths search = new BreadthFirstPaths(G,s);    findAllPaths(search, G, s);  }  private static void findAllPaths(BreadthFirstPaths search, Graph G, int s){    for(int v = 0; v < G.V(); v++){      StdOut.print(s + " to " + v + ": ");      if(search.hasPathTo(v)){        for (int x : search.pathTo(v)){          if(x == s){            StdOut.print(x);          }          else{            StdOut.print("-" + x);          }        }      }      StdOut.println();    }  }}

/** * 算法4.2 使用广度优先搜索查找图中的路径 * Created by huazhou on 2015/12/9. */public class BreadthFirstPaths {  private boolean[] marked;  //到达该顶点的最短路径已知吗?  private int[] edgeTo;  //到达该顶点的已知路径上的最后一个顶点  private int s; //起点  public BreadthFirstPaths(Graph G, int s){    marked = new boolean[G.V()];    edgeTo = new int[G.V()];    this.s = s;    bfs(G, s);  }  private void bfs(Graph G, int s){    Queue<Integer> queue = new Queue<Integer>();    marked[s] = true;  //标记起点    queue.enqueue(s);  //将它加入队列    while(!queue.isEmpty()){      int v = queue.dequeue();  //从队列中删去下一顶点      for (int w : G.adj(v)){        //对于每个未被标记的相邻顶点        if(!marked[w]){          edgeTo[w] = v; //保持最短路径的最后一条边          marked[w] = true;  //标记它,因为最短路径已知          queue.enqueue(w);  //并将它添加到队列中        }      }    }  }  public boolean hasPathTo(int v){    return marked[v];  }  public Iterable<Integer> pathTo(int v){    if(!hasPathTo(v)){      return null;    }    Stack<Integer> path = new Stack<Integer>();    for (int x = v; x != s; x = edgeTo[x]){      path.push(x);    }    path.push(s);    return path;  }}

2.执行过程

3.算法分析

命题:对于从s可达的任意顶点v,广度优先搜索都能找到一条从s到v的最短路径(没有其他从s到v的路径所含的边比这条路径更少)

命题:广度优先搜索所需的时间在最坏情况下和V+E成正比。

 

源码下载