BFS的应用求最短路径

墨蓝 2022-02-18 10:53 306阅读 0赞

因为在leetcode的卡片上学习队列，才发现，都是BFS应用的题目，队列只是个“辅助”，BFS才是“打野”。好吧，那就先解决BFS。什么是BFS？全称：Breadth First Search，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。（[https://zh.wikipedia.org/wiki/广度优先搜索）][https_zh.wikipedia.org_wiki]  
  
![在这里插入图片描述][2019041711295561.gif]  
明白了，说到BFS就要先建立图，进而在图的基础上讲BFS。  
  
1，图的设计与实现  
  
1）什么是图？  
![在这里插入图片描述][20190417113245335.png]  
概念就直接google吧，但需要了解和掌握这三个概念：图的基本常识（有向图，无向图，带权等），两种存储结构（二维数组，邻接表），连通图和生产树。

![在这里插入图片描述][20190417113602890.png]

图 1 邻接表存储有向图

![在这里插入图片描述][20190417113928455.png]

图 2 有向图对应的二维数组  2，图的编程实现（Java，邻接表存储）

// Java code to demonstrate Graph representation 
    // using ArrayList in Java 
    import java.util.*; 
      
    class Graph { 
        ArrayList<ArrayList<Integer> > adj; 
        int V; 
        Graph(int v) 
        { 
            V = v; 
            adj = new ArrayList<ArrayList<Integer> >(V); 
            for (int i = 0; i < V; i++) 
                adj.add(new ArrayList<Integer>()); 
        } 
      
        void addEdge(int u, int v) 
        { 
            adj.get(u).add(v); 
            adj.get(v).add(u); 
        } 
      
        void printAdjacencyList() 
        { 
            for (int i = 0; i < adj.size(); i++) { 
                System.out.println("Adjacency list of " + i); 
                for (int j = 0; j < adj.get(i).size(); j++) { 
                    System.out.print(adj.get(i).get(j) + " "); 
                } 
                System.out.println(); 
            } 
        } 
    } 
      
    class Test { 
      
        public static void main(String[] args) 
        { 
            // Creating a graph with 5 vertices 
            int V = 5; 
      
            Graph g = new Graph(V); 
      
            // Adding edges one by one. 
            g.addEdge(0, 1); 
            g.addEdge(0, 4); 
            g.addEdge(1, 2); 
            g.addEdge(1, 3); 
            g.addEdge(1, 4); 
            g.addEdge(2, 3); 
            g.addEdge(3, 4); 
            g.printAdjacencyList(); 
        } 
        }

3,，图的BFS（Java）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZWd5MjE4_size_16_color_FFFFFF_t_70]

// prints BFS traversal from a given source s
    void BFS(int s) {
    		// Mark all the vertices as not visited(By default
    		// set as false)
    		boolean visited[] = new boolean[V];
    
    		// Create a queue for BFS
    		LinkedList<Integer> queue = new LinkedList<Integer>();
    
    		// Mark the current node as visited and enqueue it
    		visited[s] = true;
    		queue.add(s);
    
    		while (queue.size() != 0) {
    			// Dequeue a vertex from queue and print it
    			s = queue.poll();
    			System.out.print(s + " ");
    
    			// Get all adjacent vertices of the dequeued vertex s
    			// If a adjacent has not been visited, then mark it
    			// visited and enqueue it
    			Iterator<Integer> i = adj[s].listIterator();
    			while (i.hasNext()) {
    				int n = i.next();
    				if (!visited[n]) {
    					visited[n] = true;
    					queue.add(n);
    				}
    			}
    		}
    	}

4，感悟与思考

图是算法里面常考的，非常重要。BFS算法中，队列的作用：存放 与 所选路径形成的图（染黑的节点） 连接的节点。涉及到了归纳法，从一个节点递归到所有。

[https_zh.wikipedia.org_wiki]: https://zh.wikipedia.org/wiki/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2%EF%BC%89
[2019041711295561.gif]: /images/20220218/9fcb0ee9f4b846aab6990d990624ce1c.png
[20190417113245335.png]: /images/20220218/a301b3ac25834f0b8970cd37dd2f42c8.png
[20190417113602890.png]: /images/20220218/be60a2ca5a424cada69020b40d204431.png
[20190417113928455.png]: /images/20220218/89a6c1681f3e46cd9e3147130c86afb3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZWd5MjE4_size_16_color_FFFFFF_t_70]: /images/20220218/00fc08daf6d140878c0e6ad2167c03eb.png