图的邻接表的实现

待我称王封你为后i 2022-06-04 03:53 176阅读 0赞

上篇文章介绍了图的[邻接矩阵][Link 1]的实现，本文即介绍图的另一种实现方法-邻接表

#### 邻接表的实现原理 ####

使用邻接矩阵实现图，对于n个顶点的图，即使是有向图也需要O(n^2)。实际上，如此大的空间足以容纳所有潜在的弧。然而实际应用所处理的图，所含的  
边通常远远少于O(n^2)。比如在平面图之类的稀疏图（sparse graph）中，边数渐进地不超过O(n)，仅与顶点总数大致相当。  
由此可见，邻接矩阵的空间效率之所以低，是因为其中大量单元所对应的弧，并未在图中出现。类似的问题也出现的树的顺序存储结构，对应的也可以通过链式存储的方法来改变。  
按照这一思路，的确可以导出图结构的另一种表示与实现形式。

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

以图a所示的无向图为例，只需将如图b所示的邻接矩阵，逐行地转换为图c所示的一组列表，即可分别记录各顶点的关联边（或等价地，邻接顶点）。这些表便称之为邻接表（adjacency list）。

#### 图到邻接表的转化过程 ####

以上图为例，对于图a的四个顶点A，B，C，D四个顶点的属性上添加一个对于弧的指针，指向以该顶点为起点的一条弧(被称为该顶点为起点的所有弧的首弧)。而对于弧的属性也增加一个对顶点的指针和对弧的指针，其中对于顶点的指针指向该弧的终点(弧头)，而对弧的指针指向已该弧的起点(弧尾)的另一条弧。  
这样，根据一个顶点的弧的指针，通过这个弧对于其他的弧的指针即可定义出该顶点作为起点(弧尾)的所有弧。也可以根据一个顶点的弧的指针，通过这个弧对于弧的终点的指针(弧头)便可定义出由该顶点起的一条路。

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

public class Node<T> {
    
        private T data; // 存储的数据
        private Edge head; // 该节点作为弧的起点(弧尾)的首弧
        private int outDegree; // 出度
        private int inDegree; // 入度
        //以下属性在遍历中使用
        private int status = 0;  
        //状态 0 undiscovered  1 discovered   2 visited
        //此处应该使用枚举，笔者偷懒了
        private int parent = -1;
        private int dTime = -1; //开始遍历的时间
        private int fTime = -1; //结束遍历的时间
    
        //省掉getter和setter...
        public void addInDegree() {
            this.inDegree++;
        }
    
        protected void addOutDegree() {
            this.outDegree++;
        }
    
        protected void delInDegree() {
            this.inDegree--;
        }
    
        protected void delOutDegree() {
            this.outDegree--;
        }
    
        //设置一条也该节点为起点的弧
        protected void setEdge(Edge edge) {
            // 从该节点的弧链接头指针出发
            Edge nextNull = getHead();
            if(nextNull == null) {
                // 找到最后的指针并指向新弧
                setHead(edge);
                return;
            }
            Edge nowEdge = nextNull.getNextEdge();
            while (nowEdge != null) {
                nextNull = nowEdge;
                nowEdge = nowEdge.getNextEdge();
            }
            // 找到最后的指针并指向新弧
            nextNull.setNextEdge(edge);
        }
    }

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

public class Edge<T> {
    
        private int edgeHear; //弧头索引
        private Edge<T> nextEdge;  //指向下一条弧
        private T data; // 边数据
        private int weight; // 权值
        private int type; 
        //边类型：0 CROSS 跨边  1 TREE（支撑树） 
        //2 BACKWARD(该弧的起点和终点在支撑树中存在终点到起点的路径)    //3FORWARD (该弧的起点和终点在支撑树中存在其他路径依然可以从起点到终点)
    
     //getter setter 省掉
    }

#### 邻接表的实现 ####

public class AdjacencyList {
    
        private Node[] allNodes;
        private int DEFAULT_CAPACITY = 10;
        private int size=0;
    
        public AdjacencyList() {
    
              allNodes = new Node[DEFAULT_CAPACITY];
        }
    
        public int addNode(Node node) {
               int index = size;
               //扩容
               ensureCapacityInternal(index+1);
               allNodes[size++] = node;
               return index;
        }
    
        public void setEdge(int nodeIndex, Edge edge) {
    
              Node start = this.allNodes[nodeIndex];
              Node end = this.allNodes[edge.getEdgeHear()];
              start.setEdge(edge);
              start.addOutDegree();
              end.addInDegree();
    
        }
    
        public Node getNodes(int index) {
            return this.allNodes[index];
        }
    
        //获取出度
        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();
        }
    
        //获取
        public Edge getEdge(int start, int end) {
              Edge firstEdge = allNodes[start].getHead();
    
              if(firstEdge == null) {
                  return null;
              }
    
              if(firstEdge.getEdgeHear() == end) {
                  return firstEdge;
              }
    
              Edge next = firstEdge.getNextEdge();
    
              while(next!=null) {
                if(next.getEdgeHear() == end) {
                    return next;
                }
    
                next = next.getNextEdge();
              }
              return null;
        }
    
        public void reload() {
          for(int i=0;i<size;i++) {
              allNodes[i].setStatus(0);
          }
        }
        //扩容
        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;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
    
            allNodes = Arrays.copyOf(allNodes, newCapacity);
        }
    
    }

#### 复杂度 ####

邻接表所含列表数等于顶点总数n，每条边在其中仅存放一次（有向图）或两次（无向图），故空间总量为O(n+e)，与图自身的规模相当，较之邻接矩阵有很大改进。当然，空间性能的这一改进，需以某些方面时间性能的降低为代价。如为判断顶点v到u的弧是否存在，getEdge(v, u)需在v对应的邻接表中顺序查找，共需O(n)时间。

与顶点相关操作接口，时间性能依然保持，甚至有所提高。比如，顶点的插入操作，可在O(1)而不是O(n)时间内完成。当然，顶点的删除操作，仍需遍历所有邻接表，共需O(e)时间。尽管邻接表访问单条边的效率并不算高，却十分擅长于以批量方式，处理同一顶点的所有弧。这是典型的处理流程和模式。比如，为枚举从顶点v发出的所有边，现在仅需O(1+outDegree(v))而非O(n)时间。  
故总体而言，邻接表的效率较之邻接矩阵更高

#### 基于上述定义的邻接表的使用 ####

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

[Link 1]: http://blog.csdn.net/canot/article/details/78703184
[SouthEast]: /images/20220604/5da224f14f544ae0a226b6d1f4071fa9.png