图的深度优先和广度优先算法-526互联

package com.datastruct.gragh;

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

/**
 * @version 1.0
 * @Author 作者名
 * @Date 2023/3/27 15:18
 */
public class Gragh {
    // 存放顶点的信息
    public ArrayList<String> points;
    // 存放边的关系
    public int[][] edges;
    // 边的条数
    public int numOfEdges;
    // 顶点个数
    int len = 8;
    // 用于记录顶点是否被放访问
    boolean[] isVisited = new boolean[len];


    public Gragh(int n) {
        edges = new int[n][n];
        points = new ArrayList<>(n);
    }

    /**
     * 添加顶点
     * @param point
     */
    public void insertPoint(String point){
        points.add(point);
    }

    /**
     * 添加边的关系
     * 无向图都一样
     * @param from 起始节点
     * @param to 终点顶点
     * @param weight 1 0   1:连通   0:不连通
     */
    public void insertEdge(int from, int to, int weight){
        edges[from][to] = weight;
        edges[to][from] = weight;
        numOfEdges++;
    }

    /**
     * 获取边的条数
     * @return
     */
    public int getEdgeCount(){
        return this.numOfEdges;
    }

    /**
     * 获取顶点个数
     * @return
     */
    public int getPointCount(){
        return points.size();
    }

    /**
     * 获取顶点的名称
     * @param index
     * @return
     */
    public String getValueByIndex(int index){
        return points.get(index);
    }

    /**
     * 获取某一条边的权值2
     * @param from
     * @param to
     * @return
     */
    public int getWeight(int from, int to){
        return edges[from][to];
    }

    /**
     * 显示矩阵
     */
    public void showGraph(){
        char x = 'A';
        System.out.println("  A B C D E");
        for (int[] edge : edges) {
            System.out.print(x++ +" ");
            for (int i : edge) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }
    //-------------------------------------------------------------------
    //----------------------------深度优先遍历-----------------------------
    //-------------------------------------------------------------------
    /**
     * 深度优先遍历
     */
    public void dfs(){
        for (int i = 0; i < getPointCount(); i++) {
            if (!isVisited[i]) {
                dfs(isVisited,i);
            }
        }
    }

    public void dfs(boolean[] isVisited,int i){
        // 先输出第一个节点的值
        System.out.print(points.get(i));
        // 然后将它设置为遍历过
        isVisited[i] = true;

        // 获取i节点的第一个邻居节点
        int w = getFirstNeighbor(i);

        while (w != -1) {
            if(!isVisited[w]){
                dfs(isVisited,w);
            }

            w = getNextNeighbor(i,w);
        }
    }

    /**
     * 从某一个下标开始遍历
     *   A B C D E
     * A 0 0 0 0 0
     * B 0 0 1 0 1
     * C 0 1 0 1 1
     * D 0 0 1 0 1
     * E 0 1 1 1 0
     * @param index
     * @return
     */
    public int getFirstNeighbor(int index){
        for (int i = 0; i < getPointCount(); i++) {
            if(edges[index][i] == 1){
                return i;
            }
        }
        return -1;
    }

    /**
     * 获取节点的下一个节点
     * @param v1
     * @param v2
     * @return
     */
    public int getNextNeighbor(int v1, int v2){
        for (int j = v2 + 1; j < getPointCount(); j++) {
            if(edges[v1][j] == 1){
                return j;
            }
        }

        return -1;
    }

    //-------------------------------------------------------------------
    //----------------------------广度优先遍历----------------------------
    //-------------------------------------------------------------------
    public void bfs(){
        bfs(isVisited,0);
    }

    /**
     * 广度优先算法
     * @param isVisited
     * @param i
     */
    public void bfs(boolean[] isVisited, int i) {

        // 防止覆盖
        for (int k = 0; k < len; k++) {
            isVisited[k] = false;
        }

        Queue<String> queue = new LinkedList<>();

        // 将第一个节点入队
        queue.add(points.get(i));
        isVisited[i] = true;
        // 当队列空时结束
        while (!queue.isEmpty() && i < points.size()) {
            System.out.print(queue.poll());

            // 对一个点的一行的每一列进行遍历
            for (int j = 0; j < getPointCount(); j++) {
                // 如果是连通的 并且是没有被访问过的
                if(edges[i][j] == 1 && !isVisited[j]){
                    queue.add(points.get(j));
                    isVisited[j] = true;
                }
            }
            i++;
        }
    }


}