// 图的接口
public interface Graph {
public int V();
public int E();
public void addEdge(int v, int w);
boolean hasEdge(int v, int w);
void show();
public Iterable<Integer> adj(int v);
}- 邻接矩阵表示无向图
- 邻接矩阵表示有向图
/**
* 稠密图-邻接矩阵
*/
public class DenseGraph {
private int n; // 节点数
private int m; // 边数
private boolean directed; // 是否为有向图
private boolean[][] g; // 图的具体数据
// 构造函数
public DenseGraph( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0; // 初始化没有任何边
this.directed = directed;
// g初始化为n*n的布尔矩阵, 每一个g[i][j]均为false, 表示没有任和边
// false为boolean型变量的默认值
g = new boolean[n][n];
}
public int V(){ return n;} // 返回节点个数
public int E(){ return m;} // 返回边的个数
// 向图中添加一个边
public void addEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
if( hasEdge( v , w ) ){
return;
}
g[v][w] = true;
if( !directed ){
g[w][v] = true;
}
m ++;
}
// 验证图中是否有从v到w的边
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
return g[v][w];
}
//遍历邻边
//返回图中一个顶点的所有相邻顶点
public Iterable<Integer> adj(int v) {
assert v >= 0 && v < n;
Vector<Integer> adjV = new Vector<Integer>();
for(int i = 0 ; i < n ; i ++ )
if( g[v][i] )
adjV.add(i);
return adjV;
}
}- 邻接表表示无向图
- 邻接表表示有向图
/**
* 稀松图-领接表
*/
public class SparseGraph {
private int n; // 节点数
private int m; // 边数
private boolean directed; // 是否为有向图
private Vector<Integer>[] g; // 图的具体数据
// 构造函数
public SparseGraph( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0; // 初始化没有任何边
this.directed = directed;
// g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
g = (Vector<Integer>[])new Vector[n];
for(int i = 0 ; i < n ; i ++){
g[i] = new Vector<Integer>();
}
}
public int V(){ return n;} // 返回节点个数
public int E(){ return m;} // 返回边的个数
// 向图中添加一个边
public void addEdge( int v, int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
g[v].add(w);
if( v != w && !directed ){
g[w].add(v);
}
m ++;
}
// 验证图中是否有从v到w的边 -->时间复杂度：O(n)
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
for( int i = 0 ; i < g[v].size() ; i ++ ){
if( g[v].elementAt(i) == w ){
return true;
}
}
return false;
}
//遍历邻边
//返回图中一个顶点的所有相邻顶点
public Iterable<Integer> adj(int v){
assert v>=0 && v<n;
return g[v];
}
}/**
* 图的深度优先遍历
*/
public class DepthFirstPaths {
//标记顶点是否被访问过
private boolean[] visited;
//记录路径
private int[] edgeTo;
//起点
private int s;
public DepthFirstPaths(Graph graph,int s){
visited=new boolean[graph.V()];
edgeTo=new int[graph.V()];
for(int i=0;i<graph.V();i++){
edgeTo[i]=-1;
}
this.s=s;
dfs(graph,this.s);
}
//深度优先搜索
private void dfs(Graph graph,int v){
visited[v]=true;
for(int w:graph.adj(v)){
if(!visited[w]){
edgeTo[w]=v; //w--->v的路径
dfs(graph,w);
}
}
}
//是否有到顶点v的路径
private boolean hasPathTo(int v){
return visited[v];
}
//获取从 s->v 的路径
public Iterable<Integer> pathTo(int v){
if(!hasPathTo(v)){
return null;
}
Stack<Integer> path=new Stack<>();
for(int i=v;i!=s;i=edgeTo[i]){
path.push(i);
}
path.push(s);
return path;
}
public void showPath(int v){
Stack<Integer> path= (Stack<Integer>) pathTo(v);
StringBuffer sb=new StringBuffer();
sb.append("[");
while(!path.isEmpty()){
int w=path.peek();
if(path.size()==1){
sb.append(w);
path.pop();
}else{
sb.append(w+"-->");
path.pop();
}
}
sb.append("]");
System.out.println(sb.toString());
}
}时间复杂度：
-
领接表：O(V+E)
-
邻接矩阵：O(V^2)
/**
* 图的dfs应用之统计图的连通分量
*/
public class Component {
private Graph graph;
//连通分量的个数
private int num;
private boolean[] visited;
public Component(Graph graph){
this.graph=graph;
visited=new boolean[graph.V()];
num=0;
for(int i=0;i<graph.V();i++){
if(!visited[i]){
dfs(i);
num++;
}
}
}
private void dfs(int v){
visited[v]=true;
for(int w:graph.adj(v)){
if(!visited[w]){
dfs(w);
}
}
}
//获取连通分量个数
public int getNum(){
return num;
}
}/**
* 图的广度优先遍历
*/
public class BreadthFirstPaths {
//标记顶点是否被访问过
private boolean[] visited;
//记录路径
private int[] edgeTo;
//起点
private int s;
public BreadthFirstPaths(Graph graph, int s){
visited=new boolean[graph.V()];
edgeTo=new int[graph.V()];
for(int i=0;i<graph.V();i++){
edgeTo[i]=-1;
}
this.s=s;
bfs(graph,this.s);
}
//广度优先搜索
private void bfs(Graph graph,int s){
visited[s]=true;
Queue<Integer> queue=new LinkedList<>();
queue.add(s);
while (!queue.isEmpty()){
int v=queue.poll();
for(int w:graph.adj(v)){
if(!visited[w]){
visited[w]=true;
edgeTo[w]=v;
queue.add(w);
}
}
}
}
//是否有到顶点v的路径
private boolean hasPathTo(int v){
return visited[v];
}
//获取从 s->v 的路径
public Iterable<Integer> pathTo(int v){
if(!hasPathTo(v)){
return null;
}
Stack<Integer> path=new Stack<>();
for(int i=v;i!=s;i=edgeTo[i]){
path.push(i);
}
path.push(s);
return path;
}
public void showPath(int v){
Stack<Integer> path= (Stack<Integer>) pathTo(v);
StringBuffer sb=new StringBuffer();
sb.append("[");
while(!path.isEmpty()){
int w=path.peek();
if(path.size()==1){
sb.append(w);
path.pop();
}else{
sb.append(w+"-->");
path.pop();
}
}
sb.append("]");
System.out.println(sb.toString());
}
}public class ShortestPath {
//标记顶点是否被访问过
private boolean[] visited;
//记录路径
private int[] edgeTo;
//起点
private int s;
//从起点到某个节点的最短路径
private int[] ord;
public ShortestPath(Graph graph, int s){
visited=new boolean[graph.V()];
edgeTo=new int[graph.V()];
ord=new int[graph.V()];
for(int i=0;i<graph.V();i++){
edgeTo[i]=-1;
}
this.s=s;
bfs(graph,this.s);
}
//广度优先搜索
private void bfs(Graph graph,int s){
visited[s]=true;
Queue<Integer> queue=new LinkedList<>();
queue.add(s);
while (!queue.isEmpty()){
int v=queue.poll();
for(int w:graph.adj(v)){
if(!visited[w]){
visited[w]=true;
edgeTo[w]=v;
ord[w]=ord[v]+1;
queue.add(w);
}
}
}
}
//是否有到顶点v的路径
private boolean hasPathTo(int v){
return visited[v];
}
//获取从 s->v的路径
public Iterable<Integer> pathTo(int v){
if(!hasPathTo(v)){
return null;
}
Stack<Integer> path=new Stack<>();
for(int i=v;i!=s;i=edgeTo[i]){
path.push(i);
}
path.push(s);
return path;
}
public void showPath(int v){
Stack<Integer> path= (Stack<Integer>) pathTo(v);
StringBuffer sb=new StringBuffer();
sb.append("[");
while(!path.isEmpty()){
int w=path.peek();
if(path.size()==1){
sb.append(w);
path.pop();
}else{
sb.append(w+"-->");
path.pop();
}
}
sb.append("]");
System.out.println(sb.toString());
}
//s-->v 的最短距离
public int getLength(int v){
return ord[v];
}
}public class Edge<E extends Number & Comparable> implements Comparable<Edge>{
//定义改变的起始节点和终止节点
private int from;
private int to;
//该边的权值
private E weight;
public Edge(int v, int w, E weight)
{
this.from = v;
this.to = w;
this.weight = weight;
}
public Edge(Edge<E> e)
{
this.from = e.from;
this.to = e.to;
this.weight = e.weight;
}
//获取起点
public int v(){
return from;
}
//获取终点
public int w(){
return to;
}
//获取权值
public E wt(){
return weight;
}
// 给定一个顶点, 返回另一个顶点
public int other(int x){
assert x == from || x == to;
return x == from ? to : from;
}
//输出边的具体信息
@Override
public String toString() {
return "" + from + "-" + to + ": " + weight;
}
@Override
public int compareTo(Edge that) {
int num=weight.compareTo(that.wt());
return num;
}
}// 带权图的接口
public interface WeightedGraph<E extends Number & Comparable> {
public int V();
public int E();
public void addEdge(Edge<E> edge);
boolean hasEdge(int v, int w);
void show();
public Iterable<Edge<E>> adj(int v);
}public class DenseWeightedGraph<E extends Number & Comparable> implements WeightedGraph<E>{
private int n; // 节点数
private int m; // 边数
private boolean directed; // 是否为有向图
private Edge[][] g; // 图的具体数据
// 构造函数
public DenseWeightedGraph(int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0; // 初始化没有任何边
//false表示无向图
this.directed = directed;
// g初始化为n*n的有向边矩阵
g = new Edge[n][n];
}
@Override
public int V(){ return n;} // 返回节点个数
@Override
public int E(){ return m;} // 返回边的个数
// 向图中添加一个边
@Override
public void addEdge(Edge edge){
assert edge.v() >= 0 && edge.v() < n ;
assert edge.w() >= 0 && edge.w() < n ;
if( hasEdge( edge.v() , edge.w() ) ){
return;
}
g[edge.v()][edge.w()] = new Edge(edge);
if( edge.v() != edge.w() && !directed ){
g[edge.w()][edge.v()] = new Edge(edge.w(), edge.v(), edge.wt());
}
m ++;
}
// 验证图中是否有从v到w的边
@Override
public boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
return g[v][w]!=null;
}
@Override
public void show() {
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(g[i][j]!=null){
System.out.print(g[i][j].wt()+"\t");
}else{
System.out.print("NULL\t");
}
}
System.out.println();
}
}
// 返回图中一个顶点的所有邻边
// 由于java使用引用机制，返回一个Vector不会带来额外开销
@Override
public Iterable<Edge<E>> adj(int v) {
assert v >= 0 && v < n;
Vector<Edge<E>> adjV = new Vector<>();
for (int i = 0; i < n; i++) {
if (g[v][i]!=null) {
adjV.add(g[v][i]);
}
}
return adjV;
}
}public class SparseWeightedGraph<E extends Number & Comparable> implements WeightedGraph<E>{
private int n; // 节点数
private int m; // 边数
private boolean directed; // 是否为有向图
private Vector<Edge<E>>[] g; // 图的具体数据
// 构造函数
public SparseWeightedGraph(int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0; // 初始化没有任何边
this.directed = directed;
// g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
g = (Vector<Edge<E>>[])new Vector[n];
for(int i = 0 ; i < n ; i ++){
g[i] = new Vector<Edge<E>>();
}
}
@Override
public int V(){ return n;} // 返回节点个数
@Override
public int E(){ return m;} // 返回边的个数
// 向图中添加一个边
@Override
public void addEdge(Edge edge){
assert edge.v() >= 0 && edge.v() < n ;
assert edge.w() >= 0 && edge.w() < n ;
g[edge.v()].add(edge);
if( edge.v() != edge.w() && !directed ){
g[edge.w()].add(new Edge(edge.w(),edge.v(),edge.wt()));
}
m ++;
}
// 验证图中是否有从v到w的边 -->时间复杂度：O(n)
@Override
public boolean hasEdge(int v, int w){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
for( int i = 0 ; i < g[v].size() ; i ++ ){
if( g[v].elementAt(i).other(v) == w ){
return true;
}
}
return false;
}
@Override
public void show() {
for( int i = 0 ; i < n ; i ++ ){
System.out.print("vertex " + i + ":\t");
for( int j = 0 ; j < g[i].size() ; j ++ ){
Edge e = g[i].elementAt(j);
System.out.print( "( to:" + e.other(i) + ",wt:" + e.wt() + ")\t");
}
System.out.println();
}
}
// 返回图中一个顶点的所有邻边
// 由于java使用引用机制，返回一个Vector不会带来额外开销
@Override
public Iterable<Edge<E>> adj(int v) {
assert v >= 0 && v < n;
return g[v];
}
}最小生成树问题针对的是带权无向图，并且该图是一个连通图。
切分定理
1.切分
把图中的的顶点分成两部分，成为一个切分。
其中图中顶点被分为蓝色部分和红色部分，这就是一个切分。
2.横切边
如果一个边的两个端点，分别属于不同的切分，则这个边就被成为横切边
其中使用绿色标出了横切边。
3.切分定理
给定任意切分，横切边中权值最小边必然属于最小生成树
在这个切分中横切边中权值最小的是0.16，已使用红色标出。
在这个切分中横切边中权值最小的是0.4，已使用红色标出。
public class LazyPrimMST<E extends Number & Comparable> {
private WeightedGraph<E> G; // 图的引用
private PriorityQueue<Edge<E>> pq; // 最小堆, -->Java默认使用小根堆
private boolean[] marked; // 标记数组, 在算法运行过程中标记节点i是否被访问
private Vector<Edge<E>> mst; // 最小生成树所包含的所有边
private Number mstWeight; // 最小生成树的权值
public LazyPrimMST(WeightedGraph graph){
this.G=graph;
pq=new PriorityQueue<>();
marked=new boolean[graph.V()];
mst=new Vector<>();
//从0节点开始访问
visit(0);
while(!pq.isEmpty()){
//获取最小边
Edge<E> e=pq.poll();
//看看这条最小边是否是横切边
if(marked[e.v()]==marked[e.w()]){
continue;
}
//是横切边，说明就是MST的边
mst.add(e);
// 访问和这条边连接的还没有被访问过的节点
if(! marked[e.v()]){
visit(e.v());
}else{
visit(e.w());
}
//计算最小生成树的权值
mstWeight=mst.elementAt(0).wt();
for(int i=1;i<mst.size();i++){
mstWeight = mstWeight.doubleValue() + mst.elementAt(i).wt().doubleValue();
}
}
}
//v顶点是未访问过的
private void visit(int v){
assert !marked[v];
marked[v]=true;
//将与v节点相连的顶点边加入到堆中
for(Edge e:G.adj(v)){
if(!marked[e.other(v)]){
pq.add(e);
}
}
}
// 返回最小生成树的所有边
public Vector<Edge<E>> mstEdges(){
return mst;
}
// 返回最小生成树的权值
public Number result(){
return mstWeight;
}
}/**
* 优化的Prim算法求图的最小生成树
*/
public class PrimMST<E extends Number & Comparable> {
private WeightedGraph G; // 图的引用
private IndexMinHeap<E> ipq; // 最小索引堆, 算法辅助数据结构
private Edge<E>[] edgeTo; // 访问的点所对应的边, 算法辅助数据结构
private boolean[] marked; // 标记数组, 在算法运行过程中标记节点i是否被访问
private Vector<Edge<E>> mst; // 最小生成树所包含的所有边
private Number mstWeight; // 最小生成树的权值
public PrimMST(WeightedGraph graph){
G = graph;
assert( graph.E() >= 1 );
ipq = new IndexMinHeap<E>(graph.V());
// 算法初始化
marked = new boolean[G.V()];
edgeTo = new Edge[G.V()];
mst=new Vector<>();
//Lazy Prim算法的改进
visit(0);
while (!ipq.isEmpty()){
// 使用最小索引堆找出已经访问的边中权值最小的边
// 最小索引堆中存储的是点的索引, 通过点的索引找到相对应的边
int v=ipq.extractMinIndex();
assert( edgeTo[v] != null );
mst.add(edgeTo[v]);
visit(v);
}
//计算最小生成树的权值
mstWeight=mst.elementAt(0).wt();
for(int i=1;i<mst.size();i++){
mstWeight=mstWeight.doubleValue()+mst.elementAt(i).wt().doubleValue();
}
}
private void visit(int v){
assert !marked[v];
marked[v] = true;
// 将和节点v相连接的未访问的另一端点, 和与之相连接的边, 放入最小堆中
for(Object edge:G.adj(v)){
Edge<E> e=(Edge<E>)edge;
int w=e.other(v);
// 如果边的另一端点未被访问
if(!marked[w]){
if(edgeTo[w]==null){
//如果从没有考虑过这个端点, 直接将这个端点和与之相连接的边加入索引堆
//edgeTo[w] 表示访问w定点所对应的边<v,w>
edgeTo[w]=e;
ipq.insert(w,e.wt());
}else if(e.wt().compareTo(edgeTo[w].wt())<0){
//如果曾经考虑这个端点, 但现在的边比之前考虑的边更短, 则进行替换
edgeTo[w]=e;
ipq.change(w,e.wt());
}
}
}
}
// 返回最小生成树的所有边
Vector<Edge<E>> mstEdges(){
return mst;
}
// 返回最小生成树的权值
Number result(){
return mstWeight;
}
}public class KruskalMST<E extends Number & Comparable> {
private Vector<Edge<E>> mst; // 最小生成树所包含的所有边
private Number mstWeight; // 最小生成树的权值
public KruskalMST(WeightedGraph graph){
mst=new Vector<>();
// 将图中的所有边存放到一个最小堆中
PriorityQueue<Edge<E>> pq=new PriorityQueue<>(graph.E());
for(int i=0;i<graph.V();i++){
for(Object item:graph.adj(i)){
Edge<E> e=(Edge<E>)item;
if(e.w() <e.v()){ //由于是无向图，只要加入一条边就好了
pq.add(e);
}
}
}
//创建一个并查集, 来查看已经访问的节点的联通情况
UnionFind uf = new UnionFind(graph.V());
while (!pq.isEmpty() && mst.size()<graph.V()-1){
// 从最小堆中依次从小到大取出所有的边
Edge<E> e = pq.poll();
//如果该边的两个端点是联通的, 说明加入这条边将产生环, 扔掉这条边
if(uf.isConnected(e.w(),e.v())){
continue;
}
// 否则, 将这条边添加进最小生成树, 同时标记边的两个端点联通
mst.add(e);
uf.unionElements(e.w(),e.v());
}
// 计算最小生成树的权值
mstWeight = mst.elementAt(0).wt();
for( int i = 1 ; i < mst.size() ; i ++ ){
mstWeight = mstWeight.doubleValue() + mst.elementAt(i).wt().doubleValue();
}
}
// 返回最小生成树的所有边
Vector<Edge<E>> mstEdges(){
return mst;
}
// 返回最小生成树的权值
Number result(){
return mstWeight;
}
}| 算法 | 时间复杂度 |
|---|---|
| Lazy Prim | O(ElogE) |
| Prim | O(ElogV) |
| Kruskal | O(ElogE) |
前提：图中不能有负权边
图中的蓝色顶点表示已加入最短路径树。红色的边就是最短路径。
图的右方左部分是索引堆，右部分是distTo[v] (表示从源点到v的已知最短路径长度)。
Dijkstra算法思路 ：
将0顶点开始，将访问顶点1、2、3
到没有访问过的顶点的最短路径是2，也就是顶点2
从2开始，将访问1、3、4。
先访问顶点 1 ，则0->2->1的路径就为3，此时不需要考虑0->1权为5的边了。
访问 顶点 4 ，则 0->2->4的路径长为7。
访问 顶点 3，则 0->2->3的路径长为5，此时就不需要考虑0->3权为6的边了。
此时所能到达的最短路径是顶点1。
考虑顶点1的邻边，1->4的路径更小。
此时所能到达的最短路径是顶点4。
此时所能到达的最短路径是顶点3.
public class DijkstraSP<E extends Number & Comparable>{
private WeightedGraph G;
// 图的引用
private int s;
// 起始点
private Number[] distTo;
// distTo[i]存储从起始点s到顶点i的最短路径长度
private boolean[] marked;
// 标记数组, 在算法运行过程中标记节点i是否被访问
private Edge<E>[] from;
// from[i]记录最短路径中, 到达i点的边是哪一条
// 可以用来恢复整个最短路径
public DijkstraSP(WeightedGraph graph,int s){
this.G=graph;
this.s=s;
distTo=new Number[G.V()];
marked=new boolean[G.V()];
from=new Edge[G.V()];
//使用索引堆记录当前找到的到达每个顶点的最短距离 ---> Number类型
IndexMinHeap<E> indexMinHeap=new IndexMinHeap<>(G.V());
//初始化起始点
distTo[s] = 0.0;
from[s]=new Edge<E>(s,s,(E)((Number)0.0));
marked[s]=true;
indexMinHeap.insert(s,(E)distTo[s]);
while (!indexMinHeap.isEmpty()){
int v=indexMinHeap.extractMinIndex();
// distTo[v]就是s到v的最短距离
marked[v] = true;
for(Object item:G.adj(v)){
Edge<E> edge=(Edge<E>)item;
int w=edge.other(v);
//如果从s点到w点的最短路径还没有找到
if(!marked[w]){
// 如果w点以前没有访问过,
// 或者访问过, 但是通过当前的v点到w点距离更短, 则进行更新
if(from[w]==null ||
(distTo[v].doubleValue()+edge.wt().doubleValue() < distTo[w].doubleValue())){
distTo[w]=distTo[v].doubleValue()+edge.wt().doubleValue();
from[w]=edge;
if(indexMinHeap.contain(w)){
indexMinHeap.change(w,(E)distTo[w]);
}else{
indexMinHeap.insert(w,(E)distTo[w]);
}
}
}
}
}
}
//获取从s点到w点的最短路径长度
public Number shortestPathTo(int w){
assert hasPathTo(w);
return distTo[w];
}
// 判断从s点到w点是否联通
public boolean hasPathTo(int w){
assert w>=0 && w<G.V();
return marked[w];
}
//寻找从s到w的最短路径, 将整个路径经过的边存放在res中
public Vector<Edge<E>> shortestPath(int w){
assert hasPathTo(w);
//通过from数组逆向查找到从s到w的路径, 存放到栈中
Stack<Edge<E>> stack=new Stack<>();
Edge<E> e=from[w];
while (e.v()!=s){
stack.push(e);
e=from[e.v()];
}
//最后e.v()就是s,那么e这条边入栈
stack.push(e);
//从栈中依次取出元素, 获得顺序的从s到w的路径
Vector<Edge<E>> res=new Vector<>();
while (!stack.isEmpty()){
Edge<E> edge=stack.pop();
res.add(edge);
}
return res;
}
// 打印出从s点到w点的路径
public void showPath(int w){
assert hasPathTo(w);
Vector<Edge<E>> path = shortestPath(w);
for( int i = 0 ; i < path.size() ; i ++ ){
System.out.print( path.elementAt(i).v() + " -> ");
if( i == path.size()-1 ){
System.out.println(path.elementAt(i).w());
}
}
}
}顶点0、1、2构成了一个负权环。
显然，有负权环的图，没有最短路径。
如果一个图没有负权环，从一点到另外一点的最短路径， 最多经过所有的V个顶点，有(V-1)条边。 否则，存在顶点经过了两次，也就是说存在负权环。
- 对一个顶点的一次松弛操作，就是找到经过这个点的另外一条路径，多一条边，权值更小。
- 如果一个图没有负权环，从一个顶点到另外一个顶点的最短路径，最多经过所有的V个顶点，有(V-1)条边。
- 对所有的点进行(V-1)次松弛操作，理论上可以找到到其他所有点的最短路径。
- 如果还可以继续松弛，说明原图中有负权环。
public BellmanFordSP(WeightedGraph graph,int s){
this.G=graph;
this.s=s;
distTo=new Number[G.V()];
marked=new boolean[G.V()];
from=new Edge[G.V()];
// // 设置distTo[s] = 0, 并且让from[s]不为NULL, 表示初始s节点可达且距离为0
distTo[s] = 0.0;
from[s] = new Edge<E>(s, s, (E)(Number)(0.0));
// Bellman-Ford的过程
// 进行V-1次循环, 每一次循环求出从起点到其余所有点, 最多使用pass步可到达的最短距离
for(int pass=1;pass<G.V();pass++){
// 每次循环中对所有的边进行一遍松弛操作
// 遍历所有边的方式是先遍历所有的顶点, 然后遍历和所有顶点相邻的所有边
for(int i=0;i<G.V();i++){
for(Object item:G.adj(i)){
Edge<E> e=(Edge<E>)item;
// 对于每一个边首先判断e->v()可达
// 之后看如果e->w()以前没有到达过， 显然我们可以更新distTo[e->w()]
// 或者e->w()以前虽然到达过, 但是通过这个e我们可以获得一个更短的距离,
// 即可以进行一次松弛操作, 我们也可以更新distTo[e->w()]
if(from[e.v()]!=null &&
(from[e.w()]==null || distTo[e.v()].doubleValue()+e.wt().doubleValue()<distTo[e.w()].doubleValue())){
distTo[e.w()]=distTo[e.v()].doubleValue()+e.wt().doubleValue();
from[e.w()]=e;
}
}
}
}
}public class BellmanFordSP<E extends Number & Comparable> {
private WeightedGraph G;
// 图的引用
private int s;
// 起始点
private Number[] distTo;
// distTo[i]存储从起始点s到顶点i的最短路径长度
private boolean[] marked;
// 标记数组, 在算法运行过程中标记节点i是否被访问
private Edge<E>[] from;
// from[i]记录最短路径中, 到达i点的边是哪一条
// 可以用来恢复整个最短路径
private boolean hasNegativeCycle;
// 标记图中是否有负权环
public BellmanFordSP(WeightedGraph graph,int s){
this.G=graph;
this.s=s;
distTo=new Number[G.V()];
marked=new boolean[G.V()];
from=new Edge[G.V()];
// // 设置distTo[s] = 0, 并且让from[s]不为NULL, 表示初始s节点可达且距离为0
distTo[s] = 0.0;
from[s] = new Edge<E>(s, s, (E)(Number)(0.0));
// Bellman-Ford的过程
// 进行V-1次循环, 每一次循环求出从起点到其余所有点, 最多使用pass步可到达的最短距离
for(int pass=1;pass<G.V();pass++){
// 每次循环中对所有的边进行一遍松弛操作
// 遍历所有边的方式是先遍历所有的顶点, 然后遍历和所有顶点相邻的所有边
for(int i=0;i<G.V();i++){
for(Object item:G.adj(i)){
Edge<E> e=(Edge<E>)item;
// 对于每一个边首先判断e->v()可达
// 之后看如果e->w()以前没有到达过， 显然我们可以更新distTo[e->w()]
// 或者e->w()以前虽然到达过, 但是通过这个e我们可以获得一个更短的距离,
// 即可以进行一次松弛操作, 我们也可以更新distTo[e->w()]
if(from[e.v()]!=null &&
(from[e.w()]==null || distTo[e.v()].doubleValue()+e.wt().doubleValue()<distTo[e.w()].doubleValue())){
distTo[e.w()]=distTo[e.v()].doubleValue()+e.wt().doubleValue();
from[e.w()]=e;
}
}
}
}
hasNegativeCycle = detectNegativeCycle();
}
// 判断图中是否有负权环
boolean detectNegativeCycle(){
for( int i = 0 ; i < G.V() ; i ++ ){
for( Object item : G.adj(i) ){
Edge<E> e = (Edge<E>)item;
if( from[e.v()] != null && distTo[e.v()].doubleValue() + e.wt().doubleValue() < distTo[e.w()].doubleValue() ){
return true;
}
}
}
return false;
}
// 返回图中是否有负权环
boolean negativeCycle(){
return hasNegativeCycle;
}
// 返回从s点到w点的最短路径长度
Number shortestPathTo( int w ){
assert w >= 0 && w < G.V();
assert !hasNegativeCycle;
assert hasPathTo(w);
return distTo[w];
}
// 判断从s点到w点是否联通
boolean hasPathTo( int w ){
assert( w >= 0 && w < G.V() );
return from[w] != null;
}
// 寻找从s到w的最短路径, 将整个路径经过的边存放在vec中
Vector<Edge<E>> shortestPath(int w){
assert w >= 0 && w < G.V() ;
assert !hasNegativeCycle ;
assert hasPathTo(w) ;
// 通过from数组逆向查找到从s到w的路径, 存放到栈中
Stack<Edge<E>> s = new Stack<Edge<E>>();
Edge<E> e = from[w];
while( e.v() != this.s ){
s.push(e);
e = from[e.v()];
}
s.push(e);
// 从栈中依次取出元素, 获得顺序的从s到w的路径
Vector<Edge<E>> res = new Vector<Edge<E>>();
while( !s.empty() ){
e = s.pop();
res.add(e);
}
return res;
}
// 打印出从s点到w点的路径
void showPath(int w){
assert( w >= 0 && w < G.V() );
assert( !hasNegativeCycle );
assert( hasPathTo(w) );
Vector<Edge<E>> res = shortestPath(w);
for( int i = 0 ; i < res.size() ; i ++ ){
System.out.print(res.elementAt(i).v() + " -> ");
if( i == res.size()-1 ){
System.out.println(res.elementAt(i).w());
}
}
}
}拓扑排序，是指将有向无环图的所有顶点以线性的方式进行排序。使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。 通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
例如下图所示，其拓扑序列的一种为：(5, 4, 0, 1, 2, 3)
每次从该集合中取出(没有特殊的取出规则，随机取出也行，使用队列/栈也行，下同)一个顶点，将该顶点放入保存结果的序列中。
紧接着循环遍历由该顶点引出的所有边，从图中移除这条边，同时获取该边的另外一个顶点，如果该顶点的入度在减去本条边之后为0，那么也将这个顶点放到入度为0的集合中。然后继续从集合中取出一个顶点，直到该集合为空。
当集合为空之后，检查图中是否还存在任何边，如果存在的话，说明图中至少存在一条环路。不存在的话则返回结果序列，此时就是对图进行拓扑排序的结果。
public class KahnTopologicalSort {
//拓扑序列
private List<Integer> order;
//入度为0的集合
private Queue<Integer> setOfZeroIndegree;
//存储每个节点的入度
private int[] indegrees;
private int edges;
private Digraph graph;
public KahnTopologicalSort(Digraph graph) {
this.graph = graph;
this.edges = graph.E();
this.indegrees = new int[graph.V()];
order = new ArrayList<>();
setOfZeroIndegree = new LinkedList<>();
//对入度为0的集合进行初始化
Vector<Integer>[] g = graph.getG();
//将邻接表中的每一条[a->b]中的b添加入度
for (int i = 0; i < g.length; i++) {
for (int j:g[i]){
indegrees[j]++;
}
}
for (int i = 0; i < indegrees.length; i++) {
if (indegrees[i]==0){
setOfZeroIndegree.offer(i);
}
}
generateOrder();
}
//生成拓扑序列
private void generateOrder(){
while (!setOfZeroIndegree.isEmpty()){
//从入度为0的集合中取出一个节点
Integer curNode = setOfZeroIndegree.poll();
order.add(curNode);
//遍历该节点的邻居节点
for (int i:graph.adj(curNode)){
edges--;
indegrees[i]--;
if (indegrees[i]==0){
setOfZeroIndegree.offer(i);
}
}
}
//说明没有遍历完所有节点，证明有环
if (edges!=0){
order=new ArrayList<>();
}
}
public List<Integer> getOrder(){
return order;
}
}使用DFS（深度优先遍历），需要使用到栈，用来存在遍历过的节点，因为越早遍历到的节点其前序依赖越少，作为拓扑序列其位置应该越靠前。对于任何先序关系：v->w，DFS可以保证 w 先进入栈中，因此栈的逆序结果中 v 会在 w 之前。
public class DfsTopologicalSort {
//拓扑序列
private List<Integer> order;
//入队序列需要逆序才是拓扑序列
private Stack<Integer> stack;
//标记各节点的状态
// -1：visited;0:none-visited;1:visiting
private int[] flag;
private Digraph graph;
public DfsTopologicalSort(Digraph graph) {
this.graph = graph;
order=new ArrayList<>();
stack=new Stack<>();
flag=new int[graph.V()];
//生成拓扑序列
for (int i = 0; i < graph.V(); i++) {
if (dfs(graph,i)){
order.clear();
}
}
while (!stack.empty()){
order.add(stack.pop());
}
}
/**
* 深度优先遍历
* @param graph
* @param curNode
* @return 是否存在环路
*/
private boolean dfs(Digraph graph,int curNode){
//此时说明存在环路
if (flag[curNode]==1){
return true;
}
//当前的节点已被遍历过
if (flag[curNode]==-1){
return false;
}
flag[curNode]=1;
//继续遍历当前节点的邻居节点
for (int i:graph.adj(curNode)){
if (dfs(graph,i)){
return true;
}
}
stack.push(curNode);
flag[curNode]=-1;
return false;
}
public List<Integer> getOrder(){
return order;
}
}Kahn算法不需要检测图为DAG，如果图为DAG，那么在出度为0的集合为空之后，图中还存在没有被移除的边，这就说明了图中存在环路。而基于DFS的算法需要首先确定图为DAG，当然也能够做出适当调整，让环路的检测和拓扑排序同时进行，毕竟环路检测也能够在DFS的基础上进行。