Fork me on GitHub

数据结构-图论

图(graph)是由一些点(vertex)和这些点之间的连线(edge)所组成的;其中,点通常被成为”顶点(vertex)”,而点与点之间的连线则被成为”边或弧”(edege).通常记为,G=(V,E).

根据边是否有方向,将图可以划分为:无向图有向图.

一条边上的两个顶点叫做邻接点.

有向图中,除了邻接点之外;还有”入边”和”出边”的概念.
顶点的入边,是指以该顶点为终点的边.而顶点的出边,则是指以该顶点为起点的边.

无向图中,某个顶点的度是邻接到该顶点的边(或弧)的数目.
例如,上面无向图G0中顶点A的度是2.

有向图中,度还有”入度”和”出度”之分.
某个顶点的入度,是指以该顶点为终点的边的数目.而顶点的出度,则是指以该顶点为起点的边的数目.
顶点的度=入度+出度.

路径:如果顶点(Vm)到顶点(Vn)之间存在一个顶点序列.则表示Vm到Vn是一条路径.
路径长度:路径中”边的数量”.
简单路径:若一条路径上顶点不重复出现,则是简单路径.
回路:若路径的第一个顶点和最后一个顶点相同,则是回路.
简单回路:第一个顶点和最后一个顶点相同,其它各顶点都不重复的回路则是简单回路.

连通图:对无向图而言,任意两个顶点之间都存在一条无向路径,则称该无向图为连通图. 对有向图而言,若图中任意两个顶点之间都存在一条有向路径,则称该有向图为强连通图.

连通分量:非连通图中的各个连通子图称为该图的连通分量.

图的存储

图的存储结构,常用的是”邻接矩阵”和”邻接表”.

邻接表法:对于每个图中的点,将它的邻居放到一个链表里
邻接矩阵:对于 n 个点,构造一个 n * n 的矩阵,如果有从点 i 到点 j 的边,就将矩阵的位置 matrix[i][j] 置为 1.

邻接矩阵表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

// 稠密图 - 邻接矩阵
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];
}
}

邻接表表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.util.Vector;

// 稀疏图 - 邻接表
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的边
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;
}
}

图的遍历

遍历图最常用的有两种方式,就是 BFS 和 DFS.

BFS: Breadth First Search,广度优先搜索
DFS: Depdth First Search,深度优先搜索

DFS

通过DFS来求连通分量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

// 求无权图的联通分量
public class Components {

Graph G; // 图的引用
private boolean[] visited; // 记录dfs的过程中节点是否被访问
private int ccount; // 记录联通分量个数
private int[] id; // 每个节点所对应的联通分量标记

// 图的深度优先遍历
void dfs( int v ){

visited[v] = true;
id[v] = ccount;

for( int i: G.adj(v) ){
if( !visited[i] )
dfs(i);
}
}

// 构造函数, 求出无权图的联通分量
public Components(Graph graph){

// 算法初始化
G = graph;
visited = new boolean[G.V()];
id = new int[G.V()];
ccount = 0;
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
id[i] = -1;
}

// 求图的联通分量
for( int i = 0 ; i < G.V() ; i ++ )
if( !visited[i] ){
dfs(i);
ccount ++;
}
}

// 返回图的联通分量个数
int count(){
return ccount;
}

// 查询点v和点w是否联通
boolean isConnected( int v , int w ){
assert v >= 0 && v < G.V();
assert w >= 0 && w < G.V();
return id[v] == id[w];
}
}

寻路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import java.util.Vector;
import java.util.Stack;

public class Path {

private Graph G; // 图的引用
private int s; // 起始点
private boolean[] visited; // 记录dfs的过程中节点是否被访问
private int[] from; // 记录路径, from[i]表示查找的路径上i的上一个节点

// 图的深度优先遍历
private void dfs( int v ){
visited[v] = true;
for( int i : G.adj(v) )
if( !visited[i] ){
from[i] = v;
dfs(i);
}
}

// 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
public Path(Graph graph, int s){

// 算法初始化
G = graph;
assert s >= 0 && s < G.V();

visited = new boolean[G.V()];
from = new int[G.V()];
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
from[i] = -1;
}
this.s = s;

// 寻路算法
dfs(s);
}

// 查询从s点到w点是否有路径
boolean hasPath(int w){
assert w >= 0 && w < G.V();
return visited[w];
}

// 查询从s点到w点的路径, 存放在vec中
Vector<Integer> path(int w){

assert hasPath(w) ;

Stack<Integer> s = new Stack<Integer>();
// 通过from数组逆向查找到从s到w的路径, 存放到栈中
int p = w;
while( p != -1 ){
s.push(p);
p = from[p];
}

// 从栈中依次取出元素, 获得顺序的从s到w的路径
Vector<Integer> res = new Vector<Integer>();
while( !s.empty() )
res.add( s.pop() );

return res;
}

// 打印出从s点到w点的路径
void showPath(int w){

assert hasPath(w) ;

Vector<Integer> vec = path(w);
for( int i = 0 ; i < vec.size() ; i ++ ){
System.out.print(vec.elementAt(i));
if( i == vec.size() - 1 )
System.out.println();
else
System.out.print(" -> ");
}
}
}

BFS

通过BFS来求最短路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
import java.util.Vector;
import java.util.Stack;
import java.util.LinkedList;

public class ShortestPath {

private Graph G; // 图的引用
private int s; // 起始点
private boolean[] visited; // 记录dfs的过程中节点是否被访问
private int[] from; // 记录路径, from[i]表示查找的路径上i的上一个节点
private int[] ord; // 记录路径中节点的次序.ord[i]表示i节点在路径中的次序.


// 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
public ShortestPath(Graph graph, int s){

// 算法初始化
G = graph;
assert s >= 0 && s < G.V();

visited = new boolean[G.V()];
from = new int[G.V()];
ord = new int[G.V()];
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
from[i] = -1;
ord[i] = -1;
}
this.s = s;

// 无向图最短路径算法, 从s开始广度优先遍历整张图
LinkedList<Integer> q = new LinkedList<Integer>();

q.push( s );
visited[s] = true;
ord[s] = 0;
while( !q.isEmpty() ){
int v = q.pop();
for( int i : G.adj(v) )
if( !visited[i] ){
q.push(i);
visited[i] = true;
from[i] = v;
ord[i] = ord[v] + 1;
}
}
}

// 查询从s点到w点是否有路径
public boolean hasPath(int w){
assert w >= 0 && w < G.V();
return visited[w];
}

// 查询从s点到w点的路径, 存放在vec中
public Vector<Integer> path(int w){

assert hasPath(w) ;

Stack<Integer> s = new Stack<Integer>();
// 通过from数组逆向查找到从s到w的路径, 存放到栈中
int p = w;
while( p != -1 ){
s.push(p);
p = from[p];
}

// 从栈中依次取出元素, 获得顺序的从s到w的路径
Vector<Integer> res = new Vector<Integer>();
while( !s.empty() )
res.add( s.pop() );

return res;
}

// 打印出从s点到w点的路径
public void showPath(int w){

assert hasPath(w) ;

Vector<Integer> vec = path(w);
for( int i = 0 ; i < vec.size() ; i ++ ){
System.out.print(vec.elementAt(i));
if( i == vec.size() - 1 )
System.out.println();
else
System.out.print(" -> ");
}
}

// 查看从s点到w点的最短路径长度
// 若从s到w不可达,返回-1
public int length(int w){
assert w >= 0 && w < G.V();
return ord[w];
}
}

有权图

首先创建一个边类, 包含两个点的信息及权重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 边
public class Edge<Weight extends Number & Comparable> implements Comparable<Edge>{

private int a, b; // 边的两个端点
private Weight weight; // 边的权值

public Edge(int a, int b, Weight weight)
{
this.a = a;
this.b = b;
this.weight = weight;
}

public Edge(Edge<Weight> e)
{
this.a = e.a;
this.b = e.b;
this.weight = e.weight;
}

public int v(){ return a;} // 返回第一个顶点
public int w(){ return b;} // 返回第二个顶点
public Weight wt(){ return weight;} // 返回权值

// 给定一个顶点, 返回另一个顶点
public int other(int x){
assert x == a || x == b;
return x == a ? b : a;
}

// 输出边的信息
public String toString(){
return "" + a + "-" + b + ": " + weight;
}

// 边之间的比较
public int compareTo(Edge that)
{
if( weight.compareTo(that.wt()) < 0 )
return -1;
else if ( weight.compareTo(that.wt()) > 0 )
return +1;
else
return 0;
}
}

邻接矩阵表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.util.Vector;

// 稠密图 - 邻接矩阵
public class DenseWeightedGraph<Weight extends Number & Comparable>
implements WeightedGraph{

private int n; // 节点数
private int m; // 边数
private boolean directed; // 是否为有向图
private Edge<Weight>[][] g; // 图的具体数据

// 构造函数
public DenseWeightedGraph( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0; // 初始化没有任何边
this.directed = directed;
// g初始化为n*n的布尔矩阵, 每一个g[i][j]均为null, 表示没有任和边
// false为boolean型变量的默认值
g = new Edge[n][n];
for(int i = 0 ; i < n ; i ++)
for(int j = 0 ; j < n ; j ++)
g[i][j] = null;
}

public int V(){ return n;} // 返回节点个数
public int E(){ return m;} // 返回边的个数

// 向图中添加一个边
public void addEdge(Edge e){

assert e.v() >= 0 && e.v() < n ;
assert e.w() >= 0 && e.w() < n ;

if( hasEdge( e.v() , e.w() ) )
return;

g[e.v()][e.w()] = new Edge(e);
if( e.v() != e.w() && !directed )
g[e.w()][e.v()] = new Edge(e.w(), e.v(), e.wt());

m ++;
}

// 验证图中是否有从v到w的边
public boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
return g[v][w] != null;
}

// 显示图的信息
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();
}
}

// 返回图中一个顶点的所有邻边
public Iterable<Edge<Weight>> adj(int v) {
assert v >= 0 && v < n;
Vector<Edge<Weight>> adjV = new Vector<Edge<Weight>>();
for(int i = 0 ; i < n ; i ++ )
if( g[v][i] != null )
adjV.add( g[v][i] );
return adjV;
}
}

邻接表表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.util.Vector;

// 稀疏图 - 邻接表
public class SparseWeightedGraph<Weight extends Number & Comparable>
implements WeightedGraph {

private int n; // 节点数
private int m; // 边数
private boolean directed; // 是否为有向图
private Vector<Edge<Weight>>[] 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<Weight>>[])new Vector[n];
for(int i = 0 ; i < n ; i ++)
g[i] = new Vector<Edge<Weight>>();
}

public int V(){ return n;} // 返回节点个数
public int E(){ return m;} // 返回边的个数

// 向图中添加一个边, 权值为weight
public void addEdge(Edge e){

assert e.v() >= 0 && e.v() < n ;
assert e.w() >= 0 && e.w() < n ;

// 注意, 由于在邻接表的情况, 查找是否有重边需要遍历整个链表
// 我们的程序允许重边的出现

g[e.v()].add(new Edge(e));
if( e.v() != e.w() && !directed )
g[e.w()].add(new Edge(e.w(), e.v(), e.wt()));

m ++;
}

// 验证图中是否有从v到w的边
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;
}

// 显示图的信息
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();
}
}

// 返回图中一个顶点的所有邻边
public Iterable<Edge<Weight>> adj(int v) {
assert v >= 0 && v < n;
return g[v];
}
}

最小生成树

https://zh.wikipedia.org/wiki/最小生成树

最小生成树其实是最小权重生成树的简称.

一个连通图可能有多个生成树.当图中的边具有权值时,总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和.广义上而言,对于非连通无向图来说,它的每一连通分量同样有最小生成树,它们的并被称为最小生成森林.

以有线电视电缆的架设为例,若只能沿着街道布线,则以街道为边,而路口为顶点,其中必然有一最小生成树能使布线成本最低.

Prim算法

https://zh.wikipedia.org/wiki/普林姆算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.util.Vector;

// 使用Prim算法求图的最小生成树
public class LazyPrimMST<Weight extends Number & Comparable> {

private WeightedGraph<Weight> G; // 图的引用
private MinHeap<Edge<Weight>> pq; // 最小堆, 算法辅助数据结构
private boolean[] marked; // 标记数组, 在算法运行过程中标记节点i是否被访问
private Vector<Edge<Weight>> mst; // 最小生成树所包含的所有边
private Number mstWeight; // 最小生成树的权值

// 构造函数, 使用Prim算法求图的最小生成树
public LazyPrimMST(WeightedGraph<Weight> graph){

// 算法初始化
G = graph;
pq = new MinHeap<Edge<Weight>>(G.E());
marked = new boolean[G.V()];
mst = new Vector<Edge<Weight>>();

// Lazy Prim
visit(0);
while( !pq.isEmpty() ){
// 使用最小堆找出已经访问的边中权值最小的边
Edge<Weight> e = pq.extractMin();
// 如果这条边的两端都已经访问过了, 则扔掉这条边
if( marked[e.v()] == marked[e.w()] )
continue;
// 否则, 这条边则应该存在在最小生成树中
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<Weight> e : G.adj(v) )
if( !marked[e.other(v)] )
pq.insert(e);
}

// 返回最小生成树的所有边
Vector<Edge<Weight>> mstEdges(){
return mst;
}

// 返回最小生成树的权值
Number result(){
return mstWeight;
}


// 测试 Lazy Prim
public static void main(String[] args) {

String filename = "testG3.txt";
int V = 8;

SparseWeightedGraph<Double> g = new SparseWeightedGraph<Double>(V, false);
ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);

// Test Lazy Prim MST
System.out.println("Test Lazy Prim MST:");
LazyPrimMST<Double> lazyPrimMST = new LazyPrimMST<Double>(g);
Vector<Edge<Double>> mst = lazyPrimMST.mstEdges();
for( int i = 0 ; i < mst.size() ; i ++ )
System.out.println(mst.elementAt(i));
System.out.println("The MST weight is: " + lazyPrimMST.result());

System.out.println();
}
}

Kruskal

https://zh.wikipedia.org/wiki/克鲁斯克尔演算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.util.Vector;

// Kruskal算法求最小生成树
public class KruskalMST<Weight extends Number & Comparable> {

private Vector<Edge<Weight>> mst; // 最小生成树所包含的所有边
private Number mstWeight; // 最小生成树的权值

// 构造函数, 使用Kruskal算法计算graph的最小生成树
public KruskalMST(WeightedGraph graph){

mst = new Vector<Edge<Weight>>();

// 将图中的所有边存放到一个最小堆中
MinHeap<Edge<Weight>> pq = new MinHeap<Edge<Weight>>( graph.E() );
for( int i = 0 ; i < graph.V() ; i ++ )
for( Object item : graph.adj(i) ){
Edge<Weight> e = (Edge<Weight>)item;
if( e.v() <= e.w() )
pq.insert(e);
}

// 创建一个并查集, 来查看已经访问的节点的联通情况
UnionFind uf = new UnionFind(graph.V());
while( !pq.isEmpty() && mst.size() < graph.V() - 1 ){

// 从最小堆中依次从小到大取出所有的边
Edge<Weight> e = pq.extractMin();
// 如果该边的两个端点是联通的, 说明加入这条边将产生环, 扔掉这条边
if( uf.isConnected( e.v() , e.w() ) )
continue;

// 否则, 将这条边添加进最小生成树, 同时标记边的两个端点联通
mst.add( e );
uf.unionElements( e.v() , e.w() );
}

// 计算最小生成树的权值
mstWeight = mst.elementAt(0).wt();
for( int i = 1 ; i < mst.size() ; i ++ )
mstWeight = mstWeight.doubleValue() + mst.elementAt(i).wt().doubleValue();
}

// 返回最小生成树的所有边
Vector<Edge<Weight>> mstEdges(){
return mst;
}

// 返回最小生成树的权值
Number result(){
return mstWeight;
}


// 测试 Kruskal
public static void main(String[] args) {

String filename = "testG3.txt";
int V = 8;

SparseWeightedGraph<Double> g = new SparseWeightedGraph<Double>(V, false);
ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);

// Test Kruskal
System.out.println("Test Kruskal:");
KruskalMST<Double> kruskalMST = new KruskalMST<Double>(g);
Vector<Edge<Double>> mst = kruskalMST.mstEdges();
for( int i = 0 ; i < mst.size() ; i ++ )
System.out.println(mst.elementAt(i));
System.out.println("The MST weight is: " + kruskalMST.result());

System.out.println();
}
}

最短路径

https://zh.wikipedia.org/wiki/最短路问题

Dijkstra

https://zh.wikipedia.org/wiki/戴克斯特拉算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
import java.util.Stack;
import java.util.Vector;

// Dijkstra算法求最短路径
public class Dijkstra<Weight extends Number & Comparable> {

private WeightedGraph G; // 图的引用
private int s; // 起始点
private Number[] distTo; // distTo[i]存储从起始点s到i的最短路径长度
private boolean[] marked; // 标记数组, 在算法运行过程中标记节点i是否被访问
private Edge<Weight>[] from; // from[i]记录最短路径中, 到达i点的边是哪一条
// 可以用来恢复整个最短路径

// 构造函数, 使用Dijkstra算法求最短路径
public Dijkstra(WeightedGraph graph, int s){

// 算法初始化
G = graph;
assert s >= 0 && s < G.V();
this.s = s;
distTo = new Number[G.V()];
marked = new boolean[G.V()];
from = new Edge[G.V()];
for( int i = 0 ; i < G.V() ; i ++ ){
distTo[i] = 0.0;
marked[i] = false;
from[i] = null;
}

// 使用索引堆记录当前找到的到达每个顶点的最短距离
IndexMinHeap<Weight> ipq = new IndexMinHeap<Weight>(G.V());

// 对于其实点s进行初始化
distTo[s] = 0.0;
from[s] = new Edge<Weight>(s, s, (Weight)(Number)(0.0));
ipq.insert(s, (Weight)distTo[s] );
marked[s] = true;
while( !ipq.isEmpty() ){
int v = ipq.extractMinIndex();

// distTo[v]就是s到v的最短距离
marked[v] = true;

// 对v的所有相邻节点进行更新
for( Object item : G.adj(v) ){
Edge<Weight> e = (Edge<Weight>)item;
int w = e.other(v);
// 如果从s点到w点的最短路径还没有找到
if( !marked[w] ){
// 如果w点以前没有访问过,
// 或者访问过, 但是通过当前的v点到w点距离更短, 则进行更新
if( from[w] == null || distTo[v].doubleValue() + e.wt().doubleValue() < distTo[w].doubleValue() ){
distTo[w] = distTo[v].doubleValue() + e.wt().doubleValue();
from[w] = e;
if( ipq.contain(w) )
ipq.change(w, (Weight)distTo[w] );
else
ipq.insert(w, (Weight)distTo[w] );
}
}
}
}
}

// 返回从s点到w点的最短路径长度
Number shortestPathTo( int w ){
assert w >= 0 && w < G.V();
assert hasPathTo(w);
return distTo[w];
}

// 判断从s点到w点是否联通
boolean hasPathTo( int w ){
assert w >= 0 && w < G.V() ;
return marked[w];
}

// 寻找从s到w的最短路径, 将整个路径经过的边存放在vec中
Vector<Edge<Weight>> shortestPath(int w){

assert w >= 0 && w < G.V();
assert hasPathTo(w);

// 通过from数组逆向查找到从s到w的路径, 存放到栈中
Stack<Edge<Weight>> s = new Stack<Edge<Weight>>();
Edge<Weight> e = from[w];
while( e.v() != this.s ){
s.push(e);
e = from[e.v()];
}
s.push(e);

// 从栈中依次取出元素, 获得顺序的从s到w的路径
Vector<Edge<Weight>> res = new Vector<Edge<Weight>>();
while( !s.empty() ){
e = s.pop();
res.add( e );
}

return res;
}

// 打印出从s点到w点的路径
void showPath(int w){

assert w >= 0 && w < G.V();
assert hasPathTo(w);

Vector<Edge<Weight>> 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%