【正文】 NOIP 圖的常用算法簡介 石 門 中 學(xué) 江 濤 目 錄 ? 圖 的表示 鄰 接矩 陣 、 鄰 接 鏈 表、 圖 的遍 歷 ? 最 小 生成 樹 算法 Prim算法、 Kruskal算法 ? 最短 路 徑 算法 Dijkstra算法、 Bellman_Ford算法及 SPFA算法、 Floyd算法 目 錄 ? 圖 的表示 鄰 接矩 陣 、 鄰 接 鏈 表、 圖 的遍 歷 ? 最 小 生成 樹 算法 Prim算法、 Kruskal算法 ? 最短 路 徑 算法 Dijkstra算法、 Bellman_Ford算法及 SPFA算法、 Floyd算法 ? 頂點(diǎn) ? 給點(diǎn)編號為連續(xù)的整數(shù) ? 把頂點(diǎn)存放在數(shù)組中 ? 邊 ? 鄰接矩陣 ? 布爾值 (或邊權(quán)值 ) TRUE – 有邊 FALSE – 無邊 ? 空間復(fù)雜度 O(|V|2) 圖的表示 鄰 接矩 陣 ? 邊 ? 鄰接鏈表 ? 每一個(gè)頂點(diǎn) ? 有一個(gè)所有與之相鄰的鏈表 ? 每一條邊 ? 2 個(gè)（對 無向圖 ） ? 要在兩個(gè)頂點(diǎn)的鏈表中都加入 ? 空間復(fù)雜度 O(|E|) ? 對稀疏圖這種方式比較好 圖的表示 鄰 接 鏈 表 圖的鄰接鏈表的 Pascal和 C++實(shí)現(xiàn) 具體參見 《 NOIP基礎(chǔ)數(shù)據(jù)結(jié)構(gòu) 》 ppt 圖的表示 C/P語 言程序 實(shí)現(xiàn) 圖的深度優(yōu)先 (DepthFirst)遍歷 :鄰接鏈表、 C++ 圖的表示 圖 的遍 歷 //圖的一般結(jié)構(gòu) struct graph_node{ … }。 struct AdjList { int id。 AdjList *next。 }。 int n_nodes,S_index=0。 graph_node nodes[ maxN ]。 int visited[ maxN ]。 AdjList *adj[ maxN ]。 標(biāo)識項(xiàng)點(diǎn)有沒有訪問過 每個(gè)頂點(diǎn)都有鄰接鏈表 鄰接鏈表的節(jié)點(diǎn) 數(shù)據(jù)結(jié)構(gòu) 圖的深度優(yōu)先 (DepthFirst)遍歷 :鄰接鏈表、 C++ 圖的表示 圖 的遍 歷 置每個(gè)點(diǎn)標(biāo)識為“未訪問” 從所有未被訪問 的點(diǎn) k出發(fā)， 調(diào)用 DFS(k) void search( ) { int k。 for(k=0。kn_nodes。k++) visited[k] = 0。 for(k=0。kn_nodes。k++) if ( !visited[k] ) DFS( k )。 } 置被訪問節(jié)點(diǎn)的 “時(shí)間” 次序 訪問 k的所有相鄰的節(jié)點(diǎn) void DFS( int k ) { //從 k出發(fā)搜索 AdjList *j。 visited[k] = ++S_index。 for(j=adj[k]。j!=NULL。 j=jnext) { if ( !visited[jid] ) DFS( jid )。 } 圖的深度優(yōu)先 (DepthFirst)遍歷 :鄰接鏈表、 Pascal 圖的表示 圖 的遍 歷 //圖的一般結(jié)構(gòu) type graph_node=record … end。 type AdjList=record id :integer。 next :^AdjList。 end。 var n_nodes,S_i:integer。 nodes:array[1..maxN] of graph_node。 visited:array[1..maxN]of integer。 adj:array[1..maxN] of ^AdjList。 標(biāo)識項(xiàng)點(diǎn)有沒有訪問過 每個(gè)頂點(diǎn)都有鄰接鏈表 鄰接鏈表的節(jié)點(diǎn) 數(shù)據(jù)結(jié)構(gòu) 圖的深度優(yōu)先 (DepthFirst)遍歷 :鄰接鏈表、 Pascal 圖的表示 圖 的遍 歷 置每個(gè)點(diǎn)標(biāo)識為“未訪問” 從所有未被訪問 的點(diǎn) k出發(fā)， 調(diào)用 DFS(k) procedure search( )。 begin k :integer。 for k:=1 to n_nodes do visited[k]:= 0。 for k:=1 to n_nodes do if visited[k]0 then DFS( k )。 end。 置被訪問節(jié)點(diǎn)的 “時(shí)間” 次序 訪問 k的所有相鄰的節(jié)點(diǎn) procedure DFS(k:integer)。begin //從 k出發(fā)搜索 var j:^AdjList 。 begin inc(S_i)。visited[k]:=S_i。 j:=adj[k]。 while (jNULL) do begin if visited[j^.id]0 then DFS(j^.id)。 j:=j^.next。 end。 end。 圖的寬度優(yōu)先 (BreadthFirst)遍歷 :鄰接鏈表、 C++ 圖的表示 圖 的遍 歷 //圖的一般結(jié)構(gòu) struct graph_node{ … }。 struct AdjList { int id。 AdjList *next。 }。 int n_nodes,S_index=0。 graph_node nodes[ maxN ]。 int visited[ maxN ]。 AdjList *adj[ maxN ]。 標(biāo)識項(xiàng)點(diǎn)有沒有訪問過 每個(gè)頂點(diǎn)都有鄰接鏈表 鄰接鏈表的節(jié)點(diǎn) 數(shù)據(jù)結(jié)構(gòu) 圖的寬度優(yōu)先 (BreadthFirst)遍歷 :鄰接鏈表、 C++ 圖的表示 圖 的遍 歷 置每個(gè)點(diǎn)標(biāo)識為“未訪問” 從所有未被訪問 的點(diǎn) k出發(fā)， 調(diào)用 BFS(k) void search( ) { int k。 for(k=0。kn_nodes。k++) visited[k] = 0。 for(k=0。kn_nodes。k++) if ( !visited[k] ) BFS( k )。 } 圖的寬度優(yōu)先 (BreadthFirst)遍歷 :鄰接鏈表、 C++ 圖的表示 圖 的遍 歷 int q[ maxN ]。 void BFS( int k ) { int front,back。 q[0]=k。 front=back=0。 for(。fron=back。 fron++){ k = q[front]。 visited[k] = ++search_index。 for(Adjlist *j=adj[k]。j!=NULL。j=jnext){ if ( !visited[jid] ) { q[++back]=jid。 visited[jid]=++S_index。 } } } } BFS用的隊(duì)列，一般 全局 Front=back,隊(duì)列不空 訪問 k的所有相鄰的節(jié)點(diǎn) 圖的寬度優(yōu)先 (BreadthFirst)遍歷實(shí)例示意 : 圖的表示 圖 的遍 歷 目 錄 ? 圖 的表示 鄰 接矩 陣 、 鄰 接 鏈 表、 圖 的遍 歷 ? 最 小 生成 樹 算法 Prim算法、 Kruskal算法 ? 最短 路 徑 算法 Dijkstra算法、 Bellman_Ford算法及 SPF