C++算法-圖算法-03

?

?

圖處理問題 圖問題按照解決難度，可以粗略分為如下幾類： 1.簡單。簡單問題在最壞情況下運行是線性的。 簡單連通性 一個給定的圖是連通的嗎？ 有向圖中的強連通 有向圖中的每對頂點，是否存在一條彼此連接的有向路徑？ 傳遞閉包 有向圖中，由各個頂點出發，沿著有向邊可以到達哪些頂點？ 最小生成樹 加權圖中，找到連接所有頂點的邊集，且其權值最小。 單源最短路徑 加權有向圖中，將一個給定頂點v與圖中各個頂點相連的最短路徑是什么？ 2.易處理。對于這種問題已經有一種算法，而且可以保證該算法的時間和空間需求由圖規模(V+E)的一個多項式函數所限定。 平面性 是否可以畫出一個給定圖，并且用來表示邊的任何線段都不相交？ 庫拉托夫斯基定理：無法在沒有邊交叉的條件下畫出的圖僅為如下的圖，即它們包括一些子圖，刪除這些子圖中度數為2的頂點后，相應子圖與圖平面圖中的禁止子圖（略）所示的某個圖同構。 匹配 給定一個圖，對于其邊的某些子集，其中任意兩條邊都不會連接到同一個頂點上，那么滿足此屬性的最大邊子集是什么？ 有向圖中的偶環 一個給定的有向圖中，是否存在一個長度為偶數的環？ 指派 二部加權匹配，它是在一個二部圖中找到一種最小權值的最佳匹配。網絡流算法 一般連通性 如果將圖中的某條邊刪除，將把這個圖分解為不相交的兩個部分，那么這種邊最少是多少（邊連通性）？ 郵差問題 給定一個圖，找出一條變數最小的周游路徑，該圖中的每條邊至少使用了一次（不過允許多次使用邊）。 3.難處理。尚無已知的算法可以保證在一個合理的時間內解決此問題。 NP難問題。 最長路徑 在一個圖中，連接兩個給定頂點的最長簡單路徑是什么？ 著色問題 是否存在一種方法可以為圖中的每個頂點著色，其可選顏色有k種，要求不存在連接相同顏色頂點的邊。 獨立集 存在一些圖頂點子集，其中任何兩個頂點都未由邊相連，那么滿足這種屬性的最大頂點子集的規模如何？ 包 在一個給定圖中，最大包（完全子圖）的規模是多少？ 4.未知。既不知道其存在高效的算法，也未認定它們是NP難問題。 圖同構 通過對頂點的重命名，能否使兩個給定的圖相同？

轉載于:https://blog.51cto.com/spider20030901/526268

總結

以上是生活随笔為你收集整理的C++图算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。