图:BFS(深度优先搜索)图解分析代码实现

2020/11/09 10:24
阅读数 206

一、介绍

图的DFS(深度优先搜索)与BFS(广度优先搜索)是图的两种遍历方式。

主要区别在于当到达图中的一个顶点后,DFS直接到达其中的一个(未遍历过的)顶点,之后再以这个新的顶点为基点重复上面的操作;而BFS到达图中的一个顶点后,会先遍历顶点周围的所有(未遍历过的)顶点,然后在以其中的一个顶点为基点,重复上面的操作。

举个简单的例子:
在这里插入图片描述
如果分别用DFS和BFS进行遍历(以A为起点):
DFS:A B D E C (一条路走到头)
BFS:A B C D E (先把A的周围走完,接着走完B和C的周围)



这篇文章将进行BFS的分析,前一篇文章分析DFS。

二、图的建立

2.1建立图类

  • 使用邻接矩阵保存图的信息。
  • 为了给每个顶点起名字,使用了两组map集合使顶点的名字与邻接矩阵的数字一一对应。
  • 用boolean型数组记录某节点是否被访问过。

代码

class graph{
   
   
    int vertexNum;//顶点数
    int edgeNum;//边数
    int[][] adjacentMatrix;//邻接矩阵
    boolean[] isVisited;//各顶点是否被访问

    Map<Character,Integer> nameToNum;
    Map<Integer,Character> numToName;
    int index;//顶点名称的下标

    //构造函数
    graph(int vertexnum, int edgenum){
   
   
        vertexNum = vertexnum;
        edgeNum = edgenum;
        adjacentMatrix = new int[vertexNum][vertexNum];
        nameToNum = new HashMap<>();
        numToName = new HashMap<>();
        isVisited = new boolean[vertexnum];
    }

    //顶点名称
    public void addVertexName(char vertex){
   
   
        nameToNum.put(vertex,index);
        index++;
    }

    //反转顶点和其索引的对应关系
    public void invertNameToNum(){
   
   
        Set<Character> chs = nameToNum.keySet();
        for (Character c : chs) {
   
   
            numToName.put(nameToNum.get(c),c);
        }
    }

    //打印两个map
    public void printMap(){
   
   
        System.out.println("name to num:");
        Set<Character> chs = nameToNum.keySet();
        for (Character c : chs) {
   
   
            System.out.println(c + "->" + nameToNum.get(c));
        }
        System.out.println();
        System.out.println("num to name:");
        Set<Integer> ins = numToName.keySet();
        for (Integer in : ins) {
   
   
            System.out.println(in+"->"+ numToName.get(in));
        }

    }

    //添加边
    public void addEdge(char vertex1, char vertex2, int weight){
   
   
        adjacentMatrix[nameToNum.get(vertex1)][nameToNum.get(vertex2)] = weight;
        adjacentMatrix[nameToNum.get(vertex2)][nameToNum.get(vertex1)] = weight;
    }

    //打印邻接矩阵
    public void printAdjacentMatrix(){
   
   
        for (int[] am : adjacentMatrix) {
   
   
            for (int i : am) {
   
   
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }
    
}

2.2建立图

以下面的图为例,建立图结构。
在这里插入图片描述
main方法中的代码:

    public static void main(String[] args) {
   
   
        //while (true) {
   
   
        System.out.println("请输入顶点数:");
        Scanner sc = new Scanner(System.in);
        int vertexNum = sc.nextInt();
        System.out.println("请输入边数:");
        int edgeNum = sc.nextInt();
        graph gr = new graph(vertexNum, edgeNum);

        for (int i = 0; i < vertexNum; i++) {
   
   
            System.out.println("请输入第" + i + "个顶点的名称:");
            gr.addVertexName(sc.next().charAt(0));//字符串的第一个字符存入
        }
        gr.invertNameToNum();
        for (int i = 0; i < edgeNum; i++) {
   
   
            System.out.println("请输入第" + i + "条边(name1 name2 weight):");
            gr.addEdge(sc.next().charAt(0), sc.next().charAt(0), 1);//无向图权重为1,不用输入
        }
        gr.printAdjacentMatrix();
	}	

依次输入相关信息:
在这里插入图片描述
在这里插入图片描述
出来的邻接矩阵:
在这里插入图片描述



三、BFS

  • BFS方法使用队列进行遍历。
  • 先将出发点压入队列,之后将其周围的点压入队列。
  • 出队列的过程就是遍历输出的过程。
  • 每次出队列时,将其周围的(未遍历过的)顶点都入队列。
  • 当队列中没有元素了,就表明遍历完成。

3.1图解:

以A为起始点,将A的周围顶点都入队列(队列=ABCD),A出队列输出A,A周围的顶点都入队列了,不用执行入队列操作。
在这里插入图片描述
此时队列=BCD,B出队列,输出B,将B相邻顶点E入队列。
在这里插入图片描述
此时队列=BCDE,C出队列,输出C,将C相邻顶点F入队列。
在这里插入图片描述
此时队列=DEF,D出队列,输出D,将D相邻顶点G入队列。
在这里插入图片描述
此时队列=EFG,E出队列,输出E。后面循环这个操作,依次输出E,F,G。
在这里插入图片描述
输出顺序为:A B C D E F G。
代码:










3.2代码

graph类中的方法。

    public void BFS(){
   
   
        Queue<Integer> qu = new ArrayDeque<>();//创建队列
        qu.add(0);//从第0开始访问
        System.out.print(numToName.get(0)+ "->");
        isVisited[0] = true;
        while(!qu.isEmpty()){
   
   //队列是否为非空
            int po = qu.poll();//出队列
            int start = 0;
            while(start < vertexNum ){
   
   //将周围的顶点(未标记过的)入队列
                if(adjacentMatrix[po][start] != 0 && !isVisited[start]){
   
   
                    qu.add(start);//入队列
                    System.out.print(numToName.get(start)+"->");//输出
                    isVisited[start] = true;//标记为访问过
                }
                start++;
            }
        }
        System.out.println("结束");
    }

结果:A->B->C->D->E->F->G->结束

四、DFS和BFS完整代码

package graph;
import java.util.*;

public class BFSAndDFS {
   
   
    public static void main(String[] args) {
   
   
        System.out.println("请输入顶点数:");
        Scanner sc = new Scanner(System.in);
        int vertexNum = sc.nextInt();
        System.out.println("请输入边数:");
        int edgeNum = sc.nextInt();
        graph gr = new graph(vertexNum, edgeNum);

        for (int i = 0; i < vertexNum; i++) {
   
   
            System.out.println("请输入第" + i + "个顶点的名称:");
            gr.addVertexName(sc.next().charAt(0));//字符串的第一个字符存入
        }
        gr.invertNameToNum();

        for (int i = 0; i < edgeNum; i++) {
   
   
            System.out.println("请输入第" + i + "条边(name1 name2 weight):");
            gr.addEdge(sc.next().charAt(0), sc.next().charAt(0), 1);
        }
        gr.printAdjacentMatrix();
        gr.DFS();
        gr.BFS();
    }

}

class graph{
   
   
    int vertexNum;//顶点数
    int edgeNum;//边数
    int[][] adjacentMatrix;//邻接矩阵
    boolean[] isVisited;//各顶点是否被访问

    Map<Character,Integer> nameToNum;
    Map<Integer,Character> numToName;
    int index;//顶点名称的下标

    //构造函数
    graph(int vertexnum, int edgenum){
   
   
        vertexNum = vertexnum;
        edgeNum = edgenum;
        adjacentMatrix = new int[vertexNum][vertexNum];
        nameToNum = new HashMap<>();
        numToName = new HashMap<>();
        isVisited = new boolean[vertexnum];
    }

    //顶点名称
    public void addVertexName(char vertex){
   
   
        nameToNum.put(vertex,index);
        index++;
    }

    //反转顶点和其索引的对应关系
    public void invertNameToNum(){
   
   
        Set<Character> chs = nameToNum.keySet();
        for (Character c : chs) {
   
   
            numToName.put(nameToNum.get(c),c);
        }
    }

    //打印两个map
    public void printMap(){
   
   
        System.out.println("name to num:");
        Set<Character> chs = nameToNum.keySet();
        for (Character c : chs) {
   
   
            System.out.println(c + "->" + nameToNum.get(c));
        }
        System.out.println();
        System.out.println("num to name:");
        Set<Integer> ins = numToName.keySet();
        for (Integer in : ins) {
   
   
            System.out.println(in+"->"+ numToName.get(in));
        }

    }

    //添加边
    public void addEdge(char vertex1, char vertex2, int weight){
   
   
        adjacentMatrix[nameToNum.get(vertex1)][nameToNum.get(vertex2)] = weight;
        adjacentMatrix[nameToNum.get(vertex2)][nameToNum.get(vertex1)] = weight;
    }

    //打印邻接矩阵
    public void printAdjacentMatrix(){
   
   
        for (int[] am : adjacentMatrix) {
   
   
            for (int i : am) {
   
   
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

    /**
     * 深度优先遍历
     * @param index 顶点的索引
     */
    public void DFS(int index){
   
   
        System.out.print(numToName.get(index) + "->");
        isVisited[index] = true;
        int start = 0;
        while( start < vertexNum && (adjacentMatrix[index][start] == 0||(adjacentMatrix[index][start] != 0 && isVisited[start]))){
   
   
            start++;
        }

        if(start > vertexNum - 1){
   
   
            return;
        }

        DFS(start);
    }


    public void DFS(){
   
   
        for (int i = 0; i < vertexNum; i++) {
   
   
            if(!isVisited[i]){
   
   
                DFS(i);
            }
        }
        System.out.println("结束");
        for (int i = 0; i < isVisited.length; i++) {
   
   
            isVisited[i] = false;
        }
    }

    public void BFS(){
   
   
        Queue<Integer> qu = new ArrayDeque<>();//创建队列
        qu.add(0);//从第0开始访问
        System.out.print(numToName.get(0)+ "->");
        isVisited[0] = true;
        while(!qu.isEmpty()){
   
   
            int po = qu.poll();
            int start = 0;
            while(start < vertexNum ){
   
   
                if(adjacentMatrix[po][start] != 0 && !isVisited[start]){
   
   
                    qu.add(start);
                    System.out.print(numToName.get(start)+"->");
                    isVisited[start] = true;
                }
                start++;
            }
        }
        System.out.println("结束");
    }

}

展开阅读全文
def
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部
返回顶部
顶部