BFS & DFS（Java实现）

我就是我 2021-09-19 23:02 359阅读 0赞

[https://blog.csdn.net/lixibin0829/article/details/79262763][https_blog.csdn.net_lixibin0829_article_details_79262763]

BFS 广度优先搜索 （Broadth First Search）  
类似于树按层次遍历的过程  
要求顺次访问  
为了顺次访问路径长度为2、3、…的顶点，需要使用队列记录已访问的顶点  
时间复杂度：O（n + e）   
e为无向图中边的数或有向图中弧的数  
    /\*\*  
     \* Broadth First Search  
     \* @param graph 用于存放图中每个结点的邻接表  
     \*              key：Character value：该结点的邻接表 LinkedList<Character>  
     \* @param map 用于存放每个结点与顶点的距离  
     \*            key：Character value：距离  
     \* @param start 起始顶点  
     \*/  
    public void BFS(HashMap<Character, LinkedList<Character>> graph,  
                    HashMap<Character, Integer> map,  
                    char start) \{

Queue<Character> q = new LinkedList<>();  
        q.add(start); //将起始顶点加入队列  
        map.put(start, 0);

int i = 0;

while (!q.isEmpty()) \{  
            //取出队首元素  
            char top = q.poll();

i++;  
            System.out.println("The" + i +"th element: " + top + "Distance from start is: " + map.get(top));

//计算周边未访问过的结点的距离  
            int distance = map.get(top) + 1;

//访问队首元素结点的邻接表  
            for (Character c : graph.get(top)) \{

//在该邻接表中，如果某元素还没被访问到，说明还未遍历，则访问这个结点  
                if (!map.containsKey(c))\{  
                    map.put(c, distance);  
                    q.add(c);  
                \}  
            \}  
        \}  
    \}  
  
DFS 深度优先搜索 （Depth First Search）  
可以快速发现底部元素  
时间复杂度：O（n + e）   
e为无向图中边的数或有向图中弧的数  
    static int count = 0;

/\*\*  
     \* Broadth First Search  
     \* @param graph 用于存放图中每个结点的邻接表  
     \*              key：Character value：该结点的邻接表 LinkedList<Character>  
     \* @param visited 用于存放每个结点与顶点的距离  
     \*            key：Character value：距离  
     \* @param start 起始顶点  
     \*/  
    public void DFS(HashMap<Character, LinkedList<Character>> graph,  
                    HashMap<Character, Boolean> visited,  
                    char start) \{  
        visit(graph, visited, 's');  
    \}

private static void visit(HashMap<Character, LinkedList<Character>> graph,  
                              HashMap<Character, Boolean> visited,  
                              char start) \{  
        if (!visited.containsKey(start)) \{  
            count++;  
            //记录进入该结点的时间  
            System.out.println("The time into element: " + start + ":" + count);  
            //将该结点标志为已访问  
            visited.put(start, true);

//访问队首元素结点的邻接表  
            for (char c : graph.get(start)) \{  
                //递归访问其他邻近结点  
                if (!visited.containsKey(c)) \{  
                    visit(graph, visited, c);  
                \}  
            \}  
            count++;  
            System.out.println("The time out element: " + start + ":" + count);  
        \}

\---------------------

[https_blog.csdn.net_lixibin0829_article_details_79262763]: https://blog.csdn.net/lixibin0829/article/details/79262763