minimum-spanning-tree

6熱度

2回答

我從Robert Sedgewick的算法書中得到了這個問題。關鍵邊緣。從圖中刪除會導致MST權重增加的MST邊稱爲臨界邊。顯示如何在與E log E成比例的時間內查找所有關鍵邊的時間。注意：此問題假設邊緣權重不一定是不同的（否則MST中的所有邊都是關鍵的）。請提出解決此問題的算法。我能想到的一種方法是在時間上做這項工作E.V. 我的方法是運行kruskal的算法。但是，無論何時我們遇到在

0熱度

2回答

如何運行Dijkestra算法使其與Prim類似並生成MST？

假設我正在運行Dijkstra算法來訪問所有節點（而不是原始初始節點和目標節點），即我正在檢查所有節點是否被訪問，而不是目標節點。此算法是否會生成MST（最小生成樹）？（它是否類似於Prim？）

1熱度

1回答

尋找最小/最大重量斯坦納樹

我在reddit上問過這個問題，但還沒有收斂到解決方案。由於我的許多搜索將我帶入Stack Overflow，因此我決定嘗試一下。下面是我的問題的一個簡單公式：給定一個加權無向圖G（V，E，w）和G中頂點S的子集，找到跨越S的最小/最大權重樹。添加頂點不是允許。基本模型的擴展是添加0重量的邊，以及必須排除的頂點。這似乎類似的問題在這裏問： Algorithm to find minimum sp

0熱度

2回答

Prim算法的動態位置

假設你有一個輸入文件： <total vertices> <x-coordinate 1st location><y-coordinate 1st location> <x-coordinate 2nd location><y-coordinate 2nd location> <x-coordinate 3rd location><y-coordinate 3rd location> ..

0熱度

1回答

克魯斯卡爾算法生成的邊緣集合

設G =（V，E）爲加權的連通無向圖。設T是在Kruskal算法中生長的邊集，並在k次迭代後停止（因此T可能包含小於| E | -1的邊）。設W（T）是該集合的加權和。設T'爲非零邊集，使| T | = | T'|。證明W（T）< = W（T'）我理解算法的原始證明，並且我嘗試了幾種方法來解決這個問題，但都沒有成功。例如：我認爲在| T |可能會工作。 For | T | = 1很明顯。我們

10熱度

4回答

在Python中建模圖形

我正試圖解決與Python圖形相關的問題。由於它是一個令人眼花繚亂的編程問題，我沒有使用任何其他第三方軟件包。該問題以5 X 5正方形網格的形式呈現圖形。假定機器人位於用戶在網格上的位置。網格索引爲左上角的(0,0)，右下角爲(4,4)。網格中的每個單元格均由以下3個字符中的任何一個表示。 'b'（ascii值98）指示機器人的當前位置，'d'（ascii值100）指示髒單元並且' - '（A

3熱度

1回答

什麼是最小跨越森林？

最小生成樹給出了一個無向圖最廉價的方法。但什麼是最小跨越森林？它是針對連通圖還是未連接圖定義的？

0熱度

1回答

描述決定是否有完全2個不同MST的算法

設G =（V，E）爲加權的，連通的和無向的圖。描述了一個高效的算法，決定是否有G. ，我已經解決了是輕鬆了許多以前的問題恰好2個不同的MSTS：描述一個高效的算法，決定是否有隻有一個MST在G. 這就是我解決後一個問題的方法：我們運行Kruskal算法，然後用藍色着色新的MST的邊緣，其餘的邊緣用紅色着色。然後，我用另一個簡單的算法，我們已經看到（使用Kruskal），在包含最大數量的紅色邊

0熱度

1回答

java網絡接受線程之間的網絡連接

在Java中，我創建了256個使用網絡套接字相互通信的線程。所有這256個線程並行運行。當一個線程被產生時，它會嘗試連接到它的鄰居線程。鄰居列表可以是任意的。在這種情況下，如何保證所有的線程創建與他們的鄰居沒有僵局沒有一個星型拓撲結構的連接（中心節點）爲了形成兩者之間的連接線程，一個線程必須打開一個ServerSocket和其他線程必須加入它。目前，我使用的是簡單的算法： for all

5熱度

1回答

在「IGRAPH」創建一個加權無向圖中的C/C++

問題：我想用的igraph使從存儲在.csv文件鄰接矩陣加權無向圖，然後做最小生成樹和它的一些其他算法。我開始製作一個有10個頂點和5個邊的有向圖。默認情況下，igraph不允許使用邊的權重，你必須使用一些對我無意義的屬性（如igraph_i_set_attribute_table）。有人可以幫助我解決這個問題。 void print_vector(igraph_vector_t *v, F