图(一,图的基本概念)

58.jpg

图的概念:

由顶点的有穷非空集合和顶点之间的边组成.
like this :

image.png

图的存储方式:

我们用邻接矩阵和邻接表来表示一个图

• 邻接矩阵

  
  image.png

• 邻接表

  
  image.png

图的遍历:

• 深度优先
  以迷宫为例
  深度优先就是一直往下走,遇到走不通的地方就退回到分叉口,往另一个方向走

  
  image.png
  

  类似于树的前序遍历

• 广度优先
  广度优先类似于树的分层遍历
  先访问当前顶点的所有邻接点,再往下一层访问

image.png

以上面的图为例:
深度优先:v0>v1>v3>退回到v0>v2>over
广度优先:第一步:v0>v1和v0>v2同时进行 next:v1>v3 结束

代码:

import java.util.LinkedList;

public class Graphic {

    public int[] vertices;//顶点集
    public int verticesSize;
    public int[][] matrix;//图的边信息
    public static final int MAX_WEIGHT = Integer.MAX_VALUE;
    public boolean[] isVisited;

    public Graphic() {
    }

    public Graphic(int verticesSize) {
        this.verticesSize = verticesSize;
        this.vertices = new int[verticesSize];
        this.matrix = new int[verticesSize][verticesSize];
        this.isVisited = new boolean[verticesSize];

        for (int i = 0; i < verticesSize; i++) {
            vertices[i] = i;
        }
    }

    //获取权重
    private int getWeight(int v1, int v2) {
        int weight = matrix[v1][v2];
        return weight == MAX_WEIGHT ? -1 : weight;
    }

    //获取顶点
    private int[] getVertices() {
        return vertices;
    }

    //获取入度
    private int getInDegree(int v) {
        int inDegree = 0;
        for (int i = 0; i < verticesSize; i++) {
            int weight = getWeight(i, v);
            if (weight > 0) {
                inDegree++;
            }
        }
        return inDegree;
    }

    //获取出度
    private int getOutDegree(int v) {
        int outDegree = 0;
        for (int i = 0; i < verticesSize; i++) {
            int weight = getWeight(v, i);
            if (weight > 0) {
                outDegree++;
            }
        }
        return outDegree;
    }

    //获取第一个邻接点
    private int getFirstNeightbor(int v) {
        for (int i = 0; i < verticesSize; i++) {
            if (getWeight(v, i) > 0) {
                return i;
            }
        }
        return -1;
    }

    //获取顶点v的邻接点index的下一个邻接点
    private int getNextNeightBor(int v, int index) {
        for (int i = index + 1; i < verticesSize; i++) {
            if (getWeight(v, i) > 0) {
                return i;
            }
        }
        return -1;
    }

    //深度优先

    public void dfs() {
        for (int i = 0; i < verticesSize; i++) {
            if (!isVisited[i]) {
                dfs(i);
            }
        }
    }

    private void dfs(int i) {
        isVisited[i] = true;
        System.out.println("visited vertices" + i);
        int v = getFirstNeightbor(i);
        while (v != -1) {
            if (!isVisited[v]) {
                dfs(v);
            }
            v = getNextNeightBor(i, v);
        }
    }

    //广度优先
    public void bfs() {
        for (int i = 0; i < verticesSize; i++) {
            isVisited[i] = false;
        }

        for (int i = 0; i < verticesSize; i++) {
            if (!isVisited[i]) {
                System.out.println("visited vertices: " + i);
                isVisited[i] = true;
                bfs(i);
            }
        }
    }

    private void bfs(int i) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        //获取当前结点的邻接点
        int v = getFirstNeightbor(i);
        if (v <= 0) {
            return;
        }
        if (!isVisited[v]) {
            System.out.println("visited vertices:" + v);
            isVisited[v] = true;
            linkedList.offer(v);
        }

        //把后面的邻接点都入队
        int next = getNextNeightBor(i, v);
        while (next > 0) {
            if (!isVisited[next]) {
                System.out.println("visited vertices:" + next);
                isVisited[next] = true;
                linkedList.offer(next);
            }
            next = getNextNeightBor(i, next);
        }

        while (!linkedList.isEmpty()) {
            bfs(linkedList.poll());
        }
    }


}

    @Test
    public void test(){
        Graph graph = new Graph(5);
        int[] v0 = new int[]{0, 1, 1, MAX_WEIGHT, MAX_WEIGHT};
        int[] v1 = new int[]{MAX_WEIGHT, 0, MAX_WEIGHT, 1, MAX_WEIGHT};
        int[] v2 = new int[]{MAX_WEIGHT, MAX_WEIGHT, 0, MAX_WEIGHT, MAX_WEIGHT};
        int[] v3 = new int[]{1, MAX_WEIGHT, MAX_WEIGHT, 0, MAX_WEIGHT};
        int[] v4 = new int[]{MAX_WEIGHT, MAX_WEIGHT, 1, MAX_WEIGHT, 0};
        graph.matrix[0] = v0;
        graph.matrix[1] = v1;
        graph.matrix[2] = v2;
        graph.matrix[3] = v3;
        graph.matrix[4] = v4;
//        graph.dfs();
        graph.bfs();
    }