摘要:樹是一副無環(huán)連通圖?;ゲ幌噙B的樹組成的集合稱為森林。表示無向圖的數(shù)據(jù)類型圖的基本操作的兩個(gè)構(gòu)造,得到頂點(diǎn)數(shù)和邊數(shù),增加一條邊。該方法不符合第一個(gè)條件,上百萬個(gè)頂點(diǎn)的圖是很常見的空間不滿足。
四種重要的圖模型:
無向圖(簡單連接)
有向圖(連接有方向性)
加權(quán)圖(連接帶有權(quán)值)
加權(quán)有向圖(連接既有方向性又帶有權(quán)值)
無向圖定義:由一組頂點(diǎn)和一組能夠?qū)蓚€(gè)頂點(diǎn)相連的邊組成。
特殊:自環(huán)(一條連接一個(gè)頂點(diǎn)和其自身的邊);平行邊(連接同一對頂點(diǎn)的兩條邊)
數(shù)學(xué)家將含有平行邊的圖稱為多重圖;將沒有平行邊或自環(huán)的圖稱為簡單圖。現(xiàn)實(shí)當(dāng)中,兩點(diǎn)就可以指代一條邊。
術(shù)語表兩個(gè)頂點(diǎn)通過一條邊相連,稱這兩頂點(diǎn)相鄰,并稱該連接依附于這兩個(gè)頂點(diǎn)。
某個(gè)頂點(diǎn)的度數(shù)即為依附于它的邊的總數(shù)。
子圖是由一幅圖的所有邊的一個(gè)子集(以及它們所依附的所有頂點(diǎn))組成的圖。
路徑是由邊順序連接的一系列頂點(diǎn)。
簡單路徑是一條沒有重復(fù)頂點(diǎn)的路徑。
環(huán)是一條至少含有一條邊且起點(diǎn)和終點(diǎn)相同的路徑。
簡單環(huán)是一條(除了起點(diǎn)和終點(diǎn)必須相同之外)不含有重復(fù)頂點(diǎn)和邊的環(huán)。
路徑或者環(huán)的長度為其中所包含的邊數(shù)。
大多情況研究簡單環(huán)和簡單路徑,并會省略簡單二字。當(dāng)允許重復(fù)的頂點(diǎn)時(shí),指的都是一般的路徑和環(huán)。
當(dāng)兩個(gè)頂點(diǎn)之間存在一條連接雙方的路徑時(shí),稱一個(gè)頂點(diǎn)和另一個(gè)頂點(diǎn)是連通的。
U-V-W-X記為U到X的一條路徑;U-V-W-X-U記為U到V到W到X再回到U的一條環(huán)。
從任意一個(gè)頂點(diǎn)都存在一條路徑到達(dá)另一個(gè)任意頂點(diǎn),稱這幅圖是連通圖。
一副非連通的圖由若干連通的部分組成,它們都是其極大連通子圖。
直觀上:如果頂點(diǎn)是念珠,邊是連接念珠的線,它們都是物理存在的對象,那么將任意頂點(diǎn)提起來,連通圖都將是一個(gè)整體,而非連通圖則會變成兩個(gè)或多個(gè)部分。
一般來說:要處理一張圖就要一個(gè)個(gè)地處理它的連通分量(子圖)。
無環(huán)圖:不包含環(huán)的圖。
樹是一副無環(huán)連通圖?;ゲ幌噙B的樹組成的集合稱為森林。連通圖的生成樹是它的一副子圖,它含有圖中的所有頂點(diǎn)且是一棵樹。圖的生成樹森林是它的所有連通子圖的生成樹的集合。
樹的定義非常通用,稍作改動(dòng)就可以變成用來描述程序行為的(函數(shù)調(diào)用層次)模型和數(shù)據(jù)結(jié)構(gòu)(二叉查找樹、2-3樹等)。
當(dāng)且僅當(dāng)一幅含有V個(gè)節(jié)點(diǎn)的圖G滿足下列5個(gè)條件之一時(shí),它就是一棵樹:
G有V-1條邊且不含有環(huán);
G有V-1條邊且是連通的;
G是連通的,但刪除任意一條邊都會使之不再連通;
G是無環(huán)圖,但添加任意一條邊都會產(chǎn)生一條環(huán);
G中的任意一對頂點(diǎn)之間僅存在一條簡單路徑。
圖的密度是指已經(jīng)連接的頂點(diǎn)對占所有可能被連接的的頂點(diǎn)對的比例。一般來說,如果一幅圖中不同的邊的數(shù)量只占頂點(diǎn)總數(shù)V的一小部分,那么就認(rèn)為這幅圖是稀疏的,否則是稠密的。
二分圖是一種能夠?qū)⑺泄?jié)點(diǎn)分為兩部分的圖,其中圖的每條邊所連接的兩個(gè)頂點(diǎn)都分別屬于不同的部分。二分圖會出現(xiàn)在許多場景中。
表示無向圖的數(shù)據(jù)類型圖的基本操作的API:
兩個(gè)構(gòu)造,得到頂點(diǎn)數(shù)V( )和邊數(shù)E( ),增加一條邊addEdge( int v, int w )。本節(jié)所有算法都基于adj( )方法所抽象的基本操作。第二個(gè)構(gòu)造函數(shù)接受的輸入由2E+2個(gè)整數(shù)組成:首先是V, 然后是E, 在然后是 E 對 0到V-1之間的整數(shù),每個(gè)整數(shù)對都表示一條邊。
圖的幾種表示方法要面對的下一個(gè)圖處理問題就是用哪種數(shù)據(jù)結(jié)構(gòu)來表示并實(shí)現(xiàn)這份API,這包含兩個(gè)要求:
必須為可能在應(yīng)用中碰到的各種類型的圖預(yù)留出足夠的空間;
實(shí)例方法的實(shí)現(xiàn)一定要快—它們是開發(fā)處理圖的各種用例的基礎(chǔ)。
要求比較模糊,但是仍然能幫我們在三種圖的表示方法中進(jìn)行選擇。
鄰接矩陣。用V*V的布爾矩陣,當(dāng)V和W有邊時(shí),定義V行W列元素為TRUE,否則為FALSE。該方法不符合第一個(gè)條件,上百萬個(gè)頂點(diǎn)的圖是很常見的.V^2空間不滿足。
邊的數(shù)組??梢允褂靡粋€(gè)Edge類,含有兩個(gè)int實(shí)例變量。表示方法簡單但是不滿足第二個(gè)條件—要實(shí)現(xiàn)adj( )需要檢查所有邊。
鄰接表數(shù)組??梢允褂靡粋€(gè)以頂點(diǎn)為索引的列表數(shù)組,其中每個(gè)元素都是和該頂點(diǎn)相鄰的頂點(diǎn)列表。該結(jié)構(gòu)同時(shí)滿足兩個(gè)條件。本章一直用它。
除了性能目標(biāo),還發(fā)現(xiàn):允許存在平行邊相當(dāng)于排除了鄰接矩陣,因?yàn)猷徑泳仃嚐o法表示它們。
鄰接表的數(shù)據(jù)結(jié)構(gòu)非稠密圖的標(biāo)準(zhǔn)表示稱為鄰接表的數(shù)據(jù)結(jié)構(gòu),它將每個(gè)頂點(diǎn)的所有相鄰頂點(diǎn)都保存在該頂點(diǎn)對于的元素所指向的一張鏈表中。使用這個(gè)數(shù)組就是為了快速訪問給定頂點(diǎn)的鄰接頂點(diǎn)列表。
使用Bag抽象數(shù)據(jù)類型(也可用Java中的
這種Graph的實(shí)現(xiàn)的性能:
使用的空間和V+E成正比;
添加一條邊所需要的時(shí)間為常數(shù);
遍歷頂點(diǎn)V的所有相鄰頂點(diǎn)所需要的時(shí)間和V的度數(shù)成正比。
對于這樣的操作,這樣的特性已經(jīng)是最優(yōu),可以滿足圖處理應(yīng)用的需要,并且支持平行邊和自環(huán)。邊的插入順序決定了Graph得鄰接表中頂點(diǎn)的出現(xiàn)順序。使用構(gòu)造函數(shù)從標(biāo)準(zhǔn)輸入中讀入一副圖時(shí),就意味著輸入的格式和邊的順序決定了Graph的鄰接表數(shù)組中頂點(diǎn)的出現(xiàn)順序。
/** * 無向圖 */ public class Graph { private int vertexCount; // 頂點(diǎn)數(shù) private int edgeCount; // 邊數(shù) private LinkedList[] adj; // 鄰接表數(shù)組 public Graph(int v){ this.adj = new LinkedList[v]; for(int i = 0; i ();// 初始化鄰接表數(shù)組 this.vertexCount = v; } public Graph(In in) { this(in.readInt()); int e = in.readInt();//得到邊數(shù) // 讀取每條邊,進(jìn)行圖的初始化操作 for(int i = 0; i adj(int v){return adj[v];} /** 把圖轉(zhuǎn)化成標(biāo)準(zhǔn)字符串形式*/ public String toString(){ String NEWLINE = System.getProperty("line.separator"); StringBuilder sb = new StringBuilder(); sb.append("vertex count: ").append(getVertexCount()) .append(" edge count: ").append(getEdgeCount()) .append(Config.NEWLINE); for (int v = 0; v < getVertexCount();v++){ LinkedList list = adj(v); sb.append(v).append(": ").append("["); for (int i=0; i < list.size();i++){ sb.append(list.get(i)).append(","); } sb.deleteCharAt(sb.length() - 1); sb.append("]").append(NEWLINE); } return sb.toString(); } public static void main(String[] args) { String dir = Graph.class.getPackage().getName().replace(".", "/"); String path = Graph.class.getClassLoader().getResource(dir+"/tinyG.txt").getPath(); In in = new In(new File(path)); Graph g = new Graph(in); System.out.println(g.toString()); } }
/** * 圖的基本常用操作工具類 */ public class GraphUtils { /** 計(jì)算頂點(diǎn)v的度數(shù)*/ public static int degree(Graph graph, int v){return graph.adj(v).size();} /** 計(jì)算圖中最大的度*/ public static int maxDegree(Graph graph){ int max = 0; for(int i = 0;imax ? currentDegree : max; } return max; } /** 計(jì)算圖的平均度數(shù)*/ public static int avgDegree(Graph g){ return 2 * g.getEdgeCount() / g.getVertexCount(); } /** 計(jì)算自環(huán)的個(gè)數(shù)*/ public static int numberOfSelfLoops(Graph g){ int count = 0; for(int v = 0; v < g.getVertexCount(); v++) for(int w: g.adj(v)) if(v == w) count++; return count / 2; // 每條邊計(jì)算了兩次 } public static void main(String[] args) { String dir = GraphUtils.class.getPackage().getName().replace(".", "/"); String path = GraphUtils.class.getClassLoader().getResource(dir+"/tinyG.txt").getPath(); In in = new In(new File(path)); Graph g = new Graph(in); for (int i = 0; i < g.getVertexCount(); i++) { System.out.println(i+" degree : "+GraphUtils.degree(g, i)); } System.out.println("the max degree is : " + GraphUtils.maxDegree(g)); System.out.println(g.toString()); System.out.println("avg degree: "+GraphUtils.avgDegree(g)); System.out.println("count of self loop: "+GraphUtils.numberOfSelfLoops(g)); } }
0 degree : 4 1 degree : 1 2 degree : 1 3 degree : 2 4 degree : 3 5 degree : 3 6 degree : 2 7 degree : 1 8 degree : 1 9 degree : 3 10 degree : 1 11 degree : 2 12 degree : 2 the max degree is : 4 vertex count: 13 edge count: 13 0: [5,1,2,6] 1: [0] 2: [0] 3: [4,5] 4: [3,6,5] 5: [0,4,3] 6: [4,0] 7: [8] 8: [7] 9: [12,10,11] 10: [9] 11: [12,9] 12: [9,11] avg degree: 2 count of self loop: 0圖的處理算法的設(shè)計(jì)模式
將圖的表示和實(shí)現(xiàn)分離開。為每個(gè)任務(wù)創(chuàng)建一個(gè)相應(yīng)的類,用例可以創(chuàng)建相應(yīng)的對象來完成任務(wù)。
深度優(yōu)先搜索探索迷宮方法:tremaux搜索:
選擇一條沒有標(biāo)記過的通道,在走過的路上鋪一條繩子;
標(biāo)記所有你第一次路過的路口和通道;
當(dāng)來到一個(gè)標(biāo)記過的路口時(shí)(用繩子)回退到上一個(gè)路口;
當(dāng)回退到得路口已經(jīng)沒有可走的通道時(shí)繼續(xù)回退。
繩子可保證總能找到一條出路,標(biāo)記則能保證不會兩次經(jīng)過同一條通道或同一個(gè)路口。
看Java代碼實(shí)現(xiàn):
/** * 圖的深度優(yōu)先搜索算法 */ public class DepthFirstSearch { private int count; private boolean[] marked; // 數(shù)組存儲每個(gè)頂點(diǎn)是否被遍歷過 /** * 從頂點(diǎn)s開始對g進(jìn)行深搜 * @param g * @param s */ public DepthFirstSearch(Graph g, int s) { marked = new boolean[g.getVertexCount()]; dfs(g, s); } /** 深搜*/ private void dfs(Graph g, int s) { marked[s] = true; // 1.標(biāo)記頂點(diǎn)s count++; // 2.count數(shù)加一 LinkedListlist = g.adj(s);// 3.獲取s的鄰接表 for(int w: list) // 4.對鄰接表進(jìn)行遍歷 if(!isMarked(w)) dfs(g,w); // 5.如果遍歷到的頂點(diǎn)沒有被標(biāo)記過,對該頂點(diǎn)繼續(xù)遞歸深搜 } /** 頂點(diǎn)w是否和起點(diǎn)s相連通*/ public boolean isMarked(int w){return marked[w];} /** 與起點(diǎn)s連通的頂點(diǎn)數(shù)量*/ public int count(){return count;} public static void main(String[] args) { String dir = DepthFirstSearch.class.getPackage().getName().replace(".", "/"); String path = DepthFirstSearch.class.getClassLoader().getResource(dir+"/tinyG.txt").getPath(); In in = new In(new File(path)); Graph g = new Graph(in); int start = 0; DepthFirstSearch search = new DepthFirstSearch(g, start); System.out.print("start vertex: "+ start+". "); StringBuilder sb = new StringBuilder(); for(int i = 0; i< g.getVertexCount(); i++) if(search.isMarked(i)) sb.append(" "+ i); System.out.println("Connected " + sb.toString()); // 如果和s連通的頂點(diǎn)數(shù)量和圖的頂點(diǎn)數(shù)量相同,說明是連通圖 if(search.count() == g.getVertexCount()) System.out.println("g is a connected graph."); else System.out.println("g is not a connected graph."); } }
start vertex: 0. Connected 0 1 2 3 4 5 6 g is not a connected graph.
“兩個(gè)給定頂點(diǎn)是否連通?”等價(jià)于“兩個(gè)給定的頂點(diǎn)之間是否存在一條路徑”,也叫路徑檢測問題。
union-find算法的數(shù)據(jù)結(jié)構(gòu)并不能解決找出這樣一條路徑問題,DFS是已經(jīng)學(xué)習(xí)過的方法中第一個(gè)能夠解決該問題的算法
能解決的另一問題:單點(diǎn)路徑----給定一幅圖和一個(gè)起點(diǎn)s,“從S到給定的頂點(diǎn)V是否存在一條路徑,如果有,找出”
尋找路徑構(gòu)造函數(shù)接受一個(gè)起點(diǎn)S作為參數(shù),計(jì)算S到與S連通的每個(gè)頂點(diǎn)之間的路徑。在為S創(chuàng)建了Paths對象后,用例可以調(diào)用pathTo()實(shí)例方法來遍歷從S到任意和S連通的頂點(diǎn)的路徑上的所有頂點(diǎn)。以后會實(shí)現(xiàn)只查找具有某些屬性的路徑。
Java實(shí)現(xiàn)
/** * 深搜尋找路徑問題 */ public class DepthFirstPaths { private boolean[] marked; private int[] edgeTo; // 路徑 private int start; // 起點(diǎn) public DepthFirstPaths(Graph g, int s){ marked = new boolean[g.getVertexCount()]; edgeTo = new int[g.getVertexCount()]; this.start = s; dfs(g, s); } private void dfs(Graph g, int s) { marked[s] = true; for(int w: g.adj(s)){ if(!marked[w]){ // 如果w沒有被標(biāo)記過,把路徑數(shù)組中的w處置為s,意思:從s到達(dá)了w。此處記錄了每一次深搜的路徑節(jié)點(diǎn) edgeTo[w] = s; dfs(g, w); } } } /** 從起點(diǎn)s到頂點(diǎn)v是否存在通路*/ public boolean hasPathTo(int v){return marked[v];} public StackpathTo(int v){ if(!hasPathTo(v)) return null; Stack stack = new Stack<>(); for(int x = v; x!=start; x=edgeTo[x]) // 從終點(diǎn)開始,倒著找起點(diǎn),依次push入棧 stack.push(x); stack.push(start);// for循環(huán)到起點(diǎn)處終止,所以在循環(huán)結(jié)束后要把起點(diǎn)入棧,至此 一條完整的路徑依次入棧 return stack; } public static void main(String[] args) { String dir = DepthFirstPaths.class.getPackage().getName().replace(".", "/"); String path = DepthFirstPaths.class.getClassLoader().getResource(dir+"/tinyG.txt").getPath(); In in = new In(new File(path)); Graph g = new Graph(in); int start = 0; DepthFirstPaths pathSearch = new DepthFirstPaths(g, start); StringBuilder sb = new StringBuilder(); for(int i = 0; i p = pathSearch.pathTo(i); while(!p.isEmpty()) sb.append(p.pop()).append("->"); sb.deleteCharAt(sb.length()-1); sb.deleteCharAt(sb.length()-1); System.out.println(sb.toString()); } } }
0 to 1: 0->1 0 to 2: 0->2 0 to 3: 0->5->4->3 0 to 4: 0->5->4 0 to 5: 0->5 0 to 6: 0->5->4->6 0 to 7 : not connected. 0 to 8 : not connected. 0 to 9 : not connected. 0 to 10 : not connected. 0 to 11 : not connected. 0 to 12 : not connected.廣度優(yōu)先搜索BFS
深搜得到的路徑不僅取決于圖的結(jié)構(gòu),還取決于圖的表示和遞歸調(diào)用的性質(zhì)。我們自然對最短路徑感興趣:
單點(diǎn)最短路徑。給定一幅圖和一個(gè)起點(diǎn)S,從S到給定頂點(diǎn)V是否存在一條路徑?如果有,請找出其中最短的那條(所含邊數(shù)最少)。
DFS遍歷圖的順序和找出最短路徑的目標(biāo)無關(guān)。
BFS為了這個(gè)目標(biāo)而出現(xiàn)。要找到從S到V得最短路徑,從S開始,在所有由一條邊就可以到達(dá)的頂點(diǎn)中查找V, 如果找不到就繼續(xù)在與S距離兩條邊的所有頂點(diǎn)中查找,如此一直執(zhí)行。
DFS好像是一個(gè)人在走迷宮,BFS則像一組人在一起朝各個(gè)方向走這個(gè)迷宮,每個(gè)人都有自己的繩子,當(dāng)出現(xiàn)新的叉路時(shí),可以假設(shè)一個(gè)探索者可以分裂為更多的人來搜索。當(dāng)來個(gè)那個(gè)探索者相遇的時(shí)候,合二為一,并繼續(xù)使用先到達(dá)者的繩子。
在程序中,搜索一幅圖時(shí)遇到有多條邊需要遍歷的情況,我們會選擇其中一條并將其他通道留到以后再繼續(xù)搜索。在DFS中,用了一個(gè)可以下壓的棧,以支持遞歸搜索。使用LIFO的規(guī)則來描述壓棧和走迷宮時(shí)先探索相鄰的通道類似。從有待搜索的通道中選擇最晚遇到過的那條。
在BFS中希望按照與起點(diǎn)的距離的順序來遍歷所有的頂點(diǎn):使用FIFO先進(jìn)先出隊(duì)列來代替棧LIFO后進(jìn)先出 即可。將從有待搜索的通道中選擇最早遇到的那條。
實(shí)現(xiàn):
算法4.2實(shí)現(xiàn)了BFS。使用隊(duì)列保存所有已經(jīng)被標(biāo)記過但其鄰接表還未被檢查過的頂點(diǎn)。先將起點(diǎn)加入隊(duì)列,然后重復(fù)下面步驟直到隊(duì)列為空:
取隊(duì)列中的下一個(gè)頂點(diǎn)V并標(biāo)記它;
將與V相鄰的所有未被標(biāo)記過的頂點(diǎn)加入隊(duì)列。
算法4.2中的方法不是遞歸的,不像遞歸中隱式使用的棧,而是顯式地使用了一個(gè)隊(duì)列。
從隊(duì)列中刪除0,將相鄰頂點(diǎn)2 1 5加入隊(duì)列,標(biāo)記它們并分別將它們在edgeTo[ ]中的值置為0;隊(duì)列: 0 2 1 5
從隊(duì)列中刪除2,并檢查相鄰頂點(diǎn)0 1 3 4, 0和1已經(jīng)被標(biāo)記,將3和4這兩個(gè)沒被標(biāo)記的加入隊(duì)列,標(biāo)記它們,并分別將它們在edgeTo[ ] 中的值設(shè)為2;隊(duì)列: 0 2 1 5 3 4
刪除1,檢查相鄰點(diǎn)0 2,發(fā)現(xiàn)都已經(jīng)被標(biāo)記;隊(duì)列: 0 2 1 5 3 4
刪除5, 檢查相鄰點(diǎn) 0 3, 發(fā)現(xiàn)都已經(jīng)被標(biāo)記;隊(duì)列: 0 2 1 5 3 4
刪除3, 檢查相鄰點(diǎn) 2 4 5, 發(fā)現(xiàn)都已經(jīng)被標(biāo)記;隊(duì)列: 0 2 1 5 3 4
刪除4, 檢查相鄰點(diǎn) 2 3, 發(fā)現(xiàn)都已經(jīng)被標(biāo)記;隊(duì)列: 0 2 1 5 3 4
/** * 廣搜找到最短路徑 * 對于從s可達(dá)的任意頂點(diǎn)v,廣搜都能找到一條從s到v的最短路徑 * (沒有其他從s到v的路徑所含邊比這條路徑更少) * 廣搜所需時(shí)間在最壞情況下和(v + e)成正比。 */ public class BreadthFirstPaths { private boolean[] marked; private int[] edgeTo; private int start; public BreadthFirstPaths(Graph g, int s){ this.start = s; marked = new boolean[g.getVertexCount()]; edgeTo = new int[g.getVertexCount()]; bfs(g, s); } private void bfs(Graph g, int s) { Queuequeue = new Queue<>(); marked[s] = true; // 標(biāo)記起點(diǎn) queue.enqueue(s); // 起點(diǎn)入隊(duì) while(!queue.isEmpty()){ int head = queue.dequeue(); // 從隊(duì)列中取出隊(duì)首 LinkedList list = g.adj(head); // 得到隊(duì)首的鄰接表 for(int w: list){ //遍歷鄰接表 if(!marked[w]){ // 若當(dāng)前節(jié)點(diǎn)沒有被標(biāo)記過 edgeTo[w] = head; // 1.存入路徑 marked[w] = true; // 2.進(jìn)行標(biāo)記 queue.enqueue(w); // 3.節(jié)點(diǎn)入隊(duì) } } } } /** 從起點(diǎn)s到頂點(diǎn)v是否存在通路*/ public boolean hasPathTo(int v){return marked[v];} /** 返回從起點(diǎn)s到頂點(diǎn)v的一條最短路徑*/ public Stack pathTo(int v){ if(!hasPathTo(v)) return null; // 若不存在到v的路徑,返回Null Stack path = new Stack<>(); for(int x = v; x!=start; x=edgeTo[x]) path.push(x); path.push(start); return path; } public static void main(String[] args) { String dir = BreadthFirstPaths.class.getPackage().getName().replace(".", "/"); String path = BreadthFirstPaths.class.getClassLoader().getResource(dir+"/tinyG.txt").getPath(); In in = new In(new File(path)); Graph g = new Graph(in); int start = 5; BreadthFirstPaths bfPath = new BreadthFirstPaths(g, start); for(int i = 0; i p = bfPath.pathTo(i); while(!p.isEmpty()){ sb.append(p.pop() + "->"); } sb.deleteCharAt(sb.length() - 1); sb.deleteCharAt(sb.length() - 1); System.out.println(sb.toString()); } } }
5 to 0 : 5->0 5 to 1 : 5->0->1 5 to 2 : 5->0->2 5 to 3 : 5->3 5 to 4 : 5->4 5 to 6 : 5->0->6 5 to 7 : not connected. 5 to 8 : not connected. 5 to 9 : not connected. 5 to 10 : not connected. 5 to 11 : not connected. 5 to 12 : not connected.
對于這個(gè)例子,edgeTo[]數(shù)組在第二步之后就已經(jīng)完成了。和深搜一樣,一點(diǎn)所有頂點(diǎn)都已經(jīng)被標(biāo)記,余下的計(jì)算工作就只是在檢查連接到各個(gè)已被標(biāo)記的頂點(diǎn)的邊而已。
命題:對于從S可達(dá)到的任意頂點(diǎn)V, 廣搜都能找到一條從S到V的最短路徑(沒有其他從S到V得路徑所含的邊比這條路徑更少)
續(xù): 廣搜所需的時(shí)間在最壞情況下和V+E成正比。
DFS和BFS都會先將起點(diǎn)存入數(shù)據(jù)結(jié)構(gòu)中,然后重復(fù)以下步驟知道數(shù)據(jù)結(jié)構(gòu)被清空:
取其中的下一個(gè)頂點(diǎn)并標(biāo)記它;
將V的所有相鄰而又未被標(biāo)記的頂點(diǎn)加入數(shù)據(jù)結(jié)構(gòu)。
不同之處在于從數(shù)據(jù)結(jié)構(gòu)中獲取下一個(gè)頂點(diǎn)的規(guī)則:廣搜是最早加入的頂點(diǎn);深搜是最晚加入的頂點(diǎn)。這種差異得到了處理圖的兩種完全不同的視角,無論哪種,所有與起點(diǎn)連通的頂點(diǎn)和邊都會被檢查到。
連通分量深搜下一個(gè)直接應(yīng)用就是找出一幅圖的所有連通分量。API:
CC的實(shí)現(xiàn)使用了marked[ ]數(shù)組來尋找一個(gè)頂點(diǎn)作為每個(gè)連通分量中深度優(yōu)先搜索的起點(diǎn)。遞歸的深搜第一次調(diào)用的參數(shù)是頂點(diǎn)0,會標(biāo)記所有與0連通的頂點(diǎn)。然后構(gòu)造函數(shù)中的for循環(huán)會查找每個(gè)沒有被標(biāo)記的頂點(diǎn)并遞歸調(diào)用dfs來標(biāo)記和它相鄰的所有頂點(diǎn)。另外,它還使用了一個(gè)以頂點(diǎn)作為索引的數(shù)組id[ ],將同一個(gè)連通分量中的頂點(diǎn)和連通分量的標(biāo)識符關(guān)聯(lián)起來。這個(gè)數(shù)組使得connected( )方法的實(shí)現(xiàn)變得十分簡單。
/** * 強(qiáng)連通分量 */ public class CC { private boolean[] marked; private int[] id; private int count; public CC(Graph g){ marked = new boolean[g.getVertexCount()]; id = new int[g.getVertexCount()]; for(int s = 0; s < g.getVertexCount(); s++){ if(!marked[s]){ dfs(g,s); count++; } } } private void dfs(Graph g, int v) { marked[v] = true; id[v] = count; for(int w: g.adj(v)) if(!marked[w]) dfs(g,w); } /** v和w連通嗎*/ public boolean connected(int v, int w) { return id[v] == id[w]; } /** v所在的連通分量的標(biāo)識符*/ public int id(int v) { return id[v]; } /** 連通分量數(shù)*/ public int count() {return count;} public static void main(String[] args) { String dir = CC.class.getPackage().getName().replace(".", "/"); String path = CC.class.getClassLoader().getResource(dir+"/tinyG.txt").getPath(); In in = new In(new File(path)); Graph g = new Graph(in); CC cc = new CC(g); int m = cc.count(); System.out.println("number of components: "+ m); LinkedList[] components = new LinkedList[m]; for(int i =0;i (); for(int v = 0; v< g.getVertexCount(); v++) components[cc.id(v)].add(v); for(int i=0;i number of components: 3 0 1 2 3 4 5 6 7 8 9 10 11 12其實(shí)現(xiàn)基于一個(gè)由頂點(diǎn)索引的數(shù)組id[ ].若V屬于第i個(gè)連通分量,則id[v]的值為i。構(gòu)造函數(shù)會找出一個(gè)未被標(biāo)記的頂點(diǎn)并調(diào)用遞歸函數(shù)dfs( )來標(biāo)記并區(qū)分出所有和它連通的頂點(diǎn),如此重復(fù)直到所有的頂點(diǎn)都被標(biāo)記并區(qū)分。
命題C:深搜的預(yù)處理使用的時(shí)間和空間與V+E成正比且可以在常數(shù)時(shí)間內(nèi)處理關(guān)于圖的連通性查詢。
和union-find算法對比:理論上深搜比union-find快,因?yàn)槟鼙WC所需時(shí)間是常數(shù),而union-find不行;但在實(shí)際中,該差異微不足道。union-find更快,因?yàn)樗恍枰暾臉?gòu)造并表示一幅圖。更重要的是:union-find算法是一種動(dòng)態(tài)算法(在任何時(shí)候都能用接近常數(shù)的時(shí)間檢查兩個(gè)頂點(diǎn)是否連通,甚至是在添加一條邊的時(shí)候),但深搜就必須對圖進(jìn)行預(yù)處理。
因此,在完成只需要判斷連通性或是需要完成有大量連通性查詢和插入操作混合等類似的任務(wù)時(shí),更傾向使用union-find,而深搜更適合實(shí)現(xiàn)圖的抽象數(shù)據(jù)類型,因?yàn)槟軌蚋行У睦靡延袛?shù)據(jù)結(jié)構(gòu)。
DFS已經(jīng)解決了幾個(gè)基礎(chǔ)問題。該方法很簡單,遞歸實(shí)現(xiàn)使得我們能夠進(jìn)行復(fù)雜的運(yùn)算并為一些圖的處理問題給出簡潔的解決方法。
下面對兩個(gè)問題進(jìn)行解答:
檢測環(huán):給定的圖是無環(huán)圖嗎?
雙色問題:能夠用兩種顏色將圖的所有頂點(diǎn)著色,使得任意一條邊上的兩個(gè)端點(diǎn)的顏色都不同嗎?這個(gè)問題等價(jià)于:這是一幅二分圖嗎?
檢測環(huán)解題:/** * 給定的圖是無環(huán)圖嗎 * 檢測自環(huán):假設(shè)沒有自環(huán),沒有平行邊 */ public class Cycle { private boolean[] marked; private boolean hasCycle; public Cycle(Graph g){ marked = new boolean[g.getVertexCount()]; for(int i = 0;i true false雙色問題解題/** * 雙色問題:能夠用兩種顏色將圖的所有頂點(diǎn)著色,使得任意一條邊上的兩個(gè)端點(diǎn)的顏色都不同嗎? * 等價(jià)于:判斷是否是二分圖的問題 */ public class TwoColor { private boolean[] marked; private boolean[] color; private boolean isColorable; public TwoColor(Graph g){ isColorable = true; marked = new boolean[g.getVertexCount()]; color = new boolean[g.getVertexCount()]; for(int i = 0; i true false符號圖典型應(yīng)用中,圖都是通過文件或者網(wǎng)頁定義的,使用的是字符串而非整數(shù)來表示和指代頂點(diǎn)。為了適應(yīng)這樣的應(yīng)用,定義擁有以下性質(zhì)的輸入格式:
頂點(diǎn)名為字符串
用指定的分隔符來隔開頂點(diǎn)名(允許頂點(diǎn)名中含有空格)
每一行都表示一組邊的集合,每條邊都連接著這一行的第一個(gè)名稱表示的頂點(diǎn)和其他名稱所表示的頂點(diǎn)
頂點(diǎn)總數(shù)V和邊的總數(shù)E都是隱式定義的。
例子:
API
定義了一個(gè)構(gòu)造來讀取并構(gòu)造圖,用name( )方法和index( )方法將輸入流中的頂點(diǎn)名和圖算法使用的頂點(diǎn)索引對應(yīng)起來。
測試用例例子:飛機(jī)場routes.txt--輸入機(jī)場代碼查找從該機(jī)場起飛到達(dá)的城市,但這些信息并不是直接從文件中能得到的。
例子:電影movies.txt--輸入一部電影名字得到演員列表。這不過是在照搬文件中對應(yīng)的行數(shù)據(jù),
? 但輸入演員名字 查看其出演的電影列表,相當(dāng)于反向索引。
? 盡管數(shù)據(jù)庫的構(gòu)造是為了將電影名連接到演員,二分圖模型同時(shí)也意味著將演員連接到電影名。
? 二分圖的性質(zhì)自動(dòng)完成了反向索引。這將成為處理更復(fù)雜的和圖有關(guān)的問題的基礎(chǔ)。
符號圖的實(shí)現(xiàn)SymbolGraph用到了3種數(shù)據(jù)結(jié)構(gòu):
一個(gè)符號表st,鍵的類型為String(頂點(diǎn)名),值得類型為int(索引);
一個(gè)數(shù)組keys[ ],用作反向索引,保存每個(gè)頂點(diǎn)索引對應(yīng)的頂點(diǎn)名;
一個(gè)Graph對象G,使用索引來引用圖中的頂點(diǎn)。
SymbolGraph會遍歷兩遍數(shù)據(jù)結(jié)構(gòu)來構(gòu)造以上數(shù)據(jù)結(jié)構(gòu),主要是因?yàn)闃?gòu)造Graph對象需要頂點(diǎn)總數(shù)V。在典型的實(shí)際應(yīng)用中,在定義圖的文件中指明V和E可能會不方便,從而有了SymbolGraph,這樣就可以方便地在routes.txt或者movies.txt中添加或者刪除條目而不用但系需要維護(hù)邊或者頂點(diǎn)的總數(shù)。
Java實(shí)現(xiàn)
/** * 符號圖 */ public class SymbolGraph { private HashMapmap; // key:頂點(diǎn)名 value:索引 private String[] keys; // 反向索引,保存每個(gè)頂點(diǎn)索引對應(yīng)的頂點(diǎn)名 private Graph g; // 使用索引來引用圖中的頂點(diǎn) public SymbolGraph(String path, String sp){ map = new HashMap<>(); BufferedReader reader; String line; try { reader = new BufferedReader(new FileReader(new File(path))); while((line = reader.readLine()) != null){//第一遍,構(gòu)造索引 String [] vertexs = line.split(sp); for(String s : vertexs) if(!map.containsKey(s)) map.put(s, map.size()); } reader.close(); keys = new String[map.size()]; for(String name: map.keySet()){ // 遍歷map的key,構(gòu)造頂點(diǎn)名的反向索引 keys[map.get(name)] = name; } g = new Graph(map.size()); line = ""; reader = new BufferedReader(new FileReader(new File(path))); while((line = reader.readLine()) != null){ // 第二遍,構(gòu)造圖,將每一行的頂點(diǎn)和該行其他點(diǎn)相連 String[] strs = line.split(sp); int start = map.get(strs[0]);//獲取起點(diǎn) for(int i = 1; i< strs.length; i++) g.addEdge(start, map.get(strs[i])); } reader.close(); } catch (IOException e) { e.printStackTrace(); } } /** key是一個(gè)頂點(diǎn)嗎*/ public boolean contains(String key){return map.containsKey(key);} /** key的索引*/ public int index(String key){return map.get(key);} /** 索引v的頂點(diǎn)名*/ public String name(int v){return keys[v];} /** 隱藏的Graph對象*/ public Graph graph(){return g;} public static void main(String[] args) { String dir = Cycle.class.getPackage().getName().replace(".", "/"); String path = Cycle.class.getClassLoader().getResource(dir+"/routes.txt").getPath(); SymbolGraph sg = new SymbolGraph(path, " "); Graph g = sg.graph(); HashMap map = sg.map; for(Entry s: map.entrySet()){ System.out.println(s.getKey() + "-" +s.getValue()); } System.out.println(g.toString()); String start = "JFK"; if(!sg.contains(start)){ System.out.println("起點(diǎn)"+start + " 不在數(shù)據(jù)庫."); return; } int s = sg.index(start); BreadthFirstPaths bfs = new BreadthFirstPaths(g, s); String end = "LAS"; if(!sg.contains(end)){ System.out.println("終點(diǎn)"+end + " 不在數(shù)據(jù)庫."); }else{ int t = sg.index(end); if(!bfs.hasPathTo(t)){ System.out.println(start +" 和 " + end + " 沒有路徑相同."); return; } Stack stack = bfs.pathTo(t); StringBuilder sb = new StringBuilder(); while(!stack.isEmpty()){ sb.append(sg.name(stack.pop())).append(" "); } System.out.println("起點(diǎn)"+start+"到終點(diǎn)"+end+"的路徑為:"); System.out.println(sb.toString()); } } } LAS-9 LAX-8 DFW-5 ORD-2 JFK-0 HOU-4 ATL-7 DEN-3 PHX-6 MCO-1 vertex count: 10 edge count: 18 0: [1,7,2] 1: [0,7,4] 2: [3,4,5,6,0,7] 3: [2,6,9] 4: [2,7,5,1] 5: [6,2,4] 6: [5,2,3,8,9] 7: [0,4,2,1] 8: [6,9] 9: [3,8,6] 起點(diǎn)JFK到終點(diǎn)LAS的路徑為: JFK ORD DEN LAS同樣可以把電影-演員作為例子輸入:
這個(gè)Graph實(shí)現(xiàn)允許用例用字符串代替數(shù)字索引來表示圖中的頂點(diǎn)。
它維護(hù)了
實(shí)例變量st(符號表用來映射頂點(diǎn)名和索引)
keys(數(shù)組用來映射索引和頂點(diǎn)名)
g(使用索引表示頂點(diǎn)的圖)
為了構(gòu)造這些數(shù)據(jù)結(jié)構(gòu),代碼會將圖的定義處理兩遍(定義的每一行都包含一個(gè)頂點(diǎn)以及它的相鄰頂點(diǎn)列表,用分隔符sp隔開)
間隔的度數(shù)圖處理的一個(gè)經(jīng)典問題就是,找到一個(gè)社交網(wǎng)絡(luò)之中兩個(gè)人間隔的度數(shù)。
演員K演過很多電影,為圖中每個(gè)演員附一個(gè)K數(shù):
K本人為0,
所有和K演過同一部電影的人的值為1,
所有(除K外)和K數(shù)為1的演員出演過同一部電影的人的值為2,
以此類推。
可以看到K數(shù)必須為最短電影鏈的長度,因此不用計(jì)算機(jī),很難知道。
用例DegreesOfSeparation所示,BreadthFirstPaths才是我們所需要的程序,通過最短路徑來找出movies.txt中任意演員的K數(shù)。
總結(jié)幾個(gè)基本概念:
圖的術(shù)語;
一種圖的表示方法,能夠處理大型而稀疏的圖;
和圖處理相關(guān)的類的設(shè)計(jì)模式,其實(shí)現(xiàn)算法通過在相關(guān)的類的構(gòu)造函數(shù)中對圖進(jìn)行預(yù)處理,構(gòu)造所需的數(shù)據(jù)結(jié)構(gòu)來高效支持用例對圖的查詢;
DFS&BFS
支持使用符號作為圖的頂點(diǎn)名的類。
上表總結(jié)了本節(jié)所有圖算法的實(shí)現(xiàn)。適合作為圖處理的入門學(xué)習(xí)。隨后學(xué)習(xí)復(fù)雜類型圖以及更加困難的問題時(shí),會用到這些代碼的變種。
考慮了邊的方向以及權(quán)重之后,同樣地問題會變得困難得多,但同樣地算法仍然湊效并將成為解決更復(fù)雜問題的起點(diǎn)。
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://www.ezyhdfw.cn/yun/66870.html
摘要:邊僅由兩個(gè)頂點(diǎn)連接,并且沒有方向的圖稱為無向圖。用分隔符當(dāng)前為空格,也可以是分號等分隔。深度優(yōu)先算法最簡搜索起點(diǎn)構(gòu)造函數(shù)找到與起點(diǎn)連通的其他頂點(diǎn)。路徑構(gòu)造函數(shù)接收一個(gè)頂點(diǎn),計(jì)算到與連通的每個(gè)頂點(diǎn)之間的路徑。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter...
摘要:本筆記內(nèi)容參考算法第四版書本大致框架書本分為大部分基礎(chǔ)排序查找圖字符串第一章基礎(chǔ) 本筆記內(nèi)容參考(第四版) 書本大致框架 showImg(https://segmentfault.com/img/bVXZzA?w=594&h=376);書本分為5大部分: 基礎(chǔ) 排序 查找 圖 字符串 第一章 基礎(chǔ) showImg(https://segmentfault.com/img/bV...
摘要:前文數(shù)據(jù)結(jié)構(gòu)與算法常用數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)總結(jié)了基本的數(shù)據(jù)結(jié)構(gòu),類似的,本文準(zhǔn)備總結(jié)一下一些常見的高級的數(shù)據(jù)結(jié)構(gòu)及其常見算法和對應(yīng)的實(shí)現(xiàn)以及應(yīng)用場景,務(wù)求理論與實(shí)踐一步到位。 前文 數(shù)據(jù)結(jié)構(gòu)與算法——常用數(shù)據(jù)結(jié)構(gòu)及其Java實(shí)現(xiàn) 總結(jié)了基本的數(shù)據(jù)結(jié)構(gòu),類似的,本文準(zhǔn)備總結(jié)一下一些常見的高級的數(shù)據(jù)結(jié)構(gòu)及其常見算法和對應(yīng)的Java實(shí)現(xiàn)以及應(yīng)用場景,務(wù)求理論與實(shí)踐一步到位。 跳躍表 跳躍列表是對...
閱讀 2753·2023-04-25 20:28
閱讀 1949·2021-11-22 09:34
閱讀 3778·2021-09-26 10:20
閱讀 1948·2021-09-22 16:05
閱讀 3151·2021-09-09 09:32
閱讀 2603·2021-08-31 09:40
閱讀 2179·2019-08-30 13:56
閱讀 3382·2019-08-29 17:01