美文网首页算法程序员数据结构和算法分析
数据结构与算法--图的实现(邻接表、邻接矩阵、边的数组)

数据结构与算法--图的实现(邻接表、邻接矩阵、边的数组)

作者: sunhaiyu | 来源:发表于2017-09-18 09:49 被阅读190次

    数据结构与算法--图的实现(邻接表、邻接矩阵、边的数组)

    应该用哪种数据结构实现图呢?主要有如下三种:

    邻接矩阵

    对一个拥有V个顶点的图,建立一个V*V的布尔数组,如果顶点i到j之间有边连接,则定义i行j列的元素值为true,否则为false,如果是带有权值的图,那么将true改成相应的权值,false改成一个不太可能出现的值比如Integer.MAX_VALUE。还可以专门用一个数组或者表,用来存放顶点信息,因为我们直接用0~N - 1的值代表了每个顶点,但这些数值具体指代了什么意思可以去顶点信息数组查找。不过邻接矩阵表示对于顶点数目很多(比如上百万)的图,N*N个值的空间是不能满足的。

    如上,左边的无向图可以转换成右边的邻接矩阵。顶点0~3的信息存在顶点信息数组里。由于这里用的是大话数据结构(C语言)中的图,0其实就是false,1就是true。顶点v0和v1有边相连,所以在矩阵中a[0][1]a[1][0]的值为true,而v1和v3之间没有边相连所以a[1][3]a[3][1]为false。仔细观察可以发现主对角线的值全是0,这是因为我们讨论的是简单图,暂时不考虑自环的情况。以主对角线为对称轴,矩阵左下a[i][j]和对应右上的a[j][i]值是一样的,这其实是一个对称矩阵。通过邻接矩阵,我们还可以获得一些其他信息。

    • 某个顶点i的度其实就是矩阵中a[i]那行中true的个数。
    • 与顶点i相邻的顶点就是矩阵中a[i]那行中所有值为true的列下标。

    邻接矩阵对于有向图也适用,只是矩阵不再是对称矩阵了。

    如图v0到v3有路径,所以a[0][3]为true,但是v3到v0不存在路径,所以a[3][0]为false。在有向图中我们说到度,一般区分出度和入度。这些信息也可以从矩阵中看出。

    • 顶点i的出度是矩阵a[i]那行中值为true的个数。
    • 顶点i的入度是矩阵a[][i]那列中值为true的个数。

    如果图的边是带有权值的(加权图),邻接矩阵可以使用一个二维int数组,如果两个顶点之间存在路径就用该边的权值代替原布尔数组中的true,如果两个顶点间没不存在路径就用一个不大可能出现的值代替false,由于权值可能为负数,我们选用Integer.MAX_VALUE

    图中的“无穷”符号,就是我们选用的Integer的最大值。主对角线依然全是0,因为某个顶点到自身并不需要花费什么代价(可以理解为权值为0)。

    虽然邻接矩阵在顶点数巨大的时候,所用空间令人发指,而且它还存了那么多没用的值——两个顶点不存在路径也存入了false或者一个不太可能出现的大值。但是无向图、有向图、加权无向图、加权有向图它都能实现,所以还是有必要动手敲一敲。

    package Chap7;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * 无向图 -- 邻接矩阵
     * @param <Item> 顶点类型
     */
    public class AdjMatrixGraph<Item> {
        private int vertexNum;
        private int edgeNum;
        // 邻接矩阵
        private boolean[][] adj;
        // 存放所有顶点信息
        private Item[] vertexInfo;
    
        // 初始化有V个顶点的图,还未加边
        public AdjMatrixGraph(Item[] vertexInfo) {
            this.vertexNum = vertexInfo.length;
            this.vertexInfo = vertexInfo;
    
            adj = new boolean[vertexNum][vertexNum];
        }
    
        public AdjMatrixGraph(Item[] vertexInfo, int[][] edges) {
            this(vertexInfo);
            for (int[] twoVertex : edges) {
                addEdge(twoVertex[0], twoVertex[1]);
            }
        }
    
        public AdjMatrixGraph(int vertexNum) {
            this.vertexNum = vertexNum;
            adj = new boolean[vertexNum][vertexNum];
        }
    
        public AdjMatrixGraph(int vertexNum,int[][] edges) {
            this(vertexNum);
            for (int[] twoVertex : edges) {
                addEdge(twoVertex[0], twoVertex[1]);
            }
        }
    
        public void addEdge(int i, int j) {
            // 对称矩阵,所以a[i][j] = a[j][i]
            adj[i][j] = true;
            adj[j][i] = true;
            edgeNum++;
        }
    
        public int vertexNum() {
            return vertexNum;
        }
    
        public int edgenum() {
            return edgeNum;
        }
    
        public Item getVertexInfo(int i) {
            return vertexInfo[i];
        }
        // 求某顶点的所有邻接顶点
        public List<Integer> adj(int i) {
            List<Integer> vertexAdj = new ArrayList<>();
            for (int j = 0; j < adj[i].length; j++) {
                if (adj[i][j]) {
                    vertexAdj.add(j);
                }
            }
            return vertexAdj;
        }
    
        // 某顶点的度
        public int degree(int i) {
            int degree = 0;
            for (int j = 0; j < adj[i].length; j++) {
                if (adj[i][j]) {
                   degree++;
                }
            }
            return degree;
        }
        // 求图的最大度数
        public int maxDegree() {
            int max = 0;
            for (int i = 0; i < vertexNum; i++) {
                if (degree(i) > max) {
                    max = degree(i);
                }
            }
            return max;
        }
        // 求图的平均度数
        // 边的条数 = 顶点度之和的一半  因为一条边对应两个顶点,这两个顶点的度数之和为2,所以边的数量是度之和的一半这样的关系
        // edgeNum = sum / 2, 则sum = 2 * edgeNum, 于是avgDegree = sum / vertexNum
        public double avgDegree() {
            return 2.0 * edgeNum / vertexNum;
        }
    
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(vertexNum).append("个顶点, ").append(edgeNum).append("条边。\n");
            for (int i = 0; i < vertexNum; i++) {
                sb.append(i).append(": ").append(adj(i)).append("\n");
            }
            return sb.toString();
        }
    
        public static void main(String[] args) {
            String[] vertexInfo = {"v0", "v1", "v2", "v3", "v4"};
            int[][] edges = {{0, 1}, {0, 2}, {0, 3},
                    {1, 3}, {1, 4},
                    {2, 4}};
            AdjMatrixGraph<String> graph = new AdjMatrixGraph<>(vertexInfo,edges);
    
            System.out.println("顶点3的度为" + graph.degree(3));
            System.out.println("顶点3的邻接点为"+graph.adj(3));
            System.out.println("该图的最大度数为" + graph.maxDegree());
            System.out.println("该图的平均度数为" + graph.avgDegree());
            System.out.println("邻接矩阵如下:\n" + graph);
        }
    }
    
    /* Outputs
    顶点3的度为2
    顶点3的邻接点为[0, 1]
    该图的最大度数为3
    该图的平均度数为2.4
    邻接矩阵如下:
    5个顶点, 6条边。
    0: [1, 2, 3]
    1: [0, 3, 4]
    2: [0, 4]
    3: [0, 1]
    4: [1, 2]
    
    */
    

    我们的实现中有两个构造器,其中一个接收一个参数,传入顶点信息数组,以顶点信息个数作为图的顶点数。另外一个还可以接收表示所有相邻顶点的二维数组,比如edges[0] = {0, 1}表示顶点0和顶点1相邻,由于addEdge方法中已经考虑了对称矩阵,所以这里传参的时候就用不着传入{0, 1}后再传入{1, 0}了,只要保证前一个数比后一个数小就可以避免重复添加。

    这里重点说一下求图的平均度数的方法avgDegree,我们有一个结论:图的边的条数 = 顶点度之和的一半,这是因为每一条边对应着两个顶点,而这两个顶点对于这条边,度之和为2。所以边的条数是所有顶点度之和的一半,即edgeNum = sum / 2,则sum = 2 * edgeNum, 于是avgDegree = sum / vertexNum

    邻接表

    邻接数组的缺点是所用空间太多,而且存放的信息很多是多余——顶点没有相邻也非得用一个false值或者不太可能出现的大值去填补数组中的位置,为何不直接留下相邻顶点就行了?比如上例中的a[0],可以从矩阵中看出与顶点0相邻的有顶点1、2、3

        0       1       2       3       4       5       
    0   false   true    true    true    false   false
    

    为什么不直接存储为a[0] = [1, 2, 3](就像上面打印的一样),这不是直观了很多嘛。由于每个顶点拥有的邻接点数目不同,使用数组实现就浪费空间了。所以存放某个顶点所有邻接点的容器,使用可变容量的表是个不错的选择,这里我就用链表了。回想树的孩子表示法,和这是一个道理,只是孩子表示法中存放的是结点对象(Node),这里存放的是用整数表示的顶点。邻接表不像邻接矩阵那样容量固定,如果某幅图要添加、删除某个顶点或某条边是相当方便的。所以在之后的实现中,如果没有特殊需求,将会一直使用邻接表。

    package Chap6;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.List;
    
    /**
     * 无向图
     * @param <Item>
     */
    public class UndiGraph<Item> {
        private int vertexNum;
        private int edgeNum;
        // 邻接表
        private List<List<Integer>> adj;
        // 顶点信息
        private List<Item> vertexInfo;
    
        public UndiGraph(List<Item> vertexInfo) {
            this.vertexInfo = vertexInfo;
            this.vertexNum = vertexInfo.size();
            adj = new ArrayList<>();
            for (int i = 0; i < vertexNum; i++) {
                adj.add(new LinkedList<>());
            }
        }
    
        public UndiGraph(List<Item> vertexInfo, int[][] edges) {
            this(vertexInfo);
            for (int[] twoVertex : edges) {
                addEdge(twoVertex[0], twoVertex[1]);
            }
        }
    
        public int vertexNum() {
            return vertexNum;
        }
    
        public int edgeNum() {
            return edgeNum;
        }
    
        public void addEdge(int i, int j) {
            adj.get(i).add(j);
            adj.get(j).add(i);
            edgeNum++;
        }
        // 不需要set,所以不用返回List,返回可迭代对象就够了
        public Iterable<Integer> adj(int i) {
            return adj.get(i);
        }
    
        public Item getVertexInfo(int i) {
            return vertexInfo.get(i);
        }
    
        public int degree(int i) {
            return adj.get(i).size();
        }
    
        public int maxDegree() {
            int max = 0;
            for (int i = 0;i < vertexNum;i++) {
                if (degree(i) > max) {
                    max = degree(i);
                }
            }
            return max;
        }
    
        public double avgDegree() {
            return 2.0 * edgeNum / vertexNum;
        }
    
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(vertexNum).append("个顶点, ").append(edgeNum).append("条边。\n");
            for (int i = 0; i < vertexNum; i++) {
                sb.append(i).append(": ").append(adj.get(i)).append("\n");
            }
            return sb.toString();
        }
    
        public static void main(String[] args) {
            List<String> vertexInfo = Arrays.asList("v0", "v1", "v2", "v3", "v4");
            int[][] edges = {{0, 1}, {0, 2}, {0, 3},
                    {1, 3}, {1, 4},
                    {2, 4}};
    
            UndiGraph<String> graph = new UndiGraph<>(vertexInfo, edges);
            
            System.out.println("顶点3的度为" + graph.degree(3));
            System.out.println("顶点3的邻接点为"+graph.adj(3));
            System.out.println("该图的最大度数为" + graph.maxDegree());
            System.out.println("该图的平均度数为" + graph.avgDegree());
            System.out.println("邻接表如下:\n" + graph);
        }
    
    }
    

    程序输出和上面邻接矩阵实现的输出完全一样。各个方法的实现其思想和邻接矩阵实现类似,比较简单就不解释了。

    顺便把有向图也用邻接表实现了。

    package Chap7;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.List;
    
    /**
     * 无向图
     *
     * @param <Item>
     */
    public class DiGraph<Item> {
        private int vertexNum;
        private int edgeNum;
        // 邻接表
        private List<List<Integer>> adj;
        // 顶点信息
        private List<Item> vertexInfo;
    
        public DiGraph(List<Item> vertexInfo) {
            this.vertexInfo = vertexInfo;
            this.vertexNum = vertexInfo.size();
            adj = new ArrayList<>();
            for (int i = 0; i < vertexNum; i++) {
                adj.add(new LinkedList<>());
            }
        }
    
        public DiGraph(List<Item> vertexInfo, int[][] edges) {
            this(vertexInfo);
            for (int[] twoVertex : edges) {
                addEdge(twoVertex[0], twoVertex[1]);
            }
        }
    
        public DiGraph(int vertexNum) {
            this.vertexNum = vertexNum;
            adj = new ArrayList<>();
            for (int i = 0; i < vertexNum; i++) {
                adj.add(new LinkedList<>());
            }
        }
    
        public DiGraph(int vertexNum, int[][] edges) {
            this(vertexNum);
            for (int[] twoVertex : edges) {
                addEdge(twoVertex[0], twoVertex[1]);
            }
        }
    
        public int vertexNum() {
            return vertexNum;
        }
    
        public int edgeNum() {
            return edgeNum;
        }
    
        public void addEdge(int i, int j) {
            adj.get(i).add(j);
            edgeNum++;
        }
    
        // 不需要set,所以不用返回List,返回可迭代对象就够了
        public Iterable<Integer> adj(int i) {
            return adj.get(i);
        }
    
        public DiGraph<Item> reverse() {
            DiGraph<Item> R = new DiGraph<>(vertexNum);
            for (int v = 0; v < vertexNum; v++) {
                for (int w: adj(v)) {
                    R.addEdge(w, v);
                }
            }
            return R;
        }
    
        public Item getVertexInfo(int i) {
            return vertexInfo.get(i);
        }
    
        public int degree(int i) {
            return adj.get(i).size();
        }
    
        public int maxDegree() {
            int max = 0;
            for (int i = 0; i < vertexNum; i++) {
                if (degree(i) > max) {
                    max = degree(i);
                }
            }
            return max;
        }
    
        public double avgDegree() {
            return 2.0 * edgeNum / vertexNum;
        }
    
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(vertexNum).append("个顶点, ").append(edgeNum).append("条边。\n");
            for (int i = 0; i < vertexNum; i++) {
                sb.append(i).append(": ").append(adj.get(i)).append("\n");
            }
            return sb.toString();
        }
    
        public static void main(String[] args) {
            List<String> vertexInfo = Arrays.asList("v0", "v1", "v2", "v3", "v4");
            int[][] edges = {{0, 1}, {0, 2}, {0, 3},
                    {1, 3}, {1, 4},
                    {2, 4}};
    
            DiGraph<String> graph = new DiGraph<>(vertexInfo, edges);
    
            System.out.println("顶点3的度为" + graph.degree(3));
            System.out.println("顶点3的邻接点为" + graph.adj(3));
            System.out.println("该图的最大度数为" + graph.maxDegree());
            System.out.println("该图的平均度数为" + graph.avgDegree());
            System.out.println("邻接表如下:\n" + graph);
        }
    
    }
    

    addEdge方法少了一行,有向图嘛,边也是有方向的,i -> j有边不一定j -> i有边。另外新增了一个反向图的reverse方法,改变了所有边的方向,并返回原图的反向图。代码中主要做的是对每个顶点v,以及v的所有邻接顶点w,本来是v -> w的方向,现在新图中调用addEdge(w, v),将方向变成w -> v,实现反向。

    至于其他方法,和无向图完全一样。

    边的数组

    这种方法实现起来很简单,顾名思义它更关注,我们可以用一个Edge来抽象边,它有两个int成员表示该边的两个顶点,如果是加权图,再多一个int型的weight成员就行了。将所有边存放到一个列表List<Edge>中,就是我们所说的边的数组了。

    package Chap7;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class EdgeGraph<Item> {
    
        public static class Edge {
            private int either;
            private int other;
    
            public int either() {
                return either;
            }
    
            public int other() {
                return other;
            }
    
            public Edge(int either, int other) {
                this.either = either;
                this.other = other;
            }
    
            @Override
            public String toString() {
                return "Edge{" +
                        "either=" + either +
                        ", other=" + other +
                        '}';
            }
        }
    
        private int vertexNum;
        private int edgeNum;
        private List<Item> vertexInfo;
        private List<Edge> edges;
    
        public EdgeGraph(List<Item> vertexInfo) {
            this.edges = new ArrayList<>();
            this.vertexInfo = vertexInfo;
            this.vertexNum = vertexInfo.size();
        }
    
        public EdgeGraph(List<Item> vertexInfo, int[][] edges) {
            this(vertexInfo);
            for (int[] twoVertex : edges) {
                addEdge(twoVertex[0], twoVertex[1]);
            }
        }
    
        public EdgeGraph(int vertexNum) {
            this.edges = new ArrayList<>();
            this.vertexNum = vertexNum;
        }
    
        public EdgeGraph(int vertexNum, int[][] edges) {
            this(vertexNum);
            for (int[] twoVertex : edges) {
                addEdge(twoVertex[0], twoVertex[1]);
            }
        }
    
        public void addEdge(int i, int j) {
            Edge edge = new Edge(i, j);
            this.edges.add(edge);
            edgeNum++;
        }
    
        public List<Integer> adj(int i) {
            List<Integer> adj = new ArrayList<>();
    
            for (Edge edge : edges) {
                if (edge.either == i) {
                    adj.add(edge.other);
                } else if (edge.other == i) {
                    adj.add(edge.either);
                }
            }
            return adj;
        }
    
        public int degree(int i) {
            return adj(i).size();
        }
    
        public int maxDegree() {
            int max = 0;
            for (int i = 0; i < vertexNum; i++) {
                if (degree(i) > max) {
                    max = degree(i);
                }
            }
            return max;
        }
    
        public double avgDegree() {
            return 2.0 * edgeNum / vertexNum;
        }
    
        public Item getVertexInfo(int i) {
            return vertexInfo.get(i);
        }
    
        public int vertexNum() {
            return vertexNum;
        }
    
        public int edgeNum() {
            return edgeNum;
        }
    
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(vertexNum).append("个顶点, ").append(edgeNum).append("条边。\n");
            for (int i = 0; i < vertexNum; i++) {
                sb.append(i).append(": ").append(adj(i)).append("\n");
            }
            return sb.toString();
        }
    
        public static void main(String[] args) {
            List<String> vertexInfo = Arrays.asList("v0", "v1", "v2", "v3", "v4");
            int[][] edges = {{0, 1}, {0, 2}, {0, 3},
                    {1, 3}, {1, 4},
                    {2, 4}};
            EdgeGraph<String> graph = new EdgeGraph<>(vertexInfo, edges);
            System.out.println("顶点3的度为" + graph.degree(3));
            System.out.println("顶点3的邻接点为" + graph.adj(3));
            System.out.println("该图的最大度数为" + graph.maxDegree());
            System.out.println("该图的平均度数为" + graph.avgDegree());
            System.out.println("邻接表如下:\n" + graph);
        }
    }
    

    自然输出和前面都一样。

    只说addEdge(int i, int j)方法和adj(int i)方法。前者给图中两个顶点添加一条边,传入两个顶点,紧接着就new一个对应Edge,再将其存入边的列表即可。后者获取某个顶点所有邻接点,遍历边的列表,因为不知道边中哪个顶点和i相等,所以需要判断一下,只要有一个顶点和i相等,就将另一个存入待返回的列表中。

    现在也知道了该实现有个缺陷:要知道某个顶点的所有邻接点,必须遍历整个边数组,效率不是很高。如果我们经常进行对顶点的操作,可以说获取某顶点所有邻接点是非常频繁的,边的数组不太适合经常对图的顶点进行操作的场合,更适合经常对边进行依次操作的场合。

    在后面加权图的实现中,我们会用到边的数组的思想,因为权值在边上嘛,邻接矩阵实现起倒是简单,但是对于邻接表来说,由上面可以知道它定义为List<List<Integer>>,内层列表存放的是顶点的所有邻接点,那么权值存在哪里?这时候我们就需要一个Edge类了。差不多像下面这样。

    public class Edge {
        private int either;
        private int other;
        private int weight;
    }
    

    邻接表随之也变成了List<List<Edge>>。这里只是稍微提一下,以后学到加权图的时候再具体来说。


    by @sunhaiyu

    2017.9.17

    相关文章

      网友评论

        本文标题:数据结构与算法--图的实现(邻接表、邻接矩阵、边的数组)

        本文链接:https://www.haomeiwen.com/subject/njmvsxtx.html