目录

基本介绍

为什么要有图

线性表局限于一个直接前驱和一个直接后继,树也只能有一个直接前驱也就是父节点,当我们要表示多对多的关系时就需要用到图。

图的常用概念

https://gitee.com/lienhui68/picStore/raw/master/null/20200630194715.png

  1. 顶点(vertex)
  2. 边(edge)
  3. 路径A->B->C
  4. 无向图 顶点之间的连接没有方向,A->B也可以B->A
  5. 有向图 顶点之间的连接有方向,比如A->B不能是B->A
  6. 带权图 边带权值,带权图也叫网

图的表示方式

两种表示方式:二维数组表示(邻接矩阵),链表表示(邻接表)。

  1. 邻接矩阵 邻接矩阵是表示图形中顶点之间相邻关系的矩阵,对于 n 个顶点的图而言,矩阵是的 row 和 col 表示的是 1….n 个点。 https://gitee.com/lienhui68/picStore/raw/master/null/20200630195237.png
  2. 邻接表 邻接矩阵需要为每个顶点都分配n个边的空间,其实有很多边都是不存在,会造成空间的一定损失.,邻接表的实现只关心存在的边,不关心不存在的边。因此没有空间浪费,邻接表由数组+链表组成 https://gitee.com/lienhui68/picStore/raw/master/null/20200630195300.png

代码实现

构建下图所示这个图,要求能够添加边,最后打印出邻接矩阵

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
package com.eh.ftd.dsa.ds;

import java.util.*;
import java.util.Queue;

/**
 * 图
 *
 * @author David Li
 * @create 2020/06/30 19:54
 */
public class Graph {
    /**
     * 图的邻接矩阵表现形式
     */
    private int[][] matrix;

    /**
     * 顶点的表现形式
     */
    private List<String> vertexNames;

    /**
     * 顶点是否被访问过,用于遍历
     */
    private boolean[] visited;

    /**
     * 构造器
     *
     * @param vertexNames 顶点名称数组
     */
    public Graph(String[] vertexNames) {
        this.matrix = new int[vertexNames.length][vertexNames.length];
        this.vertexNames = Arrays.asList(vertexNames);
        visited = new boolean[vertexNames.length];
    }

    private int getIndexByVertexName(String vertexName) {
        for (int i = 0; i < vertexNames.size(); i++) {
            if (vertexName.equals(vertexNames.get(i))) {
                return i;
            }
        }
        throw new RuntimeException();
    }

    public void buildEdge(String v1, String v2) {
        int idx1 = getIndexByVertexName(v1);
        int idx2 = getIndexByVertexName(v2);
        matrix[idx1][idx2] = 1;
        matrix[idx2][idx1] = 1;
    }

    public void printMatrix() {
        for (int[] arr : matrix) {
            System.out.println(Arrays.toString(arr));
        }
    }

    /**
     * 深度优先遍历
     *
     * @param idx
     */
    public void dfs(int idx) {
        // 输出自己
        System.out.println(vertexNames.get(idx));
        // 标记已访问
        visited[idx] = true;
        // 访问第一个邻居节点
        for (int i = 0; i < vertexNames.size(); i++) {
            if (!visited[i] && matrix[idx][i] == 1)
                dfs(i);
        }
    }


    /**
     * 广度优先遍历
     *
     * @param
     */
    public void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        // 入队自己
        queue.add(0);

        while (!queue.isEmpty()) {
            int idx = queue.poll();
            // 输出
            System.out.println(vertexNames.get(idx));
            // 标记已访问
            visited[idx] = true;

            // 将邻居入队
            for (int i = 0; i < vertexNames.size(); i++) {
                if (!visited[i] && matrix[idx][i] == 1) {
                    // 入队
                    queue.add(i);
                }
            }


        }

    }

    public static void main(String[] args) {
        String[] vertexNames = {"A", "B", "C", "D", "E", "F", "G"};
        Graph graph = new Graph(vertexNames);
        graph.buildEdge("A", "B");
        graph.buildEdge("B", "C");
        graph.buildEdge("B", "D");
        graph.buildEdge("D", "C");
        graph.buildEdge("A", "E");
        graph.buildEdge("C", "F");
        graph.buildEdge("E", "G");

//        graph.printMatrix();
//        graph.dfs(0);
        graph.bfs();
    }


}

图的遍历

算法在dfs和bfs的文章里有详细介绍,在此不过多赘述,直接上代码。

dfs

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/**
     * 深度优先遍历
     *
     * @param idx
     */
    public void dfs(int idx) {
        // 输出自己
        System.out.println(vertexNames.get(idx));
        // 标记已访问
        visited[idx] = true;
        // 访问第一个邻居节点
        for (int i = 0; i < vertexNames.size(); i++) {
            if (!visited[i] && matrix[idx][i] == 1)
                dfs(i);
        }
    }

bfs

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
     * 广度优先遍历
     *
     * @param
     */
    public void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        // 入队自己
        queue.add(0);

        while (!queue.isEmpty()) {
            int idx = queue.poll();
            // 输出
            System.out.println(vertexNames.get(idx));
            // 标记已访问
            visited[idx] = true;

            // 将邻居入队
            for (int i = 0; i < vertexNames.size(); i++) {
                if (!visited[i] && matrix[idx][i] == 1) {
                    // 入队
                    queue.add(i);
                }
            }


        }

    }