圖的典型應(yīng)用
圖的種類:
無向圖(簡單連接),有向圖(連接有方向),加權(quán)圖(連接帶有權(quán)值),加權(quán)有向圖(連接有方向,又帶有權(quán)值)
特殊的圖:
- 自環(huán),即一條邊連接頂點和自身的一條邊
-
2.平行邊:連接同一對頂點的邊
image.png
4.1.1 術(shù)語
1.兩個頂點通過一條邊連接,稱兩個頂點是相鄰, 稱該連接依附于這兩個頂點.
2.頂點度,等于依附于該頂點的邊的總數(shù)
3.子圖,所有邊的一個子集以及他們依附的邊組成的圖
4.路徑
5.聯(lián)通,兩個頂點存在一條連接雙方的路徑,稱兩頂點是聯(lián)通的.
定義:
如果從任意一個頂點都存在一條路徑到達(dá)任意一個其他的頂點,稱連通圖;一副非連通的圖有若干個聯(lián)通的部分組成,他們都是極大聯(lián)通子圖.
定義:
樹是一個無環(huán)的連通圖.互不相連的樹的集合組成森林.
樹的重要特性,就是沒有環(huán).
圖的密度:已經(jīng)連接的頂點對/所有可能連接的頂點對.
稀疏圖,稠密圖.
無向圖的API:
Graph(int v)//創(chuàng)建含有V個頂點但不包含邊的圖
Graph(In in)//從標(biāo)準(zhǔn)輸入流in讀入一副圖
int V()
int E()
void addEdge(int v,int w)//向圖中添加一條邊 v-w
Iterable<Integer> adj(int v) //和v相鄰的所有頂點
toString()
圖的表示方法:(需要滿足的要求: A.必須為可能在應(yīng)用中碰到的各種類型的圖預(yù)留足夠的空間 B.graph的實例實現(xiàn)方法必須夠快)
有3中思路:
1.鄰接矩陣:
采用一個二維 boolean 矩陣boolean[][],按照順序記錄每第i個頂點到第i個頂點直接的連接,有連接為true,無連接false. 但是空間的耗費需要V2 ,因為百萬頂點的圖很常見.所以這中方法不符合A.
2.邊的數(shù)組:
可以用一個Edge類 包含兩個頂點,構(gòu)成一條邊.但是需要計算 V() ,需要遍歷整個邊的數(shù)量.才能找到.不滿足B
3.鄰接表數(shù)組:
用頂點建立一個索引列表.其中的每個元素都是該頂點相鄰的頂點列表.這種數(shù)據(jù)結(jié)構(gòu)能同時滿足A,B要求.如下圖:
4.1.2.2 鄰接表的數(shù)據(jù)結(jié)構(gòu)
通過采用鄰接表存儲,每條邊都會出現(xiàn)兩次.
如圖表示.
這種Graph的表示有下面特征:
1.使用空間與V+E 成正比
2.添加一條邊的時間為常數(shù)
3.遍歷頂點v的相鄰頂點所需時間和v的度成正比.
對于這些操作,這樣的特性已經(jīng)是最優(yōu)的,這可以滿足對圖的操作需要,而且支持平行邊,和自環(huán).邊的插入順序決定了graph的鄰接表的頂點的出現(xiàn)順序.
4.1.3深度優(yōu)先搜索
package algorithm.sortAlgorithm.Graph;
/**
* Created by leon on 18-2-9.
* 圖的處理API
*/
public interface Search {
/**
* v 和s 是聯(lián)通嗎
*
* @param v
* @return
*/
boolean marked(int v);
/**
* 與s聯(lián)通的頂點總數(shù)
*
* @return
*/
int count();
}
package algorithm.sortAlgorithm.Graph;
/**
* Created by leon on 18-2-9.
* 深度優(yōu)先搜索,從起點位置,遍歷他的一個沒有mark的鄰接頂點,遞歸遍歷這個鄰接頂點,
* 用一個mark數(shù)組標(biāo)示已經(jīng)遍歷過的頂點.
*/
public class DeepFirstSearch implements Search {
private boolean[] marked;
private int count;
/**
* 找到與起點s聯(lián)通的所有頂點
*
* @param graph
* @param s
* @return
*/
public DeepFirstSearch(Graph graph, int s) {
//創(chuàng)建mark數(shù)組
marked = new boolean[graph.V()];
dfs(graph, s);
}
private void dfs(Graph g, int s) {
marked[s] = true;
for (int vertex : g.adj(s)) {
if (!marked(vertex)) {
dfs(g, vertex);
}
}
}
@Override
public boolean marked(int v) {
return marked[v];
}
@Override
public int count() {
return count;
}
}
4.1.3.1 走迷宮
命題A .
深度優(yōu)先搜索標(biāo)記與起點聯(lián)通所有頂點所需要時間和頂點的度成正比.
4.1.3.2 單項通道
連通性: 給定一幅圖,回答”兩個給定的頂點之間是否連通?”或者”圖中有多少個連通子圖”
單點路徑:給定一幅圖和一個起點s,回答”從s到指定的點v是否存在一條路徑?如果有找出來”
4.1.4尋找路徑
深度優(yōu)先算法:
package algorithm.sortAlgorithm.Graph;
import java.util.Stack;
/**
* Created by leon on 18-2-9.
* 深度優(yōu)先方式尋找路徑,
* 需要使用兩個數(shù)組存儲.
* mark[] =>標(biāo)記已經(jīng)訪問過的頂點
* edgeTo[n]=m, 表示到n頂點的最后頂點為m,這里的值為最后的連接n的頂點值.
*/
public class DeepFirstPaths implements Paths {
private boolean[] marked;
private int[] edgeTo;
private int startV;
/**
* @param g
* @param s 起始頂點
*/
public DeepFirstPaths(Graph g, int s) {
marked = new boolean[g.V()];
edgeTo = new int[g.V()];
startV = s;
dfs(g, s);
}
/**
* 深度優(yōu)先遍歷
*
* @param g
* @param v
*/
private void dfs(Graph g, int v) {
marked[v] = true;
for (int w : g.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
dfs(g, w);
}
}
}
@Override
public boolean hasPathTo(int v) {
return marked[v];
}
@Override
public Iterable<Integer> pathTo(int v) {
if (hasPathTo(v)) {
return null;
}
Stack<Integer> pathStack = new Stack<>();
for (int end = v; end != startV; end = edgeTo[end]) {
pathStack.push(end);
}
pathStack.push(startV);
return pathStack;
}
}
4.1.5 廣度優(yōu)先搜索
單點最短路徑.給定一幅圖和一個起點s 回答”從s到v 是否存在一條路徑?如果有找出其最短的那條”解決這個問題方法 需要采用廣度優(yōu)先搜索.這也是許多圖算法的基石.深度優(yōu)先就像一個人在走迷宮,而廣度優(yōu)先則像一組人朝著各自方向在走迷宮,如果遇到岔路時會分裂出更多人搜索,當(dāng)兩個人交匯時,會合二為一(繼續(xù)采用最短的路徑).
廣度優(yōu)先遍歷算法:1.取下一個頂點放到隊列中;2.隊列頂點出對,并取出其相鄰的未標(biāo)記的頂點加入隊列.3.循環(huán)隊列的數(shù)據(jù).
廣度優(yōu)先搜索算法:采用優(yōu)先遍歷,增加一個marked[] 數(shù)組,marked[k]=true;表示頂點K已經(jīng)標(biāo)示過.結(jié)果用edgeTo[]數(shù)組表示,edgeTo[k]=N表示從根節(jié)點s到指定頂點k的最短路徑上一個頂點為N;
package algorithm.algorithmbook.graph;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
* 廣度優(yōu)先搜索
*
* @author leon
* @date 18-2-11.
*/
public class BreadthFirstPaths implements Paths {
private boolean[] marked;
private int[] edgeTo;
private final int start;
public BreadthFirstPaths(Graph graph, int vertex) {
marked = new boolean[graph.V()];
edgeTo = new int[graph.V()];
start = vertex;
bfs(graph, start);
}
/**
* 廣度優(yōu)先搜索算法
*
* @param graph 圖
* @param v 根頂點
*/
private void bfs(Graph graph, int v) {
Queue<Integer> needTraveselQueue = new LinkedList<>();
marked[v] = true;
needTraveselQueue.offer(v);
while (!needTraveselQueue.isEmpty()) {
int popV = needTraveselQueue.poll();
if (graph.adj(popV) != null) {
for (int vertex : graph.adj(popV)) {
if (!marked[vertex]) {
//標(biāo)記
marked[vertex] = true;
edgeTo[vertex] = popV;
needTraveselQueue.offer(vertex);
}
}
}
}
}
@Override
public boolean hasPathTo(int v) {
return marked[v];
}
@Override
public Iterable<Integer> pathTo(int v) {
if (hasPathTo(v)) {
return null;
}
Stack<Integer> pathStack = new Stack<>();
for (int end = v; end != start; end = edgeTo[end]) {
pathStack.push(end);
}
pathStack.push(start);
return pathStack;
}
}
命題B:
對于從s到可到達(dá)的任意頂點v,廣度優(yōu)先搜索都能找到一條從s→v的最短路徑.(這里規(guī)定頂點的鄰接頂點排在前面的比后面的優(yōu)先級高)
命題B續(xù):
度優(yōu)先搜索的時間最壞情況下與V+E成正比.
深度優(yōu)先搜索與廣度優(yōu)先搜索比較:
1.深度優(yōu)先不斷深入圖中,并在棧中保存所有的分叉頂點;廣度優(yōu)先像扇面一樣掃描圖,用一個隊列保存訪問過的最前段的頂點.
2.深度優(yōu)先是搜索離起點更遠(yuǎn)的頂點,直到遇到死胡同才返回來訪問近處的頂點;廣度先訪問起點附近的所有結(jié)點,只有臨近的結(jié)點都訪完了才向前進(jìn).
3.深度優(yōu)先的曲線一般較長較曲折;廣度優(yōu)先的曲線較短而且直接.
4.1.6連通分量
連通分量的概念:在圖中有多個連通的圖組成的大圖,那么小圖就是大圖的連通分量;要求解連通分量,其實就是深度優(yōu)先遍歷大圖的所有未連通的頂點.
package algorithm.algorithmbook.graph;
/**
* description: 連通子圖
*
* @author leon
* @date 18-2-12.
*/
public class ConectedComponet {
//記錄每一個頂點屬于哪一個連通區(qū)
private int[] id;
//自連通圖的個數(shù)false
private int count;
private boolean[] marked;
public ConectedComponet(Graph g) {
id = new int[g.V()];
marked = new boolean[g.V()];
//對每個頂點,進(jìn)行深度優(yōu)先遍歷==>依次對頂點的相鄰頂點深度遍歷.
for (int s = 0; s < g.V(); s++) {
//保證每個連通子圖是之前沒有被 遍歷過的,
if (!marked[s]) {
dfs(g, s);
//深度優(yōu)先遍歷完,說明遍歷過的都是統(tǒng)一連通子圖,count+1
count++;
}
}
}
private void dfs(Graph graph, int v) {
marked[v] = true;
id[v] = count;
for (int s : graph.adj(v)) {
if (marked[s]) {
dfs(graph, s);
}
}
}
/**
* n 和 w 是否是連通的?
*
* @param n
* @param w
* @return
*/
public boolean isConnected(int n, int w) {
return id[n] == id[w];
}
/**
* 一共有幾個連通圖
*
* @return
*/
public int count() {
return count;
}
/**
* v屬于那個連通圖 (0 ~ n-1)
*
* @param v
* @return
*/
public int id(int v) {
return id[v];
}
}
命題c
深度優(yōu)先搜索處理的時間和空間與V+E成正比,并且能在常數(shù)時間內(nèi)處理圖的連通性查詢.
證明:
由代碼可知每個鄰接表的元素只會查詢一次,一共有2E個元素(每條邊有2條)
4.1.6.2 union-find 算法(動態(tài)連通性)
4.1.6.2.1 quik-find
package algorithm.algorithmbook.graph;
/**
* description: union-find 動態(tài)連通性接口
*
* @author leon
* @date 18-2-12.
*/
public interface IUnionFind extends IConnectedCompenont {
/**
* 在p q之間連接
*
* @param p
* @param q
*/
void union(int p, int q);
}
package algorithm.algorithmbook.graph;
import java.io.FileNotFoundException;
import java.io.IOException;
import algorithm.algorithmbook.StdIn;
/**
* description: 動態(tài)連通性實現(xiàn)
*
* @author leon
* @date 18-2-12.
*/
public class UnionFind implements IUnionFind {
//用于記錄每一個點屬于那個 連通分量 ,初始化
protected int[] id;
//分量數(shù)
protected int count;
public UnionFind(int n) {
count = n;
id = new int[n];
for (int i = 0; i < n; i++) {
id[i] = i;
}
}
@Override
public void union(int p, int q) {
}
@Override
public boolean isConnected(int p, int q) {
return whichConnectedComponent(p) == whichConnectedComponent(q);
}
@Override
public int count() {
return count;
}
@Override
public int whichConnectedComponent(int p) {
return find(p);
}
public int find(int p) {
return 0;
}
public static void main(String[] args) {
try {
StdIn stdIn = new StdIn("tinnyUF.txt");
int num = stdIn.readInt();
UnionFind unionFind = new UnionFind(num);
while (!stdIn.isEmpty()) {
int p = stdIn.readInt();
int q = stdIn.readInt();
if (!unionFind.isConnected(p, q)) {
unionFind.union(p, q);
}
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException ioE) {
ioE.printStackTrace();
}
}
}
package algorithm.algorithmbook.graph;
/**
* description:實現(xiàn)Unionfind 的一種方法,quik-find
* <p>
* 基本思路:
* 把每個頂點屬于一個分量,只要兩個頂點的分量值相等,說明這兩個點是連通的.
* 所有連通的點的分量值用最后一個點的分量值替換,最后得到的所有分量值id[],
* 存在多少組不相等的 說明有幾個連通子圖.
* <p>
* 判斷find(int) 方法非常簡單
* union(p,q)方法每次遍歷所有的 頂點,把q最新的頂點分量值替換分量值和p相同的
* 最后得到連通的分量值都會是最后一個頂點的分量值
*
* @author leon
* @date 18-2-12.
*/
public class UnionFindQuikFind extends UnionFind {
public UnionFindQuikFind(int n) {
super(n);
}
@Override
public void union(int p, int q) {
int pv = find(p);
int qv = find(q);
//pq已經(jīng)是連通了,不需要進(jìn)行遍歷操作
if (pv == qv) {
return;
}
//把最新的id[q] 替換 與p相連的(也就是分量和p相同的)
for (int i = 0; i < id.length; i++) {
if (find(i) == pv) {
id[i] = qv;
}
}
//每次連接后連通子圖的數(shù)量-1,初始話是有count=n的
count--;
}
@Override
public int find(int p) {
return id[p];
}
}
quik-find 算法分析:
find方法顯然很快.在union方法里面,時間復(fù)雜度處于O(n2)
(1)兩次find()操作哗总，訪問2次數(shù)組
(2)掃描整個數(shù)組id[]励负，判斷p和q是否在同一個連通f分量if(find(i)==pID)，訪問N次數(shù)組
(3)①只有p讳窟，其余觸點均不和p在同一連通分量 id[p] =qID,訪問1次數(shù)組
②除了q本身貌矿，其余均和p在同一連通分量 id[i] = qID(i≠q)匀泊，訪問 N-1次數(shù)組颈渊，故總的訪問次數(shù)①2+N+1 = N+3②2+N+N-1 = 2N+1
4.1.6.2.2 quik-union算法
- 原理
考慮一下瘟檩，為什么以上的解法會造成“牽一發(fā)而動全身”慎式？
因為每個節(jié)點所屬的組號都是單獨記錄伶氢，各自為政的，沒有將它們以更好的方式組織起來瘪吏，當(dāng)涉及到修改的時候癣防，除了逐一通知、修改掌眠，別無他法蕾盯。所以現(xiàn)在的問題就變成了，如何將節(jié)點以更好的方式組織起來蓝丙，組織的方式有很多種级遭，但是最直觀的還是將組號相同的節(jié)點組織在一起望拖，想想所學(xué)的數(shù)據(jù)結(jié)構(gòu)，什么樣子的數(shù)據(jù)結(jié)構(gòu)能夠?qū)⒁恍┕?jié)點給組織起來挫鸽？常見的就是鏈表说敏，圖，樹丢郊，什么的了盔沫。但是哪種結(jié)構(gòu)對于查找和修改的效率最高？毫無疑問是樹枫匾，因此考慮如何將節(jié)點和組的關(guān)系以樹的形式表現(xiàn)出來架诞。
如果不改變底層數(shù)據(jù)結(jié)構(gòu)，即不改變使用數(shù)組的表示方法的話婿牍〕薮可以采用parent-link的方式將節(jié)點組織起來。
舉例而言等脂，id[p]的值就是p節(jié)點的父節(jié)點的序號俏蛮，如果p是樹根的話，id[p]的值就是p上遥，因此最后經(jīng)過若干次查找搏屑，一個節(jié)點總是能夠找到它的根節(jié)點，即滿足id[root] = root的節(jié)點也就是組的根節(jié)點了粉楚，然后就可以使用根節(jié)點的序號來表示組號辣恋。所以在處理一個整數(shù)對的時候，將首先找到整數(shù)對中每一個節(jié)點的組號(即它們所在樹的根節(jié)點的序號)模软，如果屬于不同的組的話伟骨，就將其中一個根節(jié)點的父節(jié)點設(shè)置為另外一個根節(jié)點，相當(dāng)于將一顆獨立的樹編程另一顆獨立的樹的子樹燃异。
package algorithm.algorithmbook.graph;
/**
* description: union-find 動態(tài)連通性接口
*
* @author leon
* @date 18-2-12.
*/
public interface IUnionFind extends IConnectedCompenont {
/**
* 在p q之間連接
*
* @param p
* @param q
*/
void union(int p, int q);
}
package algorithm.algorithmbook.graph;
import java.io.FileNotFoundException;
import java.io.IOException;
import algorithm.algorithmbook.StdIn;
/**
* description: 動態(tài)連通性實現(xiàn)
*
* @author leon
* @date 18-2-12.
*/
public class UnionFind implements IUnionFind {
//用于記錄每一個點屬于那個 連通分量 ,初始化
protected int[] id;
//分量數(shù)
protected int count;
public UnionFind(int n) {
count = n;
id = new int[n];
for (int i = 0; i < n; i++) {
id[i] = i;
}
}
@Override
public void union(int p, int q) {
}
@Override
public boolean isConnected(int p, int q) {
return whichConnectedComponent(p) == whichConnectedComponent(q);
}
@Override
public int count() {
return count;
}
@Override
public int whichConnectedComponent(int p) {
return find(p);
}
public int find(int p) {
return 0;
}
public static void main(String[] args) {
try {
StdIn stdIn = new StdIn("tinnyUF.txt");
int num = stdIn.readInt();
UnionFind unionFind = new UnionFind(num);
while (!stdIn.isEmpty()) {
int p = stdIn.readInt();
int q = stdIn.readInt();
if (!unionFind.isConnected(p, q)) {
unionFind.union(p, q);
}
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException ioE) {
ioE.printStackTrace();
}
}
}
package algorithm.algorithmbook.graph;
/**
* description:這里采用的思路和quik-find 不一樣.
* 考慮到quik-find 的union方法每次都要遍歷整個頂點.
* 主要原因是這些點沒有通過某種結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)連接起來,是一個孤立的點.
* 所以考慮采用樹的結(jié)構(gòu)把連通的分量連接起來,用 id[i]存儲i的根節(jié)點,
* 如果兩個點的根節(jié)點相同,那么他們就屬于同一個連通分量
*
* @author leon
* @date 18-2-12.
*/
public class UnionFind_QuikUnion extends UnionFind {
public UnionFind_QuikUnion(int n) {
super(n);
}
/**
* 這里的find 含義為查找p的根節(jié)點, 當(dāng)id[p]==p ,說明是他的根節(jié)點
*
* @param p
* @return
*/
@Override
public int find(int p) {
//這里采用循環(huán)向上查找,直到找到p的根節(jié)點.一定能查到
while (id[p] != p) {
p = id[p];
}
return p;
}
@Override
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
//p q的根節(jié)點不相同,把 q的根節(jié)點指派給p,形成一棵樹
//使用id[pRoot]主要是找到額 pRoot的根節(jié)點,
id[pRoot] = qRoot;
count--;
}
}
Quik-union分析:
對數(shù)組元素訪問:
1.最好情況下1
2.最壞情況下,整棵樹是一個線性的表,需要遍歷N-1次while循環(huán),而 while循環(huán)中2次訪問數(shù)組,最后一次達(dá)到根節(jié)點時不需要執(zhí)行循環(huán)體.所以一共的次數(shù)為 2(N-1)+1=2N-1
基本的時間復(fù)雜度也需要 O(n2).
所以目前Quik-find 和Quik-union 的優(yōu)劣程度還不是非常好區(qū)分.
4.1.6.2.3 加權(quán)quik-union算法
原理: 因為quik-union算法,在union(p,q)的時候是隨意將一棵樹合并到另一棵樹上.
這里的大樹指的是高度大小?還是指的結(jié)點數(shù)多少?
如果是小樹合并到大樹上,那么小樹的高度+1,整棵樹的高度不變.
如果大樹合并到小樹上,那么大樹的高度+1,整棵樹的高度也可能會變.
根據(jù)find(i) 方法,所要遍歷查詢數(shù)組的時間和樹的高度有關(guān).所以如果只允許把小樹合并到大樹上,則會減少整棵樹的高度.從而減少遍歷數(shù)組的次數(shù).為此需要增加一個sz[] 來存儲 每一個觸點所在樹的結(jié)點數(shù),結(jié)點數(shù)越大說明是大樹,而結(jié)點數(shù)小的則是小樹.
package algorithm.algorithmbook.graph;
/**
* description:
* 加權(quán) Quikunion算法
* 增加一個sz[i] ,表示i所在的樹的總size大小.把小樹合并到大樹中,
* 從而保持樹的構(gòu)造是有規(guī)律,樹的高度相對較小.從而會在后期的查找根節(jié)點
* 的時間復(fù)雜度保持到對數(shù)級別
*
* @author leon
* @date 18-2-12.
*/
public class UnionFind_Weighted_QuikUnion extends UnionFind_QuikUnion {
//用于記錄每個頂點所在樹的大小,默認(rèn)初始值為1
private int[] sz;
public UnionFind_Weighted_QuikUnion(int n) {
super(n);
for (int i = 0; i < n; i++) {
sz[i] = 1;
}
}
/**
* 主要的改進(jìn)主要在union上面,把小樹合并到大樹中
*
* @param p
* @param q
*/
@Override
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
//關(guān)鍵部分,進(jìn)行合并了
if (sz[pRoot] > sz[qRoot]) {
id[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
} else {
id[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}
count--;
}
}
命題H
對于N個觸點,采用加權(quán)quik-union構(gòu)造的森林的任意結(jié)點的深度對多為logN
對于加權(quán)quik-union算法,是一種唯一一可以解決大型實際問題的算法.處理N個觸點M條鏈條的最多訪問次數(shù)為cMlogN.
綜合分析:
理論上深度優(yōu)先搜索比union-find法快.
4.1.7 符號圖
實際應(yīng)用中通常圖都是通過文件,網(wǎng)頁定義的,使用的是字符串而非數(shù)字代替頂點,為了適應(yīng)這樣的應(yīng)用我們必須定義擁有如下輸入格式:
1 .頂點為字符串.
2.用指定的分隔符來隔開頂點
3.每一行都表示一條邊的集合,每一條邊都連著這一行的第一個名稱表示的頂點和其他名稱所表示的頂點
4.頂點樹V和邊數(shù)E是隱式定義的
package algorithm.algorithmbook.graph;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.HashMap;
import algorithm.algorithmbook.StdIn;
/**
* description:符號圖,用index(String key) 和 name(v)將頂點和 索引連接起來
*
* @author leon
* @date 18-2-21.
*/
public class SymbolGraph {
private HashMap<String, Integer> st;//符號表-->索引
private String[] keys;//索引-->符號名
private Graph g;//圖
/**
* @param fileName
* @param delim 頂點分隔符
*/
public SymbolGraph(String fileName, String delim) {
//第一次遍歷,生成符號表, 以及索引數(shù)組
st = new HashMap<>();
StdIn in = null;
try {
in = new StdIn(fileName);
} catch (FileNotFoundException e) {
e.printStackTrace();
}
try {
while (!in.isEmpty()) {
String[] a = in.readLine().split(delim);
for (int i = 0; i < a.length; i++) {
if (!st.containsKey(a[i])) {
st.put(a[i], st.size());//從 0,1,2,3...順序計數(shù)
}
}
}
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
in.close();
} catch (IOException e) {
e.printStackTrace();
}
}
//創(chuàng)建反向索引
keys = new String[st.size()];
for (String key : st.keySet()) {
keys[st.get(key)] = key;//索引下標(biāo)為st的 value
}
//第二次遍歷,真正創(chuàng)建graph
g = new Graph(st.size());
try {
in = new StdIn(fileName);
} catch (FileNotFoundException e) {
e.printStackTrace();
}
try {
while (!in.isEmpty()) {
String[] a = in.readLine().split(delim);
int v = st.get(a[0]);
//這里有可能一行有多個邊??
for (int i = 1; i < a.length; i++) {
g.addEdge(v, st.get(a[i]));
}
}
} catch (IOException e) {
e.printStackTrace();
}
}
/**
* key 是一個頂點嗎
*
* @param key 頂點名
* @return boolean
*/
boolean contains(String key) {
return st.containsKey(key);
}
/**
* 返回key的索引
*
* @param key 頂點名
* @return 索引值
*/
int index(String key) {
return st.get(key);
}
/**
* 索引v的頂點名
*
* @param v 索引值
* @return 頂點名
*/
String name(int v) {
return keys[v];
}
/**
* 隱藏的graph對象
*
* @return
*/
Graph graph() {
return g;
}
}
4.1.7.4 間隔的度數(shù).
圖處理的經(jīng)典問題之一就是找尋社交網(wǎng)絡(luò)中兩個人之間的度數(shù).可以延伸到電影行業(yè)可以查詢演員之間的間隔,也可以查詢電影與電影之間的間隔,地圖地理位置之間的距離(圖的連通)
通過符號表,和廣度優(yōu)先搜索 ,可以先由符號表創(chuàng)建Graph,從索引index 開始進(jìn)行廣度優(yōu)先查找圖中的最短路徑.
