算法读书笔记之图的基本概念

图

概念定义

图是一种数学模型，它通过节点和边的组成映射现实生活中的关系。地图、互联网本身都可以用图来表示，地图两个建筑之间的距离，建筑就是节点，具体就是边.

图的分类

图分为四种：
    1.无向图
    2.有向图
    3.加权图
    4.加权有向图

图的表示方式

图是由vertex（顶点）和边(edge)相互连接而成.
一个V个顶点的图，一般用0-(V-1)个顶点表示图的顶点，与数组索引的表示方式保持一致.
度数表示的是一个顶点被多少条边连接
树本质上是一种无环连接图
图可以用密度这个概念来进行区分，密度低的就是稀疏图，反之就是稠密图.

邻接矩阵和邻接表:
    要表示一个图这种数据结构，要保证数据结构有足够的空间表示，同时时间复杂度、空间复杂度要尽可能的低.
    邻接矩阵:
        它可以将V个顶点的图表示位(0-V-1)^2的矩阵，并且每个元素通过bool类型来表示是否有连接关系.
        这样表示很清晰易懂，但是空间复杂度等于V^2,而且表示稠密图还好，如果表示稀疏图的话，就浪费了大量的空间.
    邻接表:
        邻接表的方法是通过数组的索引表示顶点的位置，通过数组的元素表示顶点连接的其他顶点.
    
    邻接表看起来比邻接矩阵更有优势，因为空间复杂度更低，而且可以表示平行矩阵
    Ps：平行矩阵代表是两个顶点可以有多个边

图的代码实现

邻接表的实现方式整体上更通用，所以使用邻接表来表示图.一个基本的图要实现以下的基本方法:

    public class AdjacencyListGraph implements Graph {

    private final int V;

    private int E;

    private LinkedList<Integer> adj[];

    public AdjacencyListGraph(int v) {
        this.V = v;
        this.E = 0;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    public AdjacencyListGraph(BufferedReader bufferedReader) throws IOException {
        this(Integer.parseInt(bufferedReader.readLine()));
        int E = Integer.parseInt(bufferedReader.readLine());
        for (int i = 0; i < E; i++) {
            int v = Integer.parseInt(bufferedReader.readLine());
            int w = Integer.parseInt(bufferedReader.readLine());
            this.addEdge(v, w);
        }
    }

    @Override
    public void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
        this.E++;
    }

    @Override
    public Iterable<Integer> adj(int v) {
        return adj[v];
    }

    @Override
    public int E() {
        return this.E;
    }

    @Override
    public int V() {
        return this.V;
    }

    @Override
    public String toString() {
        return "AdjacencyListGraph{" + "V=" + V + ", E=" + E + ", adj=" + Arrays.toString(adj) + '}';
    }