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

2021年9月19日 2点热度 0条评论 来源: lifeibigdata

遍历

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

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

深度优先

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

  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

    原文作者:lifeibigdata
    原文地址: https://blog.csdn.net/lifeibigdata/article/details/51612737
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。