共计 9979 个字符，预计需要花费 25 分钟才能阅读完成。
目录
图的存储构造
图的存储构造次要分两种，一种是 邻接矩阵 ，一种是 邻接表。
邻接矩阵
图的邻接矩阵存储形式是 用两个数组来示意图 。 一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。
设图 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();}
}
正文完
