找到兩個節點之間的隱藏節點 - 圖 - java的

我的英文不是很好，但我會盡我所能在這裏解釋我的問題。我正在研究一個我必須創建圖形的應用程序。目前我正在使用GraphStream。找到兩個節點之間的隱藏節點 - 圖 - java的

我圖的要求是非常複雜的，這就是：

我有一個名爲CDR表（呼叫數據記錄），其中我有2列A-號碼和B-號碼。表的結構非常清楚，它表明Anumber稱爲Bnumber，並且還有另一個DATETIME列，它顯示了調用的日期和時間。但我只需要兩列。

比方說，我們有4個數字的位置：123，456，789，000，表結構是這樣的

Anumber Bnumber 
------- ------- 
123  456 
123  789 
456  789 
789  000 
456  000

我的表在這裏清楚地表明，123並沒有撥打000，但123叫456和789而這兩個數字叫000所以我必須拿出向圖可能這樣表示123->456->000和132->789->000

所以，問題是我不知道如何找到123和000之間的路徑123和000之間。可能有2個以上的數字，比如5或6個數字，我有e找到所有給定的5或6個數字之間的隱藏數字AS在上述場景中456和789是隱藏數字132和000之間的數字。

另外一個問題是我的表格包含超過2000萬行，隨着用戶相互呼叫，行數將增長得非常快。

我做了什麼至今：

我已經做了一些[R & d在這個問題上，但可以沒有發現任何好的庫或這方面的任何解決方案。到目前爲止，我認爲Dijkstra's Algorithm是最適合我的情況作爲GraphStream幸運的是，提供了這種算法here。

我從你們想要什麼，給我一個想法，將這個算法會給我需要的結果，或者我要找到這將西裝最適合我的問題，任何其他算法中或圖形庫。我不擅長ALGO這就是爲什麼我在這裏得到任何幫助或指導如果你們可以給我。感謝

來源

2017-07-20 Noob Player

在您鏈接的網頁，它說，有一些方法來遍歷的最短路徑。（getPathEdges（Node），getPathEdgesIterator（Node），getPathNodes（Node）和getPathNodesIterator（Node））。我相信getPathEdges（Node）和getPathNodes（Node）會爲您提供所需的信息。嘗試使用它們並評論他們是否做了這項工作。 –

當然。我會嘗試一下，如果它根據我的需求發佈，我會在這裏發佈我的解決方案 –

不過，我建議您自己理解並實現Dijkstra的算法。這並不難理解，而且這種方式可以對其進行修改，以滿足您的任何需求。 –

你不需要Dijkstra算法在所有的，因爲你沒有在邊緣上的成本。您需要簡單的BFS算法。下面是簡單的implementation但你應該加上「標籤」陣列來標記訪問節點。因此，在BFS之後，您可以從每個節點到源節點（在您的情況下爲123）恢復傳遞，或者說從給定節點（如果此節點的標籤保持爲0）無法到達節點。您應該通過以下方式添加標籤：

所有標籤上開始

等於0，當您訪問新節點設置它的標籤爲current_node_label + 1

但Dijkstra的可以幫助你，如果你設置成本每條邊的邊界都是1.它只是解決問題的有效方法。

來源

2017-07-20 12:53:44

找到兩個節點之間的隱藏節點 - 圖 - java的

回答

相關問題