图的理解：深度优先和广度优先遍历

#遍历

图的遍历，所谓遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种访问策略：

• 深度优先遍历
• 广度优先遍历 #深度优先

---

深度优先遍历，从初始访问结点出发，我们知道初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点。总结起来可以这样说：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。 我们从这里可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。 具体算法表述如下：

1. 访问初始结点v，并标记结点v为已访问。
2. 查找结点v的第一个邻接结点w。
3. 若w存在，则继续执行4，否则算法结束。
4. 若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。
   查找结点v的w邻接结点的下一个邻接结点，转到步骤3。
   例如下图，其深度优先遍历顺序为 1->2->4->8->5->3->6->7
   #广度优先

---

类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点。 具体算法表述如下：

1. 访问初始结点v并标记结点v为已访问。
2. 结点v入队列
3. 当队列非空时，继续执行，否则算法结束。
4. 出队列，取得队头结点u。
5. 查找结点u的第一个邻接结点w。
6. 若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤：
   1). 若结点w尚未被访问，则访问结点w并标记为已访问。
   2). 结点w入队列
   3). 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。
   如下图，其广度优先算法的遍历顺序为：1->2->3->4->5->6->7->8
   

package com.lifeibigdata.algorithms.graph.liantongfenliang;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by leofei.li on 2016/5/21.
 */
public class BFS {
    static int verNum;
    static boolean []visited;
    static String []ver={"A","B","C","D","E"};
    static int  [][]edge;

    void addEdge(int i,int j){
        if(i == j)return;
        edge[i][j]=1;
        edge[j][i]=1;
    }

    void dfsTraverse(){
        visited = new boolean[verNum];
        for(int i = 0; i< verNum; i ++){
            if(visited[i] == false){
                dfs(i);
            }
        }
    }
    void dfs(int i){
        visited[i] = true;
        System.out.print(ver[i] + " ");
        for(int j = 0; j < verNum; j++){
            if(visited[j] == false && edge[i][j] == 1){
                dfs(j);
            }
        }
    }

    void bfsTraverse(){
        visited = new boolean[verNum];
        Queue<Integer> quene = new LinkedList<Integer>();
        for (int i = 0; i < verNum; i ++){
            if(visited[i] == false){
                visited[i] = true;
                System.out.print(ver[i]+" ");
                quene.add(i);           //此处存储的是索引
                while (!quene.isEmpty()){ //注意结束条件
                    int j = quene.poll();
                    for (int k = 0; k < verNum; k++){    //找到该节点所有的子节点
                        if(edge[j][k] == 1 && visited[k] == false){
                            visited[k] = true;
                            System.out.print(ver[k]+" ");
                            quene.add(k);
                        }
                    }
                }
            }
        }
    }

    void con(){
        int count = 0;
        visited = new boolean[verNum];
        for(int i = 0; i < verNum; i ++){
            if(!visited[i]){
                count++;
                dfsTraverse();
            }
        }
        System.out.println("共有"+count+"个连通分量!");
    }

    public static void main(String[] args) {
        verNum = ver.length;
        edge = new int[verNum][verNum];
        for(int i=0;i<verNum;i++){
            for (int j=0;j<verNum;j++){
                edge[i][j]=0;
            }
        }
        BFS b = new BFS();
        b.addEdge(0, 3);
        b.addEdge(0, 4);
        b.addEdge(1, 2);
        b.addEdge(2, 4);
        b.addEdge(2, 3);

        System.out.println("图的深度遍历操作:");
        b.dfsTraverse();
        System.out.println();
        System.out.println("图的广度遍历操作：");
        b.bfsTraverse();
        System.out.println();
        System.out.println("连通分量:");
        b.con();
    }
}

不管深搜还是广搜都需要申请总节点个数长度的数组用来标记节点是否访问过(访问数组)；深搜是遍历访问数组，从某个未被访问的节点辐射出去，每次辐射结束后，判断访问数组中是否还有未被访问的节点，如果有，再次辐射，如果没有，深搜结束；广搜是同样是遍历数组，判断是否有为被访问的节点，如果有放到对列中，然后弹出队列，将弹出节点所有未被访问的邻接节点放到队列中，继续进行访问队列，直到队列为空时继续判断访问数组

原文链接：https://segmentfault.com/a/1190000002685939#articleHeader0