標簽（空格分隔）： 學習筆記
對于圖G = （V,E）中，V代表圖的頂點，E代表頂點之間的關系，也就是我們通常說的邊。按照邊的特性我們可以將圖分為有向圖或者無向圖。但是所有的無向圖中的邊我們可以用兩條互指的有向邊進行代替，將無向圖轉換為有向圖，所以這里所有的算法都針對有向圖。
鄰接鏈表表示方法由一個包含|V|條鏈表的數組Adj所構成，每個結點有一條鏈表。對于每個結點
下圖表示了有向圖的鄰接鏈表表示方法。采用鄰接鏈表表示法的存儲空間需求為
總結：圖的鄰接鏈表存儲方式所占空間較少，可用來進行大規(guī)模圖的存儲形式，所占空間為
對于臨街矩陣表示來說，將圖表示為一個
對于無向圖來說，圖的鄰接矩陣存儲需占用
廣度優(yōu)先搜索是最簡單的圖搜索算法之一，PRim的最小生成樹算法和Dijkstra的單源最短路徑算法都使用了類似廣度優(yōu)先搜索思想。 該算法始終將已發(fā)現(xiàn)結點和未發(fā)現(xiàn)結點之間的邊界，沿其廣度方向向外擴展，也就是說，算法需要在發(fā)現(xiàn)所有距離源結點s為k的所有結點之后，才會發(fā)現(xiàn)距離源結點s為k+1的其他結點。為了跟蹤算法的進展，廣度優(yōu)先搜索在概念上將每個結點涂上白色，灰色或黑色。所有結點一開始均涂上白色，在第一次遇到一個結點時將此結點涂上灰色，并加入隊列，表示已經發(fā)現(xiàn)，在搜索了其所有子節(jié)點后，將其涂上黑色表示，然后出隊。 算法示意圖如下圖所示： 
廣度遍歷的偽碼和C++源碼如下
C++源碼
// 廣度遍歷圖void Graph::bfs(int s){ queue<int> q; q.push(s); visited[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); cout << u << " "; GNode *p = edges[u].next; while (p != NULL) { if (!visited[p->val]){ // 未被訪問，則將其加入隊列中并標志為訪問過 q.push(p->val); visited[p->val] = 1; } p = p->next; } }}void Graph::bfsTravel(){ memset(visited, 0, sizeof(int)*vertexNum); for (int i = 0; i < vertexNum; i++){ if (!visited[i]) { bfs(i); cout << endl; } }}算法的初始化成本為O(V)，每個結點進行一次入隊出隊操作，因此隊列操作時間為O(V)，掃描鄰接鏈表總時間為O(E)。算法總復雜度為O(V+E)，因此廣度搜索時間是圖G的鄰接鏈表大小的一個線性函數。
深度優(yōu)先搜索算法總是對最近才發(fā)現(xiàn)的結點v的出發(fā)邊進行探索，直到該結點的所有出發(fā)邊都被發(fā)現(xiàn)為止。一旦結點v的所有邊都被發(fā)現(xiàn)，搜索則“回溯”到v的前驅結點（v是經過該節(jié)點才被發(fā)現(xiàn)的），來搜索改前驅結點的出發(fā)邊。該過程一直持續(xù)到從源結點可以達到的所有結點都被發(fā)現(xiàn)為止。如果還存在未發(fā)現(xiàn)的節(jié)點，則深度優(yōu)先搜索將從這些未發(fā)現(xiàn)的結點中任選一個作為一個新的源結點，并重復同樣的搜索過程，直到所有結點被發(fā)現(xiàn)為止。
深度優(yōu)先搜索的前驅子圖可以形成一個由多棵深度優(yōu)先樹構成的深度優(yōu)先森林。 在算法中與廣度優(yōu)先搜索相同的是依然用白色、灰色或黑色標記未發(fā)現(xiàn)、剛發(fā)現(xiàn)、已經搜索完畢的結點。不同的是，深度優(yōu)先使用兩個時間戳來代替源點s到v的距離，第一個時間戳v.d記錄結點v第一次被發(fā)現(xiàn)的時間（涂上灰色的時候），第二個時間戳v.f記錄的是搜索完成對v的鄰接鏈表掃描的時間（涂上黑色的時候），這些時間戳提供了圖結構的重要信息，通常能夠幫助推斷深度優(yōu)先搜索算法的行為，比如在拓撲排序應用中就起到了重要作用。
算法示意圖： 
算法偽代碼如下所示：
算法總復雜度為O(V+E)。
拓撲排序首先需要圖G為有向無環(huán)圖，它是G中所有結點的一種線性次序，該次序滿足如下條件：如果圖G包含邊(u, v)，則結點u在拓撲排序中處于結點v的前面。許多實際應用中都需要使用有向無環(huán)圖來指明事件的優(yōu)先次序，拓撲排序可以找出這些進行事件的合理順序。
拓撲排序算法其實很簡單，分為兩步：第一步，對有向無環(huán)圖進行深度優(yōu)先搜索排序；第二步，將所有結點按照其完成的時間的逆序從左向右排序，此時所有的有向邊都是從左指向右。證明神馬的具體見算法導論吧。
算法示意圖(早上穿衣過程)： 
算法偽代碼：
算法第一步深度優(yōu)先搜索算法按時間復雜度為O(V+E)，第二步將結點插入鏈表最前端所需的時間為O(V)，所以總的時間復雜度為O(V+E)。
另外還有一種拓撲排序算法，其思想為首先選擇一個無前驅的頂點（即入度為0的頂點，圖中至少應有一個這樣的頂點，否則肯定存在回路），然后從圖中移去該頂點以及由他發(fā)出的所有有向邊，如果圖中還存在無前驅的頂點，則重復上述操作，直到操作無法進行。如果圖不為空，說明圖中存在回路，無法進行拓撲排序；否則移出的頂點的順序就是對該圖的一個拓撲排序。
算法偽代碼：
Topological_Sort_II(G); begin for 每個頂點u∈V[G] do d[u]←0; //初始化d[u],d[u]用來記錄頂點u的入度 for 每個頂點u∈V[G] do for 每個頂點v∈Adj[u] do d[v]←d[v]+1; //統(tǒng)計每個頂點的入度 CreateStack(s); //建立一個堆棧s for 每個頂點u∈V[G] do if d[u]=0 then push(u,s); //將度為0的頂點壓入堆棧 count←0; while (not Empty(s)) do begin u←top(s); //取出棧頂元素 pop(s); //彈出一個棧頂元素 count←count+1; R[count]←u; //線性表R用來記錄拓撲排序的結果 for 每個頂點v∈Adj[u] do //對于每個和u相鄰的節(jié)點v begin d[v]←d[v]-1; if d[v]=0 then push(v,s); //如果出現(xiàn)入度為0的頂點將其壓入棧 end; end; if count<>G.size then writeln('Error! The graph has cycle.') else 按次序輸出R; end;上面的算法中利用d[u]來記錄頂點u的入度，第5-7行用來統(tǒng)計所有頂點的入度，第11-12行將入度為0的頂點壓入堆棧，第16-29行不斷地從棧頂取出頂點，將該頂點輸出到拓撲序列中，并將所有與該頂點相鄰的頂點的入度減1，如果某個頂點的入度減至0，則壓入堆棧，重復該過程直到堆棧空了為止。顯而易見該算法的復雜度為O(VE)，因為第5-7行的復雜性就是O(VE)，后面16-29行的復雜性也是O(VE)。這個算法雖然簡單，但是沒有前面一個算法的效率高。
新聞熱點
疑難解答
