邻接矩阵定义一个图

其实就是二维数组来定义

package top.zcwfeng.java.arithmetic.graph;

/**
 *    /  v0
 *  /   |  \
 * /    |   \
 * v1   |    v3
 *   \  |    /
 *    \ |  /
 *     v2
 *
 *
 */
public class GraphDemo {
    // 定义节点数
    protected int size;
    // 定义数组保存定点信息
    protected String[]nodes;
    // 定义矩阵保存边
    protected int[][]edges;

    //遍历标记
    protected int[]visit;

    /**
     *      v0 v1 v2 v3
     * v0   0  1   1  1
     * v1   1  0   1  0
     * v2   1  1   0  1
     * v3   1  0   1  0
     */
    public GraphDemo() {
        size = 4;
        // 初始化定点
        nodes = new String[size];
        for (int i = 0; i < size; i++) {
            nodes[i] = String.valueOf(i);
        }

        //初始化边
        edges= new int[size][size];
        edges[0][1] = 1;
        edges[0][2] = 1;
        edges[0][3] = 1;
        edges[1][0] = 1;
        edges[1][2] = 1;
        edges[2][0] = 1;
        edges[2][1] = 1;
        edges[2][3] = 1;
        edges[3][0] = 1;
        edges[3][2] = 1;

    }

    public static void main(String[] args) {
        GraphDemo graph = new GraphDemo();
    }
}

图的遍历

1. 深度搜索遍历

2.广度搜索遍历

->「定义一个图」
package top.zcwfeng.java.arithmetic.graph;
/*
 * 定义图的结构
 *
 * A-F-G-E
 * |\
 * C-D
 * |
 * B
 *
 */
public class Graph {


    //节点数目
    protected int size;
    //定义数组，保存顶点信息
    protected String[] nodes;

    //定义矩阵保存顶点信息
    protected int[][] edges;

    /**
     * A B C D E F G
     * A  0 0 1 1 0 1 0
     * B  0 0 1 0 0 0 0
     * C  1 1 0 1 0 0 0
     * D  1 0 1 0 0 0 0
     * E  0 0 0 0 0 0 1
     * F  1 0 0 0 0 0 1
     * G  0 0 0 0 1 1 0
     */
    public Graph() {
        //初始化顶点
        nodes = new String[]{"A", "B", "C", "D", "E", "F", "G"};
        size = nodes.length;

        //初始化边---- 为了直观，做一个常量定义
        final int A = 0, B = 1, C = 2, D = 3, E = 4, F = 5, G = 6;
        edges = new int[size][size];
        edges[A][C] = 1;
        edges[A][D] = 1;
        edges[A][F] = 1;
        edges[B][C] = 1;
        edges[C][A] = 1;
        edges[C][D] = 1;
        edges[C][B] = 1;
        edges[D][A] = 1;
        edges[D][C] = 1;
        edges[E][G] = 1;
        edges[F][A] = 1;
        edges[F][G] = 1;
        edges[G][F] = 1;
        edges[G][E] = 1;
    }


}

遍历

package top.zcwfeng.java.arithmetic.graph;

import java.util.ArrayList;
import java.util.List;

/**
 * 图的遍历
 * A-F-G-E
 * |\
 * C-D
 * |
 * B
 */
public class GraphCover extends Graph{
    private int[] visit = new int[size];     //遍历标志，防止死环遍历

    /**
     * 深度优先遍历
     * 一条路走到黑,不撞南墙不回头
     * 对每一个可能的分支路径深入到不能再深入为止
     */
    public void DeepFirst(int start) {//从第n个节点开始遍历

        visit[start] = 1;              //标记为1表示该顶点已经被处理过
        System.out.println("齐天大圣到—>" + this.nodes[start]+"一游"); //输出节点数据

        for (int i=0;i<this.size;i++){
            if (this.edges[start][i] == 1 && visit[i]==0){
                //邻接点
                DeepFirst(i);
            }
        }

    }

    /**
     * 广度优先遍历
     * 广度优先搜索遍历图的过程中以v 为起始点，由近至远，
     * 依次访问和v 有路径相通且路径长度为1,2,…的顶点
     * 第一批节点的邻接点，?
     *
     *
     * AC|AD|AF|ACB|AFG|AFGE
     *
     *
     */
    private int[] queue = new int[size];
    public void BreadthFirst(int front,int tail) {
        int last = tail;

        for (int index=front;index<=tail;index++){
            int node = queue[index];

            System.out.println("齐天大圣到—>" + this.nodes[node]+"一游"); //输出节点数据
            //找出所有的邻接点
            for (int i=0;i<this.size;i++){
                if (this.edges[node][i] == 1 && visit[i]==0){
                    //邻接点
                    visit[i] = 1;
                    queue[++last] = i;

                }
            }
        }

        //遍历下一批节点
        if (last > tail){
            BreadthFirst(tail+1,last);
        }

    }

    public void BreadthFirst(int start){
        queue[0] = start;
        visit[start] = 1;
        BreadthFirst(0,0);
    }



    public void BreadthFirstOld(List<Integer> temp_nodes) {
        List<Integer> lastNodes = new ArrayList<>();
        for (int node:temp_nodes){
            visit[node] = 1;
            System.out.println("齐天大圣到—>" + this.nodes[node]+"一游"); //输出节点数据
            //找出所有的邻接点
            for (int i=0;i<this.size;i++){
                if (this.edges[node][i] == 1 && visit[i]==0){
                    //邻接点
                    lastNodes.add(i);

                }
            }
        }

        //遍历下一批节点
        if (lastNodes.size() > 0){
            BreadthFirstOld(lastNodes);
        }

    }

    public static void main(String[] args) {
        GraphCover graph = new GraphCover();
//        1前深度搜索
        graph.DeepFirst(0);

//        2 优化前广度搜索
//        List<Integer> nodes = new ArrayList<>();
//        nodes.add(0);
//        graph.BreadthFirstOld(nodes);


//3 优化后广度搜索
//        graph.BreadthFirst(0);
    }
}