数据结构 图论01 邻接矩阵、邻接表 代码
数据结构 图论02 十字链表详解 代码

组成

顶点 + 边

（边可以没有但是至少有一个顶点）

图Graph是顶点vertex集合和边（也称之为弧 edge)集合组成。

• G=(V,E) 这里V是vertex顶点集合，E是edge边集合
• E=(Vi,Vj) 表示顶点i和顶点j之间的连线（边，弧）

常用术语

• 无向边：2边都能通行，用圆括号表示（类似双链表）
• 有向边：反之，用尖括号表示，（也称之为弧）
• 权：可以表示一个距离，（带权重的图Graph叫做网NetWork）
• 度：无向图顶点的边数量叫做度（因为往返的重复，度 = 边数 * 2），有向图分为出度和入度
  • 出度：顶点向外发出的边的数组
  • 入度：通向（进入）顶点的变的数目，
• 网：带权重的图（请注意区分权重不是度，比如地图的距离就是边长的一种权重）
• 弧：有向边称之为弧

图的分类

• 有向图：有方向的图，比如 $A\to B$ 单向通行
• 无向图：没有方向的图比如 $A - B $ 双向通行
• 完全图：任意2点都有边向连接
• 稀疏图：相对而言边（弧）比较少的图
• 稠密图：相对而言边（弧）比较多的图

数据结构（重点）

如果我们要表示下面有向图结构由5种数据方法

1.邻接矩阵

• 用一个固定长度的一维数组表示顶点vertexs[4]，相同长度的二维数组edges[4][4]表示有向边
• 例如A到B的距离是4，所以第一行（对应顶点A）的第二个元素edges[0][1] = 4

数组的查询是很快，

但是当稀疏图（就是图中的边十分少）的时候，二维数组是比较浪费内存，并且增加边和删除边十分不便，因此我们引出我们的第二个数据结构，邻接表

2.邻接表

邻接表表示上面的图graph如下

• 顶点集合为数组，顶点数组节点vertexNode,数组节点中vertex 表示顶点 ，edges 表示 代表边节点edgeNode的链表，
• 边链表节点，edgeNode ：adjVex 表示adjacency vertex 指向下一个定点的下标，（比如第一行的A顶点的第一个edgeNode 指向自己，第二个edgeNode 指向 下标为1 的B，第三个edgeNode 指向下标为 2 的 C)
• edgeNode 中 weight ：代表权重，这里表示二个顶点之间的距离。
• edgeNode 中的 next 指向连接到其他节点的边
• 我这里讨论了自身节点的情况，如果业务没有这个需求 ，你完全可以不必考虑这个情况

代码

这里展示java代码实现上面2种数据结构
1.邻接矩阵

public class AdjacencyMatrixGraph<E> {
   /** 顶点 */
   private ArrayList<E> vertices;
   /** 边 */
   private int[][] edges;
   private int numOfVertices;
   private int numOfEdges;
   private int maxNum;

   public AdjacencyMatrixGraph(int maxOfVertices) {
       maxNum = maxOfVertices;
       vertices = new ArrayList<>();
       edges = new int[maxOfVertices][maxOfVertices];
       //init valuation for edges.
       for (int i = 0; i < maxOfVertices; i++) {
           for (int j = 0; j < maxOfVertices; j++) {
               edges[i][j] = -1;
           }
       }
       numOfEdges = 0;
       numOfEdges = 0;
   }



   /**
    * 增 顶点
    * @param vertex
    * @return
    */
   public boolean putVertex(E vertex){
       if (numOfVertices < maxNum){
           vertices.add(numOfVertices,vertex);
           numOfVertices ++;
           return true;
       }
       return false;
   }

   /**
    * 查 顶点
    * @param indexOfVertex
    * @return
    */
  public E getVertex(int indexOfVertex){
       return vertices.get(indexOfVertex);
   }

   /**
    * 删 顶点
    * @param indexOfVertex
    * @return
    */
  public boolean removeVertex(int indexOfVertex){
       vertices.set(indexOfVertex,null);
       return true;
   }
   /**
    * 增 边
    * @param indexOfVertex1
    * @param indexOfVertex2
    * @param weight
    * @return
    */
   public boolean putEdge(int indexOfVertex1, int indexOfVertex2, int weight){
       if (indexOfVertex1 < maxNum && indexOfVertex2 < maxNum){
           edges[indexOfVertex1][indexOfVertex2] = weight;
           return true;
       }
       return false;
   }

   /**
    * 查 边
    * @param indexOfVertex1
    * @param indexOfVertex2
    * @return
    */
   public int getWeight(int indexOfVertex1,int indexOfVertex2 ){
       if (indexOfVertex1 < maxNum && indexOfVertex2 < maxNum){
           return edges[indexOfVertex1][indexOfVertex2];
       }
       return -1;
   }

   /**
    * 删边 (权重)
    * @param indexOfVertex1
    * @param indexOfVertex2
    * @return
    */
   public boolean removeEdge(int indexOfVertex1,int indexOfVertex2){
       if (indexOfVertex1 < maxNum && indexOfVertex2 < maxNum){
           edges[indexOfVertex1][indexOfVertex2] = -1;
           return true;
       }
       return false;
   }
   /**
    * 【重要】路径算法dijkstra 最短路径
    */
   public int dijkstra(int fromVertex,int toVertex){

       return -1;
   }


}

Test

 //顶点集合
 String[] vertices = {"A","B","C","D"};
 //创建一个顶点个数为4 的Graph
 AdjacencyMatrixGraph<String> graph = new AdjacencyMatrixGraph<>(vertices.length);
 //设置节点
 for (String vertex : vertices) {
     graph.putVertex(vertex);
 }
 //设置边
 graph.putEdge(0,1,4);
 graph.putEdge(0,2,3);
 graph.putEdge(0,3,7);
 graph.putEdge(1,2,5);
 graph.putEdge(3,2,6);
 //获得顶点
 System.out.println(graph.getVertex(1));
 //删除节点
 System.out.println(graph.removeVertex(1));
 //获得顶点
 System.out.println(graph.getVertex(1));
 //获得边
 System.out.println(graph.getWeight(0, 2));
//删除边
 System.out.println(graph.removeEdge(0, 2));
 System.out.println(graph.getWeight(0, 2));

2. 邻接表

public class AdjacencyTableGraph <E>{
    private class Vertex{
        private E elementVertex;
        private AdjacencyTableGraph.Edge next;

        public Vertex(E elementVertex, Edge next) {
            this.elementVertex = elementVertex;
            this.next = next;
        }
    }
    private class Edge{
        private int toVertex;
        private int weight;
        private Edge nextEdge;

        public Edge(int toVertex, int weight, Edge nextEdge) {
            this.toVertex = toVertex;
            this.weight = weight;
            this.nextEdge = nextEdge;
        }
    }
    private int numOfVertices;
    private int maxOfVertices;
    private ArrayList<Vertex> vertices;
    private Edge firstEdgeNode;

    public AdjacencyTableGraph(int maxOfVertices)  {
        this.maxOfVertices = maxOfVertices;
        this.vertices = new ArrayList<>(maxOfVertices);
        numOfVertices = 0;
    }
    public boolean putVertex(E vertex){
        if (numOfVertices < maxOfVertices){
            vertices.add(new Vertex(vertex,null));
            numOfVertices ++;
            return true;
        }
        return false;
    }
    public E getVertex(int vertexIndex){
        if (vertexIndex<maxOfVertices){
            return vertices.get(vertexIndex).elementVertex;
        }
        return null;
    }
    public boolean putEdge(int fromVertex,int toVertex,int weight){
        if (fromVertex < maxOfVertices && toVertex < maxOfVertices) {
            Vertex from = vertices.get(fromVertex);
            Edge edge = new Edge(toVertex,weight, null);
            if (from.next == null) {
                from.next = edge;
                return true;
            }
            //遍历链表将新的元素放到链表尾部
            Edge node = from.next;
            while (node.nextEdge != null){
                node = node.nextEdge;
            }
            node.nextEdge = edge;
            return true;
        }
        return false;
    }
    public int getWeight(int fromVertex, int toVertex){
        if (fromVertex < maxOfVertices && toVertex < maxOfVertices) {
            Vertex fromV = vertices.get(fromVertex);
            Edge node = fromV.next;
            while (node != null){
                if (node.toVertex == toVertex){
                    return node.weight;
                }
                node = node.nextEdge;
            }
        }
        return -1;
    }
    public void print(){
        for (Vertex vertex : vertices) {
            Edge node = vertex.next;
            while (node != null){
                System.out.println("节点"+vertex.elementVertex+" to 节点 "+vertices.get(node.toVertex).elementVertex +" weight " +node.weight);
                node = node.nextEdge;
            }
        }
    }
}

test

        //顶点集合
        String[] vertices = {"A","B","C","D"};
        //创建一个顶点个数为4 的Graph
        AdjacencyTableGraph<String> graph = new AdjacencyTableGraph<>(vertices.length);
        //设置节点
        for (String vertex : vertices) {
            graph.putVertex(vertex);
        }
        //设置边
        graph.putEdge(0,1,4);
        graph.putEdge(0,2,3);
        graph.putEdge(0,3,7);
        graph.putEdge(1,2,5);
        graph.putEdge(3,2,6);
        //打印图
        graph.print();
        //获得顶点
        System.out.println(graph.getVertex(1));
        //删除节点

        //获得边
        System.out.println(graph.getWeight(0, 2));
//        删除边
        System.out.println(graph.getWeight(0, 2));

**

数据结构	优点	缺点
邻接矩阵	二维数组，实现简单，能同时求出顶点的出度和入度	稀疏图造成的空间浪费
邻接表	数组+链表，不会空间浪费	不能同时求出出度和入度；对边的操作需要2次
十字链表	横竖十字链表：可以同时求出出度和入度	对边的操作需要2次
邻接多重表	对边的操作减少到了一次	删除较为复杂

备注：这里的链表插入是遍历到链表尾部再插入，效率比较低下，建议使用”头插法“