DS09.1:图的概念与存储结构

图的基本概念

图是由顶点的集合和顶点之间的边的集合组成的，通常表示为G(V, E)。其中G表示一个图，V是图G中的顶点的集合，E是图G中边的集合。

图按照边是否有方向和边是否带权重可以分为四类，即有向无权图、有向有权图、无向无权图、无向有权图。

无向图的边通常使用“()”表示，如A与B之间的边就是(A, B)或(B, A)

有向边则通常使用“<>”表示，如A到B的边就是<A, B>，这时边有方向性，字母不能够替换。

图按照边的多少分为稀疏图和稠密图。若任意两个顶点之间都存在边叫完全图（无向完全图有n(n-1)/2条边）。没有自环边、没有平行边的图称为简单图。

无向图顶点的边数叫做“度”，有向图分为出度和入度

连通图

在无向图G中，如果对于图中任意两个顶点都是连通的，则称G为连通图。

无向图中极大连通子图称为连通分量。其实就是有几个可以互相连通的块，类似于树结构中定义的森林。

连通图的生成树是一个极小的连通子图，其含有图中全部的V个节点，但只有足以构成一棵树的v-1条边

图的存储方法与实现

邻接矩阵

在邻接矩阵实现中，由行和列都表示顶点，由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连。如果是无权图的话相连为1，不相连为0，如果是有权图的话该处的数组则为边上所带的权重。

public class AdjMatrix {
    private int V;  // 顶点集合
    private int E;  // 边集合
    private int[][] adj;    // 邻接矩阵
    
    // 读入数据，构建图
    // 先读入顶点数V，再读入边数E，最后读入边的信息
    public AdjMatrix(String filename) {
        File file = new File(filename);
        try(Scanner scanner = new Scanner(file)) {
            V = scanner.nextInt();
            if(V < 0)
                throw new IllegalArgumentException("V must be non-negative");
            E = scanner.nextInt();
            if(E < 0)
                throw new IllegalArgumentException("E must be non-negative");
            adj = new int[V][V];

            for (int i=0; i<E; i++) {
                int a = scanner.nextInt();
                validateVertex(a);
                int b = scanner.nextInt();
                validateVertex(b);
                if(a == b)
                    throw new IllegalArgumentException("Self Loop is Detected");
                if(adj[a][b] == 1)
                    throw new IllegalArgumentException("Parallel Edge is Detected");
                adj[a][b] = 1;
                adj[b][a] = 1;
            }
        }
        catch (IOException e) {
            e.printStackTrace();
        }
    }

    // 判断输入数据是否合理
    private void validateVertex(int v) {
        if(v < 0 || v >=V)
            throw new IllegalArgumentException("Vertex" + v + "is valid");
    }

    // 输出顶点数
    public int getVertex() {
        return V;
    }

    // 输出边数
    public int getEdge() {
        return E;
    }

    // 判断v1与v2之间存不存在边
    public boolean hasEdge(int v1, int v2) {
        validateVertex(v1);
        validateVertex(v2);
        return adj[v1][v2] == 1;
    }

    // 获取所有邻接的顶点
    public ArrayList<Integer> adj(int v) {
        validateVertex(v);
        ArrayList<Integer> res = new ArrayList<>();
        for (int i=0; i<V; i++) {
            if(adj[v][i] == 1)
                res.add(i);
        }
        return res;
    }

    // 获取顶点v的度
    public int degree(int v) {
        return adj(v).size();
    }
}

邻接表

在邻接列表实现中，每一个顶点会存储一个从它这里开始的边的列表。这个“列表”的具体实现的数据结构可以是链表，也可以是红黑树与哈希表等等。

public class AdjList {
    private int V;  // 顶点集合
    private int E;  // 边集合
    private LinkedList<Integer>[] adj;  // 邻接表

    // 读入数据，构建图
    // 先读入顶点数V，再读入边数E，最后读入边的信息
    public AdjList(String filename) {
        File file = new File(filename);
        try(Scanner scanner = new Scanner(file)) {
            V = scanner.nextInt();
            if(V < 0)
                throw new IllegalArgumentException("V must be non-negative");
            E = scanner.nextInt();
            if(E < 0)
                throw new IllegalArgumentException("E must be non-negative");
            adj = new LinkedList[V];

            for (int i=0; i<V; i++) {
                adj[i] = new LinkedList<>();
            }

            for (int i=0; i<E; i++) {
                int a = scanner.nextInt();
                validateVertex(a);
                int b = scanner.nextInt();
                validateVertex(b);
                if(a == b)
                    throw new IllegalArgumentException("Self Loop is Detected");
                if(adj[a].contains(b))
                    throw new IllegalArgumentException("Parallel Edge is Detected");
                adj[a].add(b);
                adj[b].add(a);
            }
        }
        catch (IOException e) {
            e.printStackTrace();
        }
    }

    // 判断输入数据是否合理
    private void validateVertex(int v) {
        if(v < 0 || v >=V)
            throw new IllegalArgumentException("Vertex" + v + "is valid");
    }

    // 输出顶点数
    public int getVertex() {
        return V;
    }

    // 输出边数
    public int getEdge() {
        return E;
    }

    // 判断v1与v2之间存不存在边
    public boolean hasEdge(int v1, int v2) {
        validateVertex(v1);
        validateVertex(v2);
        return adj[v1].contains(v2);
    }

    // 获取所有邻接的顶点
    public LinkedList<Integer> adj(int v) {
        validateVertex(v);
        return adj[v];
    }

    // 获取顶点v的度
    public int degree(int v) {
        return adj(v).size();
    }
}

复杂度分析

操作	邻接矩阵	邻接表（链表）	邻接表（红黑树）
空间复杂度	O(V^2)	O(V+E)	O(V+E)
建图	O(E)	O(E*V)	O(E*log V)
查看是否相邻	O(1)	O(degree(V))，最差时O(V)	O(log V)
返回该点的所有相邻节点	O(V)	O(degree(V))，最差时O(V)	O(degree(V))，最差时O(V)

参考

https://www.jianshu.com/p/bce71b2bdbc8

Donate