图的邻接矩阵的实现

淩亂°似流年 2022-06-04 03:44 202阅读 0赞

对于图的一些基本概率和术语的内容汗牛充栋，故本文不会做过多解释。仅仅总结下笔者学习图的邻接矩阵的相关知识

#### 邻接矩阵的实现原理 ####

邻接矩阵(adjacency matrix)是图ADT最基本的实现方式，使用二维数组A\[n\]\[n\]来表示由n个顶点构成的图。二维数组中的A\[i\]\[j\]表示一条从来顶点i为起点到顶点j的弧。

![这里写图片描述][SouthEast]

对于无权图，存在（不存在）从顶点u到v的边，当且仅当A\[u\]\[v\] =1（0）。上图a,b即为无向图和有向图的邻接矩阵实例。图c所示，矩阵各单元可从布尔型改为整型或浮点型，记录所对应边的权重。对于不存在的边，通常统一取值null。

#### 节点的实现 ####

public class Node<T> {
        private T data; // 存储的数据
        private int outDegree; // 出度
        private int inDegree; // 入度
        //如下四个属性用与遍历中
        private int status = 0;  //状态 0 undiscovered  1 discovered   2 visited   
        //status应该使用枚举的，这里笔者偷懒了
        private int parent = -1;
        private int dTime = -1; //开始遍历的时间
        private int fTime = -1; //结束遍历的时间
    
       public Node(T t) {
            this.data = t;
            this.outDegree = 0;
            this.inDegree = 0;
        }
    
        protected void addInDegree() {
            this.inDegree++;
        }
    
        protected void addOutDegree() {
            this.outDegree++;
        }
    
        protected void delInDegree() {
            this.inDegree--;
        }
    
        protected void delOutDegree() {
            this.outDegree--;
        }
    //节约篇幅，省略getter setter...
    }

#### 弧的实现 ####

public class Edge<T> {
        private T data; // 弧数据
        private int weight; // 权值
        private int type;  
        //应该使用枚举的，这里笔者偷懒了
        //弧类型：0 CROSS 跨边  1 TREE（支撑树） 
        //2 BACKWARD(该弧的起点和终点在支撑树中存在终点到起点的路径) 
        //3 FORWARD (该弧的起点和终点在支撑树中存在其他路径依然可以从起点到终点)
    
        public Edge(T data) {
            this(data, 1);
        }
        public Edge(T data, int weight) {
            this.data = data;
            this.weight = weight;
        }
        //节约篇幅，省略getter setter...
    
    }

#### **邻接矩阵的存储实现** ####

public class AdjacencyMatrix {
    
      private Edge[][] nodeGraphs;
      private Node[] allNodes;
      private Integer size=0;
      private int DEFAULT_CAPACITY = 10;
    
      //创建默认长度的邻接矩阵
      public AdjacencyMatrix() {
    
          nodeGraphs = new Edge[DEFAULT_CAPACITY][DEFAULT_CAPACITY];
          allNodes = new Node[DEFAULT_CAPACITY];
      }
    
      //创建指定长度的邻接矩阵
      public AdjacencyMatrix(int numbers) {
    
          nodeGraphs = new Edge[numbers][numbers];
          allNodes = new Node[numbers];
      }
    
      //添加新节点，并返回新节点索引
      public int addNode(Node node) {
          int returnIndex = size;
          //判断当前数组的容量，来决定是否扩容
          ensureCapacityInternal(size + 1);
          allNodes[size++] = node;
          return returnIndex;
      }
    
      private void ensureCapacityInternal(int minCapacity) {
    
          minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
          ensureExplicitCapacity(minCapacity);
      }
    
      private void ensureExplicitCapacity(int minCapacity) {
        //判断是否需要扩容
        if(minCapacity - allNodes.length > 0) {
            grow(minCapacity);
        }
      }
    
      private void grow(int minCapacity) {
    
          int oldCapacity = allNodes.length;
          //新数组的长度为(原数组长度+原数组长度/2)
          //右移n为即为除2的n次方
          int newCapacity = oldCapacity + (oldCapacity >> 1);
          if (newCapacity - minCapacity < 0)
              newCapacity = minCapacity;
          //将原数组复制到扩容后的数组中
          allNodes = Arrays.copyOf(allNodes, newCapacity);
          nodeGraphs = Arrays.copyOf(nodeGraphs, newCapacity);
            //对于二维中的数组执行扩容
            for(int i=0;i<nodeGraphs.length;i++) {
                if(nodeGraphs[i] != null) {
                  nodeGraphs[i] = Arrays.copyOf(nodeGraphs[i], newCapacity);
                }else {
                  nodeGraphs[i] = new Edge[newCapacity];
                }
          }
      }
    
      //获取出度
      public int getInDeep(int index) {
          if(allNodes[index] == null) {
              return -1;
          }
          return allNodes[index].getInDegree();
      }
    
      //获取入度
      public int getOutDeep(int index) {
          if(allNodes[index] == null) {
              return -1;
          }
          return allNodes[index].getOutDegree();
      }
    
      //删除第index边及其相关边
      public Node removeNode(int deleteIndex) {
    
          Node node = allNodes[deleteIndex];
          if(node == null) {
              throw new RuntimeException("节点为空");
          }
          //先删除节点
          allNodes[deleteIndex] = null;
          //删除所有相关边
          for(int i=0;i<size;i++) {
    
              //该节点作为一条弧的弧头(即指向该节点的弧)
              if(nodeGraphs[deleteIndex][i] != null) {
                  nodeGraphs[deleteIndex][i] = null;
                  allNodes[i].delInDegree();
              }
    
              //该节点作为一条弧的弧尾(即该节点出去的弧)
              if(nodeGraphs[i][deleteIndex] != null) {
                  nodeGraphs[i][deleteIndex] = null;
                  allNodes[i].delOutDegree();
              }
          }
          return node;
      }
    
      //设置一个从节点row为起点到col的弧
      public void setMatrix(int row, int col, Edge val) {
          nodeGraphs[row][col] = val;
          allNodes[row].addOutDegree();
          allNodes[col].addInDegree();
      }
    
      //重置状态
      public void reload() {
          for(int i=0;i<size;i++) {
              allNodes[i].setStatus(0);
              allNodes[i].setParent(-1);
          }
      }
    }

#### 性能 ####

**时间性能：**

按照代码的实现方式，各顶点的编号可直接转换为其在邻接矩阵中对应的顶点，从而使得图中所有的静态操作接口，均只需O(1)时间。弧的静态和动态操作也仅需O(1)时间，其代价是邻接矩阵的空间冗余。  
邻接矩阵的不足主要体现在，顶点的动态操作接口均十分耗时。为了插入新的顶点，顶点集向量allNodes\[\]需要添加一个元素；弧集向量nodeGraphs\[\]\[\]也需要增加一行，且每行都需要添加一个元素。顶点删除操作，亦与此类似。不难看出，这些恰恰也是数组结构固有的不足。  
但在通常的算法中，顶点的动态操作远少于其它操作。而且，即便计入向量扩容的代价，就分摊意义而言，单次操作的耗时亦不过O(n)

**空间性能：**

上述实现方式所用空间，主要消耗于邻接矩阵，亦即其中的二维弧集向量nodeGraphs\[\]\[\]。每个Edge对象虽需记录多项信息，但总体不过常数。根据我们扩容的算法根据其数组长度始终不低于50%，故空间总量渐进地不超过O(n\*n)= O(n^2)

当然，对于无向图而言，仍有改进的余地。如上图a所示，无向图的邻接矩阵必为对称阵，其中**除自环以外的每条边，都被重复地存放了两次。**也就是说，近一半的单元都是冗余的。为消除这一缺点，可采用压缩存储等技巧，进一步提高空间利用率。

#### 使用邻接矩阵实现一个图 ####

现在使用刚刚笔者定义的Node，Edge和AdjacencyMatrix定义一个图

public static void main(String[] args) {
    
    
           int aIndex = matrix.addNode(new Node<String>("a"));  //索引为0
           int bIndex = matrix.addNode(new Node<String>("b"));  //索引为1
           int cIndex =  matrix.addNode(new Node<String>("c"));  //索引为2
           int dIndex = matrix.addNode(new Node<String>("d"));  //索引为3
           int eIndex = matrix.addNode(new Node<String>("e"));  //索引为4
           int fIndex = matrix.addNode(new Node<String>("f"));  //索引为3
           int gIndex = matrix.addNode(new Node<String>("g"));  //索引为4
    
    
           matrix.setMatrix(aIndex, bIndex, new Edge<String>("这是边a到b的弧",1));
           matrix.setMatrix(aIndex, cIndex, new Edge<String>("这是边a到c的弧",1));
           matrix.setMatrix(bIndex, dIndex, new Edge<String>("这是边b到d的弧",1));
           matrix.setMatrix(bIndex, eIndex, new Edge<String>("这是边b到e的弧",1));
           matrix.setMatrix(cIndex, fIndex, new Edge<String>("这是边c到f的弧",1));
           matrix.setMatrix(cIndex, gIndex, new Edge<String>("这是边c到g的弧",1));
    
           //打印节点的出度和入度
           System.out.println("a:"+matrix.getInDeep(aIndex));
           System.out.println("a:"+matrix.getOutDeep(aIndex));
    
           System.out.println("b:"+matrix.getInDeep(bIndex));
           System.out.println("b:"+matrix.getOutDeep(bIndex));
    
           System.out.println("c:"+matrix.getInDeep(cIndex));
           System.out.println("c:"+matrix.getOutDeep(cIndex));
    
           System.out.println("d:"+matrix.getInDeep(dIndex));
           System.out.println("d:"+matrix.getOutDeep(dIndex));
     }

[SouthEast]: /images/20220604/16589139d3a5411b997037d13c141233.png