欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构-图,图的深度优先遍历和广度优先遍历(Java实现)

程序员文章站 2022-05-22 20:01:40
...
线性表和树都能处理单对多的关系,想要处理多对多的关系时我们可以使用图
图的使用最常见在地图
package datastructure.graph;

/*
    @CreateTime 2021/9/20 22:02
    @CreateBy cfk

*/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Graph {

    public static void main(String[] args) {

        /*
        数据量少时发现两种遍历完全一样
        Graph graph = new Graph(5);

        String[] vertex = {"A","B","C","D","E"};

        for (String node : vertex) {
            graph.addVertex(node);
        }

        graph.addEdge(0,1,1);
        graph.addEdge(0,2,1);
        graph.addEdge(1,2,1);
        graph.addEdge(1,3,1);
        graph.addEdge(1,4,1);
        */

        //更换不同的数据测试得出结果
        Graph graph = new Graph(8);

        String[] vertex = {"1","2","3","4","5","6","7","8"};

        for (String node : vertex) {
            graph.addVertex(node);
        }

        //更新边的关系
        graph.addEdge(0, 1, 1);
        graph.addEdge(0, 2, 1);
        graph.addEdge(1, 3, 1);
        graph.addEdge(1, 4, 1);
        graph.addEdge(3, 7, 1);
        graph.addEdge(4, 7, 1);
        graph.addEdge(2, 5, 1);
        graph.addEdge(2, 6, 1);
        graph.addEdge(5, 6, 1);

        //显示矩阵
        graph.showEdges();

        //测试深度遍历 是否成功
        System.out.println("深度优先遍历");
        graph.dfs();
        System.out.println();
        //测试广度遍历
        System.out.println("广度优先遍历");
        graph.bfs();
    }

    private ArrayList<String> vertexList; //存储顶点元素
    private int[][] edges; //存储图对应的邻接矩阵
    private int numOfEdges; //存储图的边数
    private boolean[] isVisited; //记录节点是否被访问

    public Graph(int n) {
        vertexList = new ArrayList<String>(); //创建一个集合来存储顶点
        edges = new int[n][n]; //初始化一个二维数组 长宽都为元素个数
        numOfEdges = 0; //默认边数为0
        isVisited = new boolean[n];
    }

    /* =====================bfs(广度优先遍历算法)====================================
    1)访问初始结点v并标记结点v为已访问。
    2)结点v入队列
    3)当队列非空时,继续执行,否则算法结束。
    4)出队列,取得队头结点u。
    5)查找结点u的第一个邻接结点w。
    6)若结点u的邻接结点w不存在,则转到步骤3;
    否则循环执行以下三个步骤:
    6.1若结点w尚未被访问,则访问结点w并标记为已访问。
    6.2结点w入队列
    6.3查找结点u的继w邻接结点后的下一个邻接结点w,转到步骤6。
     */
    public void bfs() {
        for (int i = 0; i < getVertex(); i++) {
            bfs(isVisited,i);
        }
    }

    public void bfs(boolean[] isVisited, int v) {
        //队列的头节点
        int u;
        //邻接结点
        int w;


        //创建一个队列记录 位置
        LinkedList<Integer> queue = new LinkedList<>();

        System.out.print(getValueByIndex(v)+"=>");

        //记录表示已经被访问
        isVisited[v] = true;

        //结点v入列
        queue.addLast(v);

        while (!queue.isEmpty()){
            //获取队列的头结点
            u = queue.removeFirst();
            //查询邻接结点
            w = getFirstNeighbor(u);

            while (w != -1){
                if (!isVisited[w]){
                    System.out.print(getValueByIndex(w) + "=>");
                    isVisited[w] = true; //标记为已访问
                    queue.addLast(w);
                }
                w = getNextNeighbor(w,u);
            }
        }

    }


    //============================================================================

    /* =====================dfs(深度优先遍历算法)====================================

     */
    //由于下面的算法仅仅只对了一个元素进行操作 所以这里重载一个方法依次对所有的元素进行遍历
    public void dfs(){
        for (int i = 0; i < getVertex(); i++) {
            if (!isVisited[i]){
                dfs(isVisited,i);
            }
        }
    }

    //深度优先遍历算法
    /*
    深度优先遍历算法步骤
    1)访问初始结点v,并标记结点v为已访问。
    2)查找结点v的第一个邻接结点w。
    3)若w存在,则继续执行4,如果w不存在,则回到第1步,将从v的下一个结点继续。
    4)若w未被访问,对w进行深度优先遍历递归(即把w当做另一个v,然后进行步骤123)。
    5)查找结点v的w邻接结点的下一个邻接结点,转到步骤3。
     */
    public void dfs(boolean[] isVisited, int v){
        //首先访问初始结点
        System.out.print(getValueByIndex(v)+"=>");

        //标记结点被访问
        isVisited[v] = true;

        //查找结点v的第一个邻接结点w
        int w = getFirstNeighbor(v);

        while (w != -1) {
            if (!isVisited[w]){
                dfs(isVisited,w);
            }
            //从当前结点下一行开始循环,因为前面就算能找到也没用
            /*
            [0, 1, 1, 0, 0]
            [1, 0, 1, 1, 1]
            [1, 1, 0, 0, 0]   比如第一次找到(0,1)后去到(1,1)继续查找
            [0, 1, 0, 0, 0]
            [0, 1, 0, 0, 0]
             */
            w = getNextNeighbor(w, v);
        }
    }

    //找到某一个初始结点的第一个邻接结点并且返回
    public int getFirstNeighbor(int index) {
        for (int i = 0; i < vertexList.size(); i++) {
            //因为当此点为1时说明为邻接结点 所以大于0说明已经找到了
            if (edges[index][i] > 0){
                return i;
            }
        }
        //如果没有找到返回-1
        return -1;
    }

    //根据前一个结点获取下一个邻接结点
    public int getNextNeighbor(int v1, int v2) {
        for (int i = v1 + 1; i < vertexList.size(); i++) {
            if (edges[v2][i] > 0){
                return i;
            }
        }
        return -1;
    }


    //=========================================================
    //通过数组下标获取数组
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }

    //展示矩阵
    public void showEdges(){
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));//打印二维数组
        }
    }

    //返回m和n的状态 1代表相连 0代表不相连
    public int getStatue(int m, int n) {
        return edges[m][n];
    }

    //添加顶点
    public void addVertex(String node) {
        vertexList.add(node);

    }

    //获取数组顶点个数
    public int getVertex(){
        return vertexList.size();
    }

    //获取数组的边数
    public int getEdges(){
        return numOfEdges;
    }

    //添加边元素
    public void addEdge(int m, int n, int status){
        edges[m][n] = status;
        edges[n][m] = status;
        numOfEdges++;
    }

}

相关标签: 数据结构 java