圖分為有向圖邑贴，和無(wú)向圖迄沫。
如果圖的邊數(shù)接近頂點(diǎn)數(shù)其為稠密圖
如果圖的邊數(shù)遠(yuǎn)遠(yuǎn)小于頂點(diǎn)數(shù)其為稀疏圖
表示稠密圖一般采用鄰接矩陣的方法
package bobo.algo;
import java.util.Vector;
// 稠密圖 - 鄰接矩陣
public class DenseGraphimplements Graph{
private int n;? // 節(jié)點(diǎn)數(shù)
? ? private int m;? // 邊數(shù)
? ? private boolean directed;? // 是否為有向圖
? ? private boolean[][] g;? ? ? // 圖的具體數(shù)據(jù)
? ? // 構(gòu)造函數(shù)
? ? public DenseGraph(int n, boolean directed ){
assert n >=0;
? ? ? ? this.n = n;
? ? ? ? this.m =0;? ? // 初始化沒(méi)有任何邊
? ? ? ? this.directed = directed;
? ? ? ? // g初始化為n*n的布爾矩陣, 每一個(gè)g[i][j]均為false, 表示沒(méi)有任和邊
? ? ? ? // false為boolean型變量的默認(rèn)值
? ? ? ? g =new boolean[n][n];
? ? }
public int V(){return n;}// 返回節(jié)點(diǎn)個(gè)數(shù)
? ? public int E(){return m;}// 返回邊的個(gè)數(shù)
? ? // 向圖中添加一個(gè)邊
? ? 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 ++;
? ? }
// 驗(yàn)證圖中是否有從v到w的邊
? ? public boolean hasEdge(int v, int w ){
assert v >=0 && v < n;
? ? ? ? assert w >=0 && w < n;
? ? ? ? return g[v][w];
? ? }
// 顯示圖的信息
? ? public void show(){
for(int i =0 ; i < n; i ++ ){
for(int j =0 ; j < n; j ++ )
System.out.print(g[i][j]+"\t");
? ? ? ? ? ? System.out.println();
? ? ? ? }
}
// 返回圖中一個(gè)頂點(diǎn)的所有鄰邊
? ? // 由于java使用引用機(jī)制，返回一個(gè)Vector不會(huì)帶來(lái)額外開(kāi)銷,
? ? public Iterable adj(int v) {
assert v >=0 && v < n;
? ? ? ? Vector adjV =new Vector();
? ? ? ? for(int i =0 ; i < n; i ++ )
if( g[v][i] )
adjV.add(i);
? ? ? ? return adjV;
? ? }
}
表示稀疏圖一般采用鄰接表的方法害驹。
package bobo.algo;
import java.util.Vector;
// 稀疏圖 - 鄰接表
public class SparseGraphimplements Graph {
private int n;? // 節(jié)點(diǎn)數(shù)
? ? private int m;? // 邊數(shù)
? ? private boolean directed;? // 是否為有向圖
? ? private Vector[] g; // 圖的具體數(shù)據(jù)
? ? // 構(gòu)造函數(shù)
? ? public SparseGraph(int n, boolean directed ){
assert n >=0;
? ? ? ? this.n = n;
? ? ? ? this.m =0;? ? // 初始化沒(méi)有任何邊
? ? ? ? this.directed = directed;
? ? ? ? // g初始化為n個(gè)空的vector, 表示每一個(gè)g[i]都為空, 即沒(méi)有任和邊
? ? ? ? g = (Vector[])new Vector[n];
? ? ? ? for(int i =0 ; i < n; i ++)
g[i] =new Vector();
? ? }
public int V(){return n;}// 返回節(jié)點(diǎn)個(gè)數(shù)
? ? public int E(){return m;}// 返回邊的個(gè)數(shù)
? ? // 向圖中添加一個(gè)邊
? ? 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 ++;
? ? }
// 驗(yàn)證圖中是否有從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) == 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 ++ )
System.out.print(g[i].elementAt(j) +"\t");
? ? ? ? ? ? System.out.println();
? ? ? ? }
}
// 返回圖中一個(gè)頂點(diǎn)的所有鄰邊
? ? // 由于java使用引用機(jī)制柑蛇，返回一個(gè)Vector不會(huì)帶來(lái)額外開(kāi)銷,
? ? public Iterable adj(int v) {
assert v >=0 && v < n;
? ? ? ? return g[v];
? ? }
}
圖的深度優(yōu)先遍歷
從0開(kāi)始，遍歷1棋弥，再遍歷1的子節(jié)點(diǎn)0，發(fā)現(xiàn)已遍歷完子節(jié)點(diǎn)退回到上層诚欠，遍歷2顽染，遍歷0漾岳，發(fā)現(xiàn)遍歷完了，再遍歷5粉寞，遍歷 0發(fā)現(xiàn)已經(jīng)遍歷換下一個(gè)尼荆，3，遍歷3的子節(jié)點(diǎn)4唧垦，遍歷4的子節(jié)點(diǎn)3捅儒，5，6振亮，以此類推
聯(lián)通分量
聯(lián)通分量之間沒(méi)有節(jié)點(diǎn)相連
深度優(yōu)先遍歷能遍歷完一個(gè)聯(lián)通分量
求聯(lián)通分量和深度遍歷
package bobo.algo;
// 求無(wú)權(quán)圖的聯(lián)通分量
public class Components {
Graph G;? ? ? ? ? ? ? ? ? ? // 圖的引用
? ? private boolean[] visited;? // 記錄dfs的過(guò)程中節(jié)點(diǎn)是否被訪問(wèn)
? ? private int ccount;? ? ? ? // 記錄聯(lián)通分量個(gè)數(shù)
? ? private int[] id;? ? ? ? ? // 每個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的聯(lián)通分量標(biāo)記
? ? // 圖的深度優(yōu)先遍歷
? ? void dfs(int v ){
visited[v] =true;
? ? ? ? id[v] = ccount;
? ? ? ? for(int i: G.adj(v) ){
if( !visited[i] )
dfs(i);
? ? ? ? }
}
// 構(gòu)造函數(shù), 求出無(wú)權(quán)圖的聯(lián)通分量
? ? 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;
? ? ? ? }
// 求圖的聯(lián)通分量
? ? ? ? for(int i =0 ; i < G.V(); i ++ )
if( !visited[i] ){
dfs(i);
? ? ? ? ? ? ? ? ccount ++;
? ? ? ? ? ? }
}
// 返回圖的聯(lián)通分量個(gè)數(shù)
? ? int count(){
return ccount;
? ? }
// 查詢點(diǎn)v和點(diǎn)w是否聯(lián)通
? ? boolean isConnected(int v, int w ){
assert v >=0 && v < G.V();
? ? ? ? assert w >=0 && w < G.V();
? ? ? ? return id[v] == id[w];
? ? }
}
找出兩點(diǎn)之間的路徑一般是在深度遍歷時(shí)記錄上一個(gè)點(diǎn)的位置即可
package bobo.algo;
import java.util.Vector;
import java.util.Stack;
public class Path {
private Graph G;? // 圖的引用
? ? private int s;? ? // 起始點(diǎn)
? ? private boolean[] visited;? // 記錄dfs的過(guò)程中節(jié)點(diǎn)是否被訪問(wèn)
? ? private int[] from;? ? ? ? // 記錄路徑, from[i]表示查找的路徑上i的上一個(gè)節(jié)點(diǎn)
? ? // 圖的深度優(yōu)先遍歷
? ? private void dfs(int v ){
visited[v] =true;
? ? ? ? for(int i : G.adj(v) )
if( !visited[i] ){
from[i] = v;
? ? ? ? ? ? ? ? dfs(i);
? ? ? ? ? ? }
}
// 構(gòu)造函數(shù), 尋路算法, 尋找圖graph從s點(diǎn)到其他點(diǎn)的路徑
? ? 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點(diǎn)到w點(diǎn)是否有路徑
? ? boolean hasPath(int w){
assert w >=0 && w < G.V();
? ? ? ? return visited[w];
? ? }
// 查詢從s點(diǎn)到w點(diǎn)的路徑, 存放在vec中
? ? Vector path(int w){
assert hasPath(w);
? ? ? ? Stack s =new Stack();
? ? ? ? // 通過(guò)from數(shù)組逆向查找到從s到w的路徑, 存放到棧中
? ? ? ? int p = w;
? ? ? ? while( p != -1 ){
s.push(p);
? ? ? ? ? ? p = from[p];
? ? ? ? }
// 從棧中依次取出元素, 獲得順序的從s到w的路徑
? ? ? ? Vector res =new Vector();
? ? ? ? while( !s.empty() )
res.add( s.pop() );
? ? ? ? return res;
? ? }
// 打印出從s點(diǎn)到w點(diǎn)的路徑
? ? void showPath(int w){
assert hasPath(w);
? ? ? ? Vector 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(" -> ");
? ? ? ? }
}
}
倆點(diǎn)之間的最短路徑（無(wú)權(quán)圖）
用廣度遍歷巧还，先遍歷其所有子節(jié)點(diǎn)，第一個(gè)子節(jié)點(diǎn)的子節(jié)點(diǎn)入棧坊秸，第二個(gè)子節(jié)點(diǎn)的子結(jié)點(diǎn)再入棧麸祷，以此類推，到第一個(gè)子節(jié)點(diǎn)的子節(jié)點(diǎn)的子節(jié)點(diǎn)入賬即可
package bobo.algo;
import java.util.Vector;
import java.util.Stack;
import java.util.LinkedList;
import java.util.Queue;
public class ShortestPath {
private Graph G;? // 圖的引用
? ? private int s;? ? // 起始點(diǎn)
? ? private boolean[] visited;? // 記錄dfs的過(guò)程中節(jié)點(diǎn)是否被訪問(wèn)
? ? private int[] from;? ? ? ? // 記錄路徑, from[i]表示查找的路徑上i的上一個(gè)節(jié)點(diǎn)
? ? private int[] ord;? ? ? ? ? // 記錄路徑中節(jié)點(diǎn)的次序妇斤。ord[i]表示i節(jié)點(diǎn)在路徑中的次序摇锋。
? ? // 構(gòu)造函數(shù), 尋路算法, 尋找圖graph從s點(diǎn)到其他點(diǎn)的路徑
? ? 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;
? ? ? ? // 無(wú)向圖最短路徑算法, 從s開(kāi)始廣度優(yōu)先遍歷整張圖
? ? ? ? Queue q =new LinkedList();
? ? ? ? q.add(s);
? ? ? ? visited[s] =true;
? ? ? ? ord[s] =0;
? ? ? ? while( !q.isEmpty() ){
int v = q.remove();
? ? ? ? ? ? for(int i : G.adj(v) )
if( !visited[i] ){
q.add(i);
? ? ? ? ? ? ? ? ? ? visited[i] =true;
? ? ? ? ? ? ? ? ? ? from[i] = v;
? ? ? ? ? ? ? ? ? ? ord[i] = ord[v] +1;
? ? ? ? ? ? ? ? }
}
}
// 查詢從s點(diǎn)到w點(diǎn)是否有路徑
? ? public boolean hasPath(int w){
assert w >=0 && w < G.V();
? ? ? ? return visited[w];
? ? }
// 查詢從s點(diǎn)到w點(diǎn)的路徑, 存放在vec中
? ? public Vector path(int w){
assert hasPath(w);
? ? ? ? Stack s =new Stack();
? ? ? ? // 通過(guò)from數(shù)組逆向查找到從s到w的路徑, 存放到棧中
? ? ? ? int p = w;
? ? ? ? while( p != -1 ){
s.push(p);
? ? ? ? ? ? p = from[p];
? ? ? ? }
// 從棧中依次取出元素, 獲得順序的從s到w的路徑
? ? ? ? Vector res =new Vector();
? ? ? ? while( !s.empty() )
res.add( s.pop() );
? ? ? ? return res;
? ? }
// 打印出從s點(diǎn)到w點(diǎn)的路徑
? ? public void showPath(int w){
assert hasPath(w);
? ? ? ? Vector 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點(diǎn)到w點(diǎn)的最短路徑長(zhǎng)度
? ? // 若從s到w不可達(dá)丹拯，返回-1
? ? public int length(int w){
assert w >=0 && w < G.V();
? ? ? ? return ord[w];
? ? }
}
