11.图-有向图
目录
一、有向图。
package 图的入门.有向图;
import 线性表.线性表_队列.Queue;
public class Digraph {
//顶点数目
private final int V;
//边的数目
private int E;
//邻接表
private Queue<Integer>[] adj;
public Digraph(int V){
//初始化顶点数量
this.V = V;
//初始化边的数量
this.E = 0;
//初始化邻接表
this.adj = new Queue[V];
for (int i = 0; i < adj.length; i++) {
adj[i] = new Queue<>();
}
}
//获取顶点数目
public int V(){
return V;
}
//获取边的数目
public int E(){
return E;
}
//向有向图中添加一条边v-》w
public void addEdge(int v,int w){
//只需要让顶点w出现在顶点v的邻接表中，因为边是有方向的，最终顶点v的邻接表中存储的相邻顶点的含义是：v-》其他顶点
adj[v].enqueue(w);
E++;
}
//获取由v指出的边所连接的所有顶点
public Queue<Integer> adj(int v){
return adj[v];
}
//获取该图的反向图
private Digraph reverse(){
//创建有向图对象
Digraph r = new Digraph(V);
for (int v = 0; v < V; v++) {//原图中表示的是由顶点v-》w的边
//获取由该顶点v指出的所有边
for (Integer w : adj[v]) {
r.addEdge(w,v);//w->v
}
}
return reverse();
}
}
二、拓扑排序。
（1）检测有向图中是否有环。
package 图的入门.有向图.图_拓扑排序_检测有向环;
import 图的入门.有向图.Digraph;
public class DirectedCycle {
//索引代表顶点，值表示当前顶点是否已经被搜索
private boolean[] marked;
//记录图中是否有环
private boolean hasCycle;
//索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上
private boolean[] onStack;
//创建一个检测环对象，检测图G中是否有环
public DirectedCycle(Digraph G){
//初始化marked数组
this.marked = new boolean[G.V()];
//初始化hasCycle
this.hasCycle = false;
//初始化onStack数组
this.onStack = new boolean[G.V()];//基本数据类型都有默认值，这里默认全部为false，引用类型数据默认是null
//找到图中每一个顶点，让每一个顶点作为人口，调用一次dfs进行搜索v
for (int v = 0; v < G.V(); v++) {
//判断如果当前结点还没有搜索过(一个连通子图中有一个调用dfs就足够了，但是图不一定就全部相通（连通图），可能有很多连通子图)，则调用dfs进行搜索
if (!marked[v]){
dfs(G,v);
}
}
}
//基于深度优先搜索，检测图G中是否有环
private void dfs(Digraph G,int v){
//把顶点v表示为已搜索
marked[v] = true;
//把当前顶点进栈
onStack[v] = true;
//进行深度搜索
/**
* 重点注意：这里的增强遍历其实不是拿出就删除了（因为这里是记录结点，然后指向下一个结点，是链表的使用），所以可以一直使用
* 如果是调用dequeue()方法，那么就会删除
*/
for (Integer w : G.adj(v)) {
//如果当前顶点w没有被搜索过，则继续递归调用dfs方法完成深度优先搜索
if (!marked[w]){
dfs(G,w);
}
//判断当前顶点w是否已经在栈中，如果已经在栈中，证明当前顶点之前处于正在搜索的状态，那么现在又要搜索一次，证明检测到环了
if (onStack[w]){
hasCycle = true;
return;
}
}
//把当前顶点出栈
onStack[v] = false;
}
//判断当前有向图G中是否有环
public boolean hasCycle(){
return hasCycle;
}
}
（2）基于深度优先的顶点排序（拓扑排序）。
package 图的入门.有向图.图_拓扑排序_顶点排序;
import 图的入门.有向图.Digraph;
import 线性表.线性表_栈.Stack;
public class DepthFirstOrder {
//索引代表顶点，值表示当前顶点是否已经被搜索
private boolean[] marked;
//使用栈，存储顶点序列
private Stack<Integer> reversePost;
//创建一个检测环对象，检测图G中是否有环
public DepthFirstOrder(Digraph G){
//初始化marked数组
this.marked = new boolean[G.V()];
//初始化reversePost栈
this.reversePost = new Stack<>();
//遍历图中每一个顶点，让每个顶点作为入口，完成一次深度优先搜索
for (int v = 0; v < G.V(); v++) {
if (!marked[v]){
dfs(G,v);
}
}
}
//基于深度优先搜索，检测图G中是否有环
private void dfs(Digraph G,int v){
//标记当前v已经被搜索
marked[v] = true;
//通过循环深度搜索顶点v
for (Integer w : G.adj(v)) {
if (!marked[w]){
dfs(G,w);
}
}
//让顶点v进栈
reversePost.push(v);
}
//获取顶点线性序列
public Stack<Integer> reversePost(){
return reversePost;
}
}
（3）拓扑排序。
package 图的入门.有向图.图_拓扑排序;
import 图的入门.有向图.Digraph;
import 图的入门.有向图.图_拓扑排序_检测有向环.DirectedCycle;
import 图的入门.有向图.图_拓扑排序_顶点排序.DepthFirstOrder;
import 线性表.线性表_栈.Stack;
public class TopoLogical {
//顶点的拓扑排序
private Stack<Integer> order;
//构造拓扑排序对象
public TopoLogical(Digraph G){
/**
* 虽然下面创建的两个对象都从同一个队列中取出数据
* 但是使用的是增强for遍历，不会影响队列里面的数据
*/
//创建一个检测有向环的对象
DirectedCycle cycle = new DirectedCycle(G);
//判断G图中有没有环，如果没有环，则进行顶点排序：创建一个顶点排序对象
if (!cycle.hasCycle()){
DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
order = depthFirstOrder.reversePost();
}
}
//判断G图是否有环
private boolean isCycle(){
return order == null;
}
//获取拓扑排序的所有顶点
public Stack<Integer> order(){
return order;
}
}
测试代码：
package 图的入门.有向图.图_拓扑排序;
import 图的入门.有向图.Digraph;
import 线性表.线性表_栈.Stack;
public class TopoLogicalTest {
public static void main(String[] args) {
//准备有向图
Digraph digraph = new Digraph(6);
digraph.addEdge(0,2);
digraph.addEdge(0,3);
digraph.addEdge(2,4);
digraph.addEdge(3,4);
digraph.addEdge(4,5);
digraph.addEdge(1,3);
//通过TopoLogical对象对有向图中的顶点进行排序
TopoLogical topoLogical = new TopoLogical(digraph);
//获取顶点的线性序列进行打印
Stack<Integer> order = topoLogical.order();
StringBuilder sb = new StringBuilder();
for (Integer w : order) {
sb.append(w+"->");
}
String str = sb.toString();
int index = str.lastIndexOf("->");
str = str.substring(0, index);
System.out.println(str);
}
}
三、加权有向图。
（1）加权有向边。
package 图的入门.有向图.加权有向图;
public class DirectedEdge {
private final int v;//起点
private final int w;//终点
private final double weight;//当前边的权重
//通过顶点v和w，以及权重weight值构造一个边对象
public DirectedEdge(int v,int w,double weight){
this.v = v;
this.w = w;
this.weight = weight;
}
//获取边的权重值
public double weight(){
return weight;
}
//获取有向边的起点
public int from(){
return v;
}
//获取有向边的终点
public int to(){
return w;
}
}
（2）加权有向图。
package 图的入门.有向图.加权有向图;
import 线性表.线性表_队列.Queue;
public class EdgeWeightedDigraph {
//顶点总数
private final int V;
//边的总数
private int E;
//邻接表
private Queue<DirectedEdge>[] adj;
//创建一个含有V个顶点的空加权有向图
public EdgeWeightedDigraph(int V){
//初始化顶点数量
this.V = V;
//初始化边的数量
this.E = 0;
//初始化邻接表
this.adj = new Queue[V];
for (int i = 0; i < adj.length; i++) {
adj[i] = new Queue<>();
}
}
//获取图中顶点的数量
public int V(){
return V;
}
//获取图中边的数量
public int E(){
return E;
}
//向加权有向图中添加一条边e
public void addEdge(DirectedEdge e){
//边e是有方向的，所以只需要让e出现在起点的邻接表中即可
int v = e.from();
adj[v].enqueue(e);
E++;
}
//获取由顶点v指出的所有的边
public Queue<DirectedEdge> adj(int v){
return adj[v];
}
//获取加权有向图的所有边
public Queue<DirectedEdge> edges(){
//遍历图中的每一个顶点，得到该顶点的邻接表，遍历得到每一条边，添加到队列中返回即可
Queue<DirectedEdge> allEdges = new Queue<>();
for (int v = 0; v < V; v++) {
for (DirectedEdge e : adj[v]) {
allEdges.enqueue(e);
}
}
return allEdges;
}
}
四、最短路径-Dijstra算法。
最小生成树是连接所有的顶点，而最短路径是起点到终点，是一条路径，不需要连接所有顶点，只需要部分顶点。
package 图的入门.有向图.最短路径_Dijstra算法;
import 优先队列.IndexMinPrioirityQueue;
import 图的入门.有向图.加权有向图.DirectedEdge;
import 图的入门.有向图.加权有向图.EdgeWeightedDigraph;
import 线性表.线性表_队列.Queue;
public class DijstraSP {
//索引代表顶点，值表示从顶点s到当前顶点的最短路径上的最后一条边
private DirectedEdge[] edgeTo;
//索引代表顶点，值从顶点s到当前顶点的最短路径的总权重
private double[] distTo;
//存放树中顶点与非树中顶点之间的有向横切边
private IndexMinPrioirityQueue<Double> pq;
//根据一副加权有向图G和顶点s，创建一个计算顶点s的最短路径树对象
public DijstraSP(EdgeWeightedDigraph G,int s){
//初始化edgeTo
this.edgeTo = new DirectedEdge[G.V()];
//初始化distTo
this.distTo = new double[G.V()];
for (int i = 0; i < distTo.length; i++) {
distTo[i] = Double.POSITIVE_INFINITY;//double类型的最大值
}
//初始化pq
this.pq = new IndexMinPrioirityQueue<>(G.V());
//找到图G中以顶点s为起点的最短路径树
//默认让顶点s进入最短路径树中
distTo[s] = 0.0;
pq.insert(s,0.0);
//遍历pq
while (!pq.isEmpty()){
relax(G,pq.delMin());
}
}
//松弛图G中的顶点v
private void relax(EdgeWeightedDigraph G,int v){
for (DirectedEdge edge : G.adj(v)) {
//获取到该边的终点w
int w = edge.to();
//通过松弛技术，判断从起点s到顶点w的最短路径是否需要先从顶点s到顶点v，然后再由顶点v到顶点w
if (distTo[v] + edge.weight() < distTo[w]){//这一步已经将已存在最短路径中的顶点排除了，进不来
distTo[w] = distTo[v] + edge.weight();
edgeTo[w] = edge;
//判断pq中是否已经存在顶点w，如果存在，则更新权重，如果不存在，则支架添加
if (pq.contains(w)){
pq.changeItem(w,distTo[w]);
}else {
pq.insert(w,distTo[w]);
}
}
}
}
//获取从顶点s到顶点v的最短路径的总权重
public double distTo(int v){
return distTo[v];
}
//判断从顶点s到顶点v是否可通达
public boolean hasPathTo(int v){
return edgeTo[v] != null;
//也可以这样
// return distTo[v] < Double.POSITIVE_INFINITY;
}
//查询从起点s到顶点v的最短路径中所有的边
public Queue<DirectedEdge> pathTo(int v){
//判断从顶点s到顶点v是否可达，如果不可达，直接返回null
if (!hasPathTo(v)){
return null;
}
//创建队列对象
Queue<DirectedEdge> allEdges = new Queue<>();
while (true){
DirectedEdge e = edgeTo[v];
if (e == null){
break;
}
allEdges.enqueue(e);
v = e.from();
}
return allEdges;
}
}
package 图的入门.有向图.最短路径_Dijstra算法;
import 图的入门.有向图.加权有向图.DirectedEdge;
import 图的入门.有向图.加权有向图.EdgeWeightedDigraph;
import 线性表.线性表_队列.Queue;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class DijstraSPTest {
public static void main(String[] args) throws IOException {
//创建一副加权有向图
BufferedReader br = new BufferedReader(new InputStreamReader(DijstraSPTest.class.getClassLoader().getResourceAsStream("min_route_test.txt")));
int total = Integer.parseInt(br.readLine());
EdgeWeightedDigraph G = new EdgeWeightedDigraph(total);
int edgeNubers = Integer.parseInt(br.readLine());
for (int i = 0; i < edgeNubers; i++) {
String line = br.readLine();
String[] str = line.split(" ");
int v = Integer.parseInt(str[0]);
int w = Integer.parseInt(str[1]);
double weight = Double.parseDouble(str[2]);
//创建加权有向边
DirectedEdge edge = new DirectedEdge(v, w, weight);
G.addEdge(edge);
}
//创建DijstraSP对象，查找最短路径树
DijstraSP dijstraSP = new DijstraSP(G, 0);
//查找最短路径,0->6的最短路径
Queue<DirectedEdge> edges = dijstraSP.pathTo(6);
//遍历打印
for (DirectedEdge edge : edges) {
System.out.println(edge.from()+"->"+edge.to()+" :: "+edge.weight());
}
}
}