国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

圖論

2019-11-14 10:03:01
字體:
來源:轉載
供稿:網友

DFS 深搜 BFS 廣搜 DAG 有向無環圖 SCC 強連通分量 BCC 雙連通分量(一般情況是同點-雙連通分量,實際上雙連通分量包括點-雙連通分量(任意兩點至少存在兩條“點不重復”的路徑)和邊-雙連通分量(任意兩點至少存在兩條“邊不重復”的路徑),下文BCC如不作特殊說明,均代表雙連通分量) 割頂:對于無向圖刪除后一個頂點x后,如果連通分量數目增加。則x稱為割頂。 割邊:……,刪掉一條邊后,連通分量數目增加,則該邊為割邊。 計算BCC,采用DFS(類似Tarjan): 點BCC:搜索遇到割點就彈棧; 邊BCC:搜索遇到割邊就彈棧。

—————————華麗分割線—————————— LCA:最近公共祖先 1、采用ST算法的倍增思想,先將待查詢點p,q“提”到同一高度,在同時向上“提”。為在線算法,預處理O(nlogn),每次查詢O(logn)。 2、采用dfs原理的Tarjan算法。為離線算法,預處理O(n),每次查詢O(1)。

—————————華麗分割線—————————— 生成樹相關 增量最小生成樹:從包含n個點的空圖開始,依次加入m條帶權邊。每加入一條邊,求圖的最小生成樹(若存在)。 先求一遍最小生成樹,之后每加入一條邊,會形成一個環,將環上最大權的邊刪去即可。而路徑唯一,隨便亂搞。時間:O(nm)。

最小瓶頸路:在無向加權圖中求給定u,v間的一條路徑使路徑上最長邊最小《==》最小生成樹上的路徑。

若干對節點最小瓶頸路:求一遍最小生成樹,1、再進行樹上倍增可在logn時間求得每組節點。2、dfs,用f(u,v)記錄(u,v間最小瓶頸路的最大邊長),每次訪問一個新節點v,考慮已訪問過的所有節點x,對f(x,v)進行更新。So時間為O(n^2)。

次小生成樹:求出最小生成樹+最小瓶頸路,枚舉加入的新邊,刪去u,v最小瓶頸路最大邊即可成為一棵新的生成樹,用其權值更新答案。時間:O(n^2)。

有向生成樹:見窩的另一篇博文~~~http://blog.csdn.net/moon1125666900/article/details/54885362


發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 德化县| 阆中市| 陕西省| 长葛市| 衡东县| 长宁区| 新邵县| 兴安县| 谢通门县| 方正县| 彭州市| 朝阳县| 东海县| 河北区| 东丰县| 奉化市| 广河县| 南华县| 柳州市| 内乡县| 灵丘县| 唐山市| 永兴县| 榆社县| 涟水县| 冕宁县| 双城市| 临汾市| 永修县| 夏津县| 共和县| 天水市| 集贤县| 观塘区| 平昌县| 上犹县| 阜康市| 铜梁县| 平乐县| 资阳市| 伊川县|