关于算法-数据结构:图的存储结构与实现总结

目录


图的存储构造

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

邻接矩阵

图的邻接矩阵存储形式是用两个数组来示意图一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息。
设图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();

    }

}

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理