learning_record_doc/图的存储结构之邻接矩阵和邻接表（Java 实现）.md at master

dashan/learning_record_doc

Fork 0

dashan a7a5aef547 doc up

2022-12-31 17:33:47 +08:00

17 KiB

Raw Permalink Blame History

本文由简悦 SimpRead 转码，原文地址 www.suibibk.com

一、图的存储结构讨论对于线性表来说，是一对一的关系，所以用数组或者链表均可以简单存放。

一、图的存储结构讨论

对于线性表来说，是一对一的关系，所以用数组或者链表均可以简单存放。
对于树结构是一对多的关系，所以我们要将数组和链表的特性结合在一起才能更好的存放。
对于图来说，是多对多的情况，另外图上的任意一个顶点都可以被看做是第一个顶点，任一顶点的邻接点之间也不存在次序关系

如下图：实际是一个图结构，只不过顶点位置不同。

由于图的结构复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在内存中的物理位置来表示元素之间的关系，也就是说，图不可能用简单的顺序存储结构来表示。内存物理位置是线性的，图的元素关系是平面的。

虽然我们可以向树结构中说到的那样使用多重链表，但是我们需要先确定最大的度，然后按照这个度最大的顶点设计结点结构，若是每个顶点的度数相差较大，就会造成大量的存储单元浪费。

二、图的存储结构（1）—- 邻接矩阵

考虑到图是由顶点和边（弧）两部分组成的，合在一起是比较困难的，那就很自然的考虑到分为两个结构来分别存储

顶点因为不区分大小，主次，所以用一个一维数组来存储时不错的选择。

而边或弧由于是顶点与顶点之间的关系，所以我们最好使用二维数组来存储，图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

1、无向图

其中1表示两个顶点之间存在关系，0表示无关，不存在顶点间的边。

对称矩阵：就是 n 阶矩阵满足 a[i][j]=a[j][i](0<=i,j<=n）。即从矩阵的左上角到右下角的主对角线为轴，右上角的源与左下角相对应的元都是相等的。

根据这个矩阵，我们可以很容易的知道图中的信息。

1. 我们要判定容易两顶点是否有边无边就非常容易了。
1. 我们要知道某个顶点的度，其实就是这个顶点 vi 在邻接矩阵中第 i 行（或第 i 列）的元素之和。比如上图顶点 v1 的度就是 1+0+1+0=2
1. 求顶点 vi 的所有邻接点就是将矩阵第 i 行元素扫描一遍，arc[i][j] 为 1 就是邻接点

2、有向图

对于上面的无向图，二维对称矩阵似乎浪费了一半的空间。若是存放有向图，会更大程度利用起来空间

其中顶点数组是一样的和无向图，弧数组也是一个矩阵，但因为是有向图，所以这个矩阵并不对称：例如 v1->v0 有弧，arc[1][0]=1, 而 v0 到 v1 没有弧，所以 arc[0][1]=0。

另外有向图，要考虑入度和出度，顶点 v1 的入度为 1，正好是第 v1 列的各数之和，顶点 v1 的出度为 2，正好是第 v2 行的各数之和

3、网

每条边上带有权的有向图就叫做网

这里‘∞’表示一个计算机允许的，大于所有边上权值的值

4、Java 实现无向图、有向图、网的邻接矩阵创建

public class G2 {
    public static void main(String[] args) {
        //1、无向图
        //定点数组vertex
        String[] v1 = new String[]{"V0","V1","V2","V3"};
        //矩阵表示边的关系edge 其中1表示两个顶点之间存在关系，0表示无关，不存在顶点间的边。
        int[][] e1 = new int[][] {
            {0,1,1,1},
            {1,0,1,0},
            {1,1,0,1},
            {1,0,1,0}
        };
        System.out.println("输出无向图：");
        for (int i = 0; i < v1.length; i++) {
            System.out.print(v1[i]+"\t");
        }
        System.out.println();
        for (int i = 0; i < v1.length; i++) {
            for (int j = 0; j < v1.length; j++) {
                System.out.print(e1[i][j]+"\t");
            }
            System.out.println();
        }
        System.out.println("--------------------");
        //2、有向图
        String[] v2 =new String[]{"V0","V1","V2","V3"};
        int[][] e2 = new int[][] {
            {0,0,0,1},
            {1,0,1,0},//V1的出度为2
            {1,1,0,0},//V2的出度为2
            {0,0,0,0}
            //V1的入度为1
        };
        System.out.println("输出有向图：");
        for (int i = 0; i < v2.length; i++) {
            System.out.print(v2[i]+"\t");
        }
        System.out.println();
        for (int i = 0; i < v2.length; i++) {
            for (int j = 0; j < v2.length; j++) {
                System.out.print(e2[i][j]+"\t");
            }
            System.out.println();
        }
        System.out.println("--------------------");
        //3、网，每条边上带有权的图就叫做网
        String[] v3 =new String[]{"V0","V1","V2","V3","V4"};
        //m表示不可达
        int m=65535;
        int[][] e3 = new int[][] {
            {0,m,m,m,6},
            {9,0,3,m,m},
            {2,m,0,5,m},
            {m,m,m,0,1},
            {m,m,m,m,0}
        };
        System.out.println("输出网：");
        for (int i = 0; i < v3.length; i++) {
            System.out.print(v3[i]+"\t");
        }
        System.out.println();
        for (int i = 0; i < v3.length; i++) {
            for (int j = 0; j < v3.length; j++) {
                System.out.print(e3[i][j]+"\t");
            }
            System.out.println();
        }
    }
}

代码中的图跟上面说的图一一对应，运行结果如下：

输出无向图：
V0    V1    V2    V3    
0    1    1    1    
1    0    1    0    
1    1    0    1    
1    0    1    0    
--------------------
输出有向图：
V0    V1    V2    V3    
0    0    0    1    
1    0    1    0    
1    1    0    0    
0    0    0    0    
--------------------
输出网：
V0    V1    V2    V3    V4    
0    65535    65535    65535    6    
9    0    3    65535    65535    
2    65535    0    5    65535    
65535    65535    65535    0    1    
65535    65535    65535    65535    0

三、图的存储结构（2）—- 邻接表

上面的邻接矩阵是一种不错的图存储结构，便于理解，但是当我们的边数相对于顶点较少的图，这种结构是存在对存储空间的极大的浪费。

我们可以考虑使用链表来动态分配空间，避免使用数组一次分配而造成空间浪费问题。

同树中，孩子表示法，我们将结点存放入数组，对结点的孩子进行链式存储，不管有多少孩子，都不会存在空间浪费。这种思路也适用于图的存储。我们把这种数组与链表相结合的存储方法称为邻接表。

邻接表处理办法

1. 图中顶点用一个一维数组。当然，顶点也可以用单链表来存储，不过数组可以较容易的读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息
1. 图中每个顶点 vi 的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点 vi 的边表，有向图则称为顶点 vi 作为弧尾的出边表
1、无向图

这样的结构，对于我们要获得图的相关信息也是很方便。比如：
我们要获取某个顶点的度，就要去查找这个顶点的边表中结点的个数。
我们要判断 vi 到 vj 是否存在边，只需要测试 vi 的边表链表中是否存在结点 vj 的下标 j 即可。
我们若是要获取顶点的所有邻接点，就是对此顶点的边表进行遍历。

2、有向图

有向图由于有方向，我们是以顶点为弧尾来存储边表的，这样很容易就可以得到每个顶点的出度。但是由于有时也需要确定顶点的入度或以顶点作为弧头的弧，我们可以建立一个有向图的逆邻接表，即对每个顶点 vi 都建立一个链接为 vi 为弧头的表。

3、带权值的网

们可以在边表结点定义中再增加一个 weight 数据域，存储权值信息即可。

4、Java 实现无向图、有向图、网的邻接链表创建

首先我们看一下《算法导论》中关于图的邻接表的定义：图 G=(V,E) 的邻接表表示有一个包含 |V| 个列表的数组 Adj 所组成，其中每个列表对应于 V 中的一个顶点，对于每一个 u∈V，邻接表 Adj[u] 包含所有满足条件（u，v）∈E 的顶点 v，亦即，Adj[u] 包含图 G 中所有和顶点 u 相邻的顶点。（或者他也可能指向这些顶点的指针），每个邻接表中的顶点一般以任意的顺序存储。（注意一下这句话！）

这里的实现方法有多重多样，下面是按我的思路实现的代码示例，一般都会有两个对象，一个是顶点，如下：

//定义定点
class Vertex{
    String value;//顶点的值
    Edge firstEdge;//第一条边
    public Vertex(String value, Edge firstEdge) {
        super();
        this.value = value;
        this.firstEdge = firstEdge;
    }
}

这里我们可已将顶点放在一个数组中，然后每个顶点都从第一条边衍生出去。当然可以按具体需求多加属性，比如顶点的出度也可以当做一个属性什么的，我这里就不加了！

然后定义边的对象：

class Edge{
    String value;//该边对应的顶点
    int weight;//权重，无向图，有向图权重为0
    Edge next;//下一个边
    /**
     * 构建一条边 weight未0表示无向图或者有向图 不为0表示网
     * @param value
     * @param weight
     * @param next
     */
    public Edge(String value, int weight, Edge next) {
        super();
        this.value = value;
        this.weight = weight;
        this.next = next;
    }
}

我这里因为要举无向图，有向图，网的例子，所以这个边就直接有权重，但是无向图，有向图的权重为 0。

然后下面是完整的代码，跟上面三个示例图对应：

/**
 * 邻接链表
 * @author suibibk.com
 */
public class Graph {
    public int num;//顶点个数
    //顶点
    List<Vertex> vertexs;
    public Graph(int num) {
        this.num = num;
        //初始化图的大小
        vertexs = new ArrayList<Vertex>(num);
    }
    //插入顶点
    public void addVertex(String value) {
        vertexs.add(new Vertex(value, null));
    }
    //获取顶点
    public Vertex getVertex(String value) {
        for (int i = 0; i < num; i++) {
            if(vertexs.get(i).value.equals(value)) {
                return vertexs.get(i);
            }
        }
        return null;
    }
    /**
     * 添加无向图的边
     * @param vertex1 第一个顶点
     * @param vertex2 第二个顶点
     */
    public void addUndigraphEdge(String vertex1,String vertex2) {
        //因为是无向图，所以就直接加入
        addEdgeByVertex(vertex1,vertex2,0);
        addEdgeByVertex(vertex2,vertex1,0);
    }
    /**
     * 添加有向图的边
     * @param start 开始节点
     * @param end 结束节点
     */
    public void addDigraphEdge(String start,String end) {
        //因为是有向图，所以只有一条边
        addEdgeByVertex(start,end,0);
    }
    /**
     * 添加网的边
     * @param start 开始节点
     * @param end 结束节点
     * @param weight 权重
     */
    public void addWebEdge(String start,String end,int weight) {
        //网就是有向图有权重
        addEdgeByVertex(start,end,weight);
    }
    /**
     * 添加一条由start-->end的边
     * @param start
     * @param end
     * @param weight 权重未0表示无向图或者有向图，部位0表示网
     */
    private void addEdgeByVertex(String start,String end,int weight) {
        //1、找到第一个顶点
        Vertex v1 = this.getVertex(start);
        //2、检查这条边是否已经存在，已经存在就直接报错
        Edge firstEdge = v1.firstEdge;
        while(firstEdge!=null) {
            //获取这个边
            String value = firstEdge.value;
            if(end.equals(value)) {
                System.out.println("边"+start+"-->"+end+"已经加入，不可以再加入");
                return;
            }else {
                Edge next = firstEdge.next;
                firstEdge=next;
            }
        }
        //到这里就可以加入这一条边了
        firstEdge = v1.firstEdge;
        //到这里就可以加入这条边
        if(firstEdge==null) {
            firstEdge = new Edge(end,weight, null);
            v1.firstEdge=firstEdge;
        }else {
            //当前节点变为第一个节点
            Edge nowEdge = new Edge(end,weight, null);
            v1.firstEdge=nowEdge;
            nowEdge.next=firstEdge;
        }
    }
    /**
     * 输出图
     */
    public void print() {
        for (int i = 0; i <num; i++) {
            Vertex vertex = vertexs.get(i);
            System.out.print(vertex.value+"-->");
            Edge edge = vertex.firstEdge;
            while(edge!=null) {
                System.out.print(edge.value+"["+edge.weight+"]");
                Edge next = edge.next;
                edge=next;
                if(next!=null) {
                    System.out.print("-->");
                }else {
                    System.out.print("-->∧");
                }
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        //测试无向图
        Graph g = new Graph(4);
        g.addVertex("V0");
        g.addVertex("V1");
        g.addVertex("V2");
        g.addVertex("V3");
        //插入边:无向图
        g.addUndigraphEdge("V0", "V1");
        g.addUndigraphEdge("V1", "V2");
        g.addUndigraphEdge("V2", "V3");
        g.addUndigraphEdge("V3", "V0");
        g.addUndigraphEdge("V2", "V0");
        System.out.println("输出无向图：");
        g.print();
        System.out.println("------------");
        Graph g1 = new Graph(4);
        g1.addVertex("V0");
        g1.addVertex("V1");
        g1.addVertex("V2");
        g1.addVertex("V3");
        //插入边:有向图
        g1.addDigraphEdge("V0", "V3");
        g1.addDigraphEdge("V1", "V0");
        g1.addDigraphEdge("V1", "V2");
        g1.addDigraphEdge("V2", "V0");
        g1.addDigraphEdge("V2", "V1");
        System.out.println("输出有向图：");
        g1.print();
        System.out.println("----------");
        Graph g2 = new Graph(4);
        g2.addVertex("V0");
        g2.addVertex("V1");
        g2.addVertex("V2");
        g2.addVertex("V3");
        //插入边:有向图
        g2.addWebEdge("V0", "V4",6);
        g2.addWebEdge("V1", "V0",9);
        g2.addWebEdge("V1", "V2",3);
        g2.addWebEdge("V2", "V0",2);
        g2.addWebEdge("V2", "V3",5);
        g2.addWebEdge("V3", "V4",1);
        System.out.println("输出带权值的网：");
        g2.print();
    }
}
//定义定点
class Vertex{
    String value;//顶点的值
    Edge firstEdge;//第一条边
    public Vertex(String value, Edge firstEdge) {
        super();
        this.value = value;
        this.firstEdge = firstEdge;
    }
}
class Edge{
    String value;//该边对应的顶点
    int weight;//权重，无向图，有向图权重为0
    Edge next;//下一个边
    /**
     * 构建一条边 weight未0表示无向图或者有向图 不为0表示网
     * @param value
     * @param weight
     * @param next
     */
    public Edge(String value, int weight, Edge next) {
        super();
        this.value = value;
        this.weight = weight;
        this.next = next;
    }
}

Copy 即可运行，结果如下：

输出无向图：
V0-->V2[0]-->V3[0]-->V1[0]-->∧
V1-->V2[0]-->V0[0]-->∧
V2-->V0[0]-->V3[0]-->V1[0]-->∧
V3-->V0[0]-->V2[0]-->∧
------------
输出有向图：
V0-->V3[0]-->∧
V1-->V2[0]-->V0[0]-->∧
V2-->V1[0]-->V0[0]-->∧
V3-->
----------
输出带权值的网：
V0-->V4[6]-->∧
V1-->V2[3]-->V0[9]-->∧
V2-->V3[5]-->V0[2]-->∧
V3-->V4[1]-->∧

上面把添加变的操作抽取成了公共的方法！

完成！

17 KiB Raw Permalink Blame History Unescape Escape

一、图的存储结构讨论

二、图的存储结构（1）—- 邻接矩阵

1、无向图

2、有向图

3、网

4、Java 实现无向图、有向图、网的邻接矩阵创建

三、图的存储结构（2）—- 邻接表

邻接表处理办法

1、无向图

2、有向图

3、带权值的网

4、Java 实现无向图、有向图、网的邻接链表创建

17 KiB

Raw Permalink Blame History