目录
图的存储构造
图的存储构造次要分两种，一种是邻接矩阵，一种是邻接表。
邻接矩阵
图的邻接矩阵存储形式是用两个数组来示意图。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。
设图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(); }}