目录

图的存储构造

图的存储构造次要分两种，一种是 邻接矩阵 ，一种是 邻接表。

邻接矩阵

图的邻接矩阵存储形式是 用两个数组来示意图 。 一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。
设图 G 有 n 个顶点，则邻接矩阵是一个 n * n 的方阵，定义为：

看一个实例，下图左就是一个无向图。

从下面能够看出，无向图的边数组是一个对称矩阵 。所谓对称矩阵就是 n 阶矩阵的元满足 aij = aji。即从矩阵的左上角到右下角的主对角线为轴，右上角的元和左下角绝对应的元全都是相等的。
从这个矩阵中，很容易晓得图中的信息。
（1）要判断任意两顶点是否有边无际就很容易了；
（2）要晓得某个顶点的度，其实就是这个顶点 vi 在邻接矩阵中第 i 行或（第 i 列）的元素之和；
（3）求顶点 vi 的所有邻接点就是将矩阵中第 i 行元素扫描一遍，arc[i][j]为 1 就是邻接点；
而有向图考究入度和出度，顶点 vi 的入度为 1，正好是第 i 列各数之和。顶点 vi 的出度为 2，即第 i 行的各数之和。
若图 G 是网图，有 n 个顶点，则邻接矩阵是一个 n * n 的方阵，定义为：

邻接表

邻接矩阵是不错的一种图存储构造，然而，对于边数绝对顶点较少的图，这种构造存在对存储空间的极大节约。因而，找到一种数组与链表相结合的存储办法称为邻接表。
邻接表的解决办法是这样的：
（1）图中顶点用一个一维数组存储 ，当然，顶点也能够用单链表来存储，不过，数组能够较容易的读取顶点的信息，更加不便。
（2） 图中每个顶点 vi 的所有邻接点形成一个线性表，因为邻接点的个数不定，所以，用单链表存储 ，无向图称为顶点 vi 的边表， 有向图则称为顶点 vi 作为弧尾的出边表 。
例如，下图就是一个无向图的邻接表的构造。

从图中能够看出，顶点表的各个结点由 data 和 firstedge 两个域示意，data 是数据域，存储顶点的信息 ，firstedge 是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。 边表结点由 adjvex 和 next 两个域组成。adjvex 是邻接点域，存储某顶点的邻接点在顶点表中的下标，next 则存储指向边表中下一个结点的指针。
对于带权值的网图，能够在边 表结点定义中再减少一个 weight 的数据域，存储权值信息即可。如下图所示。

两者区别

对于一个具备 n 个顶点 e 条边的无向图
它的邻接表示意有 n 个顶点表结点 2e 个边表结点
对于一个具备 n 个顶点 e 条边的有向图
它的邻接表示意有 n 个顶点表结点 e 个边表结点
** 如果图中边的数目远远小于 n^2 称作稠密图，这是用邻接表示意比用邻接矩阵示意节俭空间;
如果图中边的数目靠近于 n^2, 对于无向图靠近于 n *(n-1)称作浓密图, 思考到邻接表中要附加链域，采纳邻接矩阵表示法为宜。**

图的 java 实现

这个实现是基于邻接矩阵的

顶点

应用 label 作为顶点的标识

edgelist 作为 linkedlist，存储以这个顶点为终点的边

前面 3 个属性是为了应答其余操作（比方深度遍历等），特意保留的变量

package datastructure.graph.adjacencymatrixgraph;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;


/** 邻接矩阵的顶点类
 * @author xusy
 *
 * @param <T>
 */
public class Vertex<T> {
    
    /**
     * 可能标识这个定点的属性，能够用不同类型来标识顶点如 String,Integer....
     */
    private T label;
    
    /**
     * 这个定点对应的边 <br>
     * 如果为有向图，则代表以这个定点为终点的边
     */
    private List<Edge> edgeList;
    
    /**
     * 示意这个顶点是否已被拜访，在 bfs 和 dfs 中会被应用到
     */
    private boolean visited;
    
    /**
     * 该顶点的前驱节点 <br>
     * 在求图中某两个顶点之间的最短门路时，在从起始顶点遍历过程中，须要记录下遍历到某个顶点时的前驱顶点
     */
    private Vertex previousVertex;
    
    /**
     * 这个定点的权值（留神不是边的权值）*/
    private double cost;
    
    /** 创立顶点
     * @param label  这个顶点的标识
     * @param cost  这个顶点的权值
     */
    public Vertex(T label,double cost){
        this.label=label;
        // 用链表存储边
        edgeList=new LinkedList<>();
        visited=false;
        previousVertex=null;
        this.cost=cost;
    }
    
    // 上面与顶点的标识相干
    
    /** 返回顶点的标识
     * @return
     */
    public T getLabel() {return label;}

    /** 
     * 依据顶点的标识确定是否是同一个顶点
     */
    @Override
    public boolean equals(Object otherVertex) {
        boolean result;
        // 如果 otherVertex 为空或者类不同，间接返回 false
        if(otherVertex==null||getClass()!=otherVertex.getClass()){return false;}
        Vertex other=(Vertex)otherVertex;
        // 依据 label 确定是否是同一个顶点
        result=label.equals(other.getLabel());
        return result;        
    }

    // 上面与顶点的边相干
    
    /** 返回边的迭代器
     * @return
     */
    public Iterator<Edge> getEdgeIterator(){return edgeList.iterator();
    }
    
    /** 返回是否有以这个顶点为出发点的边数
     * @return
     */
    public int getEdgeCount(){return edgeList.size();
    }

    /** 将这个顶点与 endVertex 连贯，边的权值为 weight
     * @param endVertex
     * @param weight
     * @return 如果顶点曾经与 endVertex 连贯，那么将会更新权值，返回 false<br>
     * 如果顶点没有与 endVertex 相连，则相互连贯，返回 true
     */
    public boolean connect(Vertex endVertex,double weight){Iterator<Edge> iterator=getEdgeIterator();
        Edge edge=null;
        Vertex vertex=null;
        while(iterator.hasNext()){edge=iterator.next();
            vertex=edge.getEndVertex();
            if(vertex.equals(endVertex)){
                // 如果顶点曾经与 endVertex 连贯，那么将会更新权值，返回 false
                edge.setWeight(weight);
                return false;
            }
        }
        // 如果顶点没有与 endVertex 相连，则相互连贯，返回 true
        edge=new Edge(this,endVertex, weight);
        edgeList.add(edge);        
        return true;
    }
    
    /** 将这个顶点与 endVertex 连贯的边删除
     * @param endVertex
     * @return  如果顶点曾经与 endVertex 连贯，那么将会删除这条边，返回 true<br>
     * 如果顶点没有与 endVertex 连贯，则啥都不做，返回 false
     */
    public boolean disconnect(Vertex endVertex){Iterator<Edge> iterator=getEdgeIterator();
        Edge edge=null;
        Vertex vertex=null;
        while(iterator.hasNext()){edge=iterator.next();
            vertex=edge.getEndVertex();
            if(vertex.equals(endVertex)){
                // 如果顶点曾经与 endVertex 连贯，那么将会删除这条边，返回 true
                //edgeList.remove(edge);
                iterator.remove();
                return true;
            }
        }
        // 如果顶点没有与 endVertex 连贯，则啥都不做，返回 false        
        return false;
    }    
    
    /** 返回是否有以这个顶点为出发点, 以 endVertex 为完结点的边
     * @return 如果有，返回那条边 <br>
     * 如果没有，返回 null
     */
    public Edge hasNeighbourVertex(Vertex endVertex){Iterator<Edge> iterator=getEdgeIterator();
        Edge edge=null;
        Vertex vertex=null;
        while(iterator.hasNext()){edge=iterator.next();
            vertex=edge.getEndVertex();
            if(vertex.equals(endVertex)){
                // 如果顶点曾经与 endVertex 连贯，那么将返回这个边            
                return edge;
            }
        }
        // 没有则返回 null
        return null;
    }

    
    
    // 上面是与顶点是否被拜访相干
    
    /** 返回顶点是否被拜访
     * @return
     */
    public boolean isVisited() {return visited;}
    
    /**
     * 拜访这个顶点
     */
    public void visit(){visited=true;}
    
    /**
     * 不拜访这个顶点，或者说是革除拜访状态
     */
    public void unVisit(){visited=false;}
    
    /** 取得以这个顶点为出发点，相邻的第一个没有被拜访的顶点
     * @return 如果没有，返回 null<br>
     * 如果有，返回对应的顶点
     */
    public Vertex getUnvisitedVertex(){Iterator<Edge> iterator=getEdgeIterator();
        Edge edge=null;
        Vertex vertex=null;
        while(iterator.hasNext()){edge=iterator.next();
            vertex=edge.getEndVertex();
            if(vertex.isVisited()==false){return vertex;}
        }
        // 没有则返回 null
        return null;
    }
    
    // 上面与前驱节点相干    

    /** 返回顶点的前驱节点
     * @return
     */
    public Vertex getPreviousVertex() {return previousVertex;}

    /** 设置顶点的前驱节点
     * @param previousVertex
     */
    public void setPreviousVertex(Vertex previousVertex) {this.previousVertex = previousVertex;}

    // 上面与顶点的权值相干
    
    /** 返回顶点的权值
     * @return
     */
    public double getCost() {return cost;}

    /** 设置顶点的权值
     * @param cost
     */
    public void setCost(double cost) {this.cost = cost;}
    
    
    
    
    
    
}

边
–

beginVertex 是开始点

endVertex 是完结点

weight 为边的权值

package datastructure.graph.adjacencymatrixgraph;

/** 连贯两个顶点的边
 * @author xusy
 *
 */
public class Edge {
    
    /**
     * beginVertex 是边的起始顶点 <br>
     * 一般状况是不必显示地存储 beginVertex，然而生成最小生成树时须要
     */
    private Vertex beginVertex;
    
    /**
     * 因为 Edge 是存储在 Vertex 中的，所以蕴含这个边的 vertex 是开始点
     * endVertex 是完结点
     */
    private Vertex endVertex;
    
    /**
     * 边的权值
     */
    private double weight;

    /** 创立边
     * @param beginVertex 边的开始点
     * @param endVertex 边的完结点
     * @param weight  边的权值
     */
    public Edge(Vertex beginVertex,Vertex endVertex, double weight) {
        this.beginVertex = beginVertex;
        this.endVertex = endVertex;
        this.weight = weight;
    }

        
    /** 返回边的开始点
     * @return
     */
    public Vertex getBeginVertex() {return beginVertex;}

    /** 返回边的完结点
     * @return
     */
    public Vertex getEndVertex() {return endVertex;}

    /** 返回边的权值
     * @return
     */
    public double getWeight() {return weight;}

    /** 设置边的权值
     * @param weight
     */
    public void setWeight(double weight) {this.weight = weight;}
    
    
    
    

}

图
–

isDirect 用来辨别有向图，区别就是退出边的时候，无向图会退出两条，有向图只会退出一条

如果不须要边和顶点的权值，退出时，设置为 0 即可

package datastructure.graph.adjacencymatrixgraph;

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;

/** 邻接矩阵的图类
 * @author xusy
 *
 * @param <T>
 */
public class Graph<T> {
    
    /**
     * 用来存储顶点
     * T 做为标识，vertext 作为理论的顶点
     */
    private Map<T, Vertex<T>> vertexMap;
    
    /**
     * 图中边的数目 <br>
     * 顶点的数目能够用 vertexMap.size()
     */
    private int edgeCount;
    
    /**
     * 图是否为有向图 <br>
     * 如果是有向图，则为 true
     */
    boolean isDirect;
    
    /** 图的构造函数
     * @param isDirect  图是否为有向图 <br>
     * 如果是有向图，则为 true
     */
    public Graph(boolean isDirect){vertexMap=new LinkedHashMap<>();
        edgeCount=0;
        this.isDirect=isDirect;
    }
    

    // 上面与图的顶点相干
    
    /** 返回图中的顶点个数
     * @return
     */
    public int getVertexCount(){return vertexMap.size();
    }
    
    /** 返回图的顶点的迭代器
     * @return
     */
    public Iterator<Vertex<T>> getVertexIterator(){return vertexMap.values().iterator();}
    
    /** 在图中插入节点，节点的标识为 label, 节点的权值为 cost
     * @param label
     * @param cost  如果不须要节点的权值，则设 0 即可
     * @return 如果图中不存在该节点，则插入，返回 true<br>
     * 如果图中曾经存在该节点，则更新权值，返回 false
     */
    public boolean addVertex(T label,double cost){Vertex vertex=vertexMap.get(label);
        if(vertex!=null){
            // 如果图中曾经存在该节点，则更新权值，返回 false
            vertex.setCost(cost);
            return false;
        }
        // 如果图中不存在该节点，则插入，返回 true
        vertex=new Vertex<T>(label, cost);
        vertexMap.put(label, vertex);
        return true;
    }
    
    // 上面与图的边相干
    
    /** 返回图中所有的边的个数 <br>
     * 如果为有向图，则是所有的有向边的个数 <br>
     * 如果为无向图，则视一条边为两条相同的有向边，相当于返回无向边的个数 *2
     * @return
     */
    public int getEdgeCount(){Iterator<Vertex<T>> iterator=getVertexIterator();
        int count=0;
        while(iterator.hasNext()){Vertex<T> vertex=iterator.next();
            count=count+vertex.getEdgeCount();}
        return count;
    }
    
    /** 返回图中标识为 label 的顶点作为出发点的边的个数
     * @param label
     * @return 如果为有向图，则返回标识为 label 的顶点作为出发点的边的个数
     * 如果为无向图，则返回标识为 label 的顶点相连接的边的个数
     * 如果图中没有这个顶点，返回 -1
     */
    public int getEdgeCount(T label){Vertex<T> vertex=vertexMap.get(label);
        if(vertex==null){
            // 如果图中没有这个顶点，返回 -1
            return -1;
        }
        // 返回途中标识为 label 的顶点作为出发点的边的个数
        return vertex.getEdgeCount();}
    
    /** 返回图中标识为 label 的顶点作为出发点的边的迭代器
     * @param label
     * @return 如果没有这个顶点，返回 null
     */
    public Iterator<Edge> getEdgeIterator(T label){Vertex<T> vertex=vertexMap.get(label);
        if(vertex==null){
            // 如果图中没有这个顶点，返回 null
            return null;
        }
        return vertex.getEdgeIterator();}
    
    
    /** 在图中退出一条边，如果 isDirect 为 true，则为有向图，则 <br>
     * 建设一条以 begin 作为标识的节点开始的边，以 end 作为标识的节点完结，边的权值为 weight<br>
     * 如果 isDirect 为 false，则为无向图，则 <br>
     * 建设两条边，一条以 begin 开始，到 end，一条以 end 开始，到 begin
     * @param begin
     * @param end
     * @param weight 如果不须要边的权值，能够设为 0
     * @return 如果没有对应的边，则退出对应的边，返回 true<br>
     * 如果有对应的边，则更新 weight，返回 false
     * 如果没有以 begin 或者 end 标识的顶点，则间接返回 false
     */
    public boolean addEdge(T begin,T end,double weight){Vertex beginVertex=vertexMap.get(begin);
        Vertex endVertex=vertexMap.get(end);
        if(beginVertex==null||endVertex==null){
            // 如果没有以 begin 或者 end 标识的顶点，则间接返回 false
            return false;
        }
        // 有向图和无向图都要建设 begin 到 end 的边
        // 如果顶点曾经与 endVertex 连贯，那么将会更新权值，result=false
        // 如果顶点没有与 endVertex 相连，则相互连贯，result=true
        boolean result=beginVertex.connect(endVertex, weight);
        if(result){edgeCount++;}
        if(!isDirect){
            // 如果不是有向图，则建设两条边, 一条以 end 开始，到 begin
            endVertex.connect(beginVertex, weight);
            if(result){edgeCount++;}
        }                
        return result;
    }
    
    /** 在图中删除一条边，如果 isDirect 为 true，则为有向图，则 <br>
     * 删除一条以 begin 作为标识的节点开始的边，以 end 作为标识的节点完结 <br>
     * 如果 isDirect 为 false，则为无向图，则 <br>
     * 删除两条边，一条以 begin 开始，到 end，一条以 end 开始，到 begin
     * @param begin
     * @param end
     * @return 如果有对应的边，则删除对应的边，返回 true<br>
     * 如果没有有对应的边，则间接返回 false
     * 如果没有以 begin 或者 end 标识的顶点，则间接返回 false
     */
    public boolean removeEdge(T begin,T end){Vertex beginVertex=vertexMap.get(begin);
        Vertex endVertex=vertexMap.get(end);
        if(beginVertex==null||endVertex==null){
            // 如果没有以 begin 或者 end 标识的顶点，则间接返回 false
            return false;
        }
        // 有向图和无向图都要删除 begin 到 end 的边
        // 如果顶点曾经与 endVertex 连贯，那么将会删除这条边，返回 true
        // 如果顶点没有与 endVertex 连贯，则啥都不做，返回 false
        boolean result=beginVertex.disconnect(endVertex);
        if(result){edgeCount--;}
        if(!isDirect){
            // 如果不是有向图，则删除两条边, 一条以 end 开始，到 begin
            endVertex.disconnect(beginVertex);
            if(result){edgeCount--;}
        }                
        return result;
    }
    

    // 上面与打印相干
    
    /**
     * 打印图的详情，所有顶点，所有边
     */
    public void printGraph(){Iterator<Vertex<T>> iteratorVertex=getVertexIterator();
        Iterator<Edge> iteratorEdge;
        Vertex<T> vertex;
        Edge edge;
        T label;
        System.out.println("图是否为有向图："+isDirect+"，图的顶点个数："+getVertexCount()+"，图的总边个数："+getEdgeCount());
        while(iteratorVertex.hasNext()){vertex=iteratorVertex.next();
            label=vertex.getLabel();
            iteratorEdge=vertex.getEdgeIterator();
            System.out.println("顶点："+label+"，以这个顶点为出发点的边的个数："+getEdgeCount(label)+"，该顶点的权值为："+vertex.getCost());
            while(iteratorEdge.hasNext()){edge=iteratorEdge.next();
                System.out.print("边：从"+label+"到"+edge.getEndVertex().getLabel()+"，权值："+edge.getWeight()+" ");
            }
            System.out.println();}
        System.out.println();}
    
    
}

测试

package datastructure.graph.adjacencymatrixgraph;

public class Main {public static void main(String[] args) {Graph<String> graph=new Graph<>(false);
        graph.addVertex("first", 0);
        graph.addVertex("second", 0);
        graph.addVertex("third", 1);
        graph.addEdge("first", "second", 1);
        graph.addEdge("first", "third", 2);
        
        graph.printGraph();
        
        graph.removeEdge("first", "second");
        graph.printGraph();}

}