MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » 数据结构与算法-图的实现(邻接表、邻接矩阵、边的

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

www.MyException.Cn  网友分享于:2013-10-08  浏览:0次
数据结构与算法--图的实现(邻接表、邻接矩阵、边的数组)

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

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

邻接矩阵

对一个拥有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

文章评论

程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
那些争议最大的编程观点
那些争议最大的编程观点
 程序员的样子
程序员的样子
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
老程序员的下场
老程序员的下场
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
程序员应该关注的一些事儿
程序员应该关注的一些事儿
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
我是如何打败拖延症的
我是如何打败拖延症的
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
漫画:程序员的工作
漫画:程序员的工作
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
Java程序员必看电影
Java程序员必看电影
总结2014中国互联网十大段子
总结2014中国互联网十大段子
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
10个调试和排错的小建议
10个调试和排错的小建议
为什么程序员都是夜猫子
为什么程序员都是夜猫子
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
中美印日四国程序员比较
中美印日四国程序员比较
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
一个程序员的时间管理
一个程序员的时间管理
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
每天工作4小时的程序员
每天工作4小时的程序员
代码女神横空出世
代码女神横空出世
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
如何成为一名黑客
如何成为一名黑客
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
程序员必看的十大电影
程序员必看的十大电影
程序员和编码员之间的区别
程序员和编码员之间的区别
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
编程语言是女人
编程语言是女人
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
程序员都该阅读的书
程序员都该阅读的书
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有