如何在visual basic中刪除圖形中的循環或循環？

本網站有許多關於我的問題的文章。我有一個矩陣例如（10 x 10），代表10個節點。稱爲MyMat的矩陣（9,9）如何在visual basic中刪除圖形中的循環或循環？

此矩陣的行表示源節點（來自節點），列表示目標節點（去節點）。它有14個隨機分佈的鏈接。非零值表示節點之間的連接。

 
0 0 0 0 1 0 0 0 0 0 
0 0 0 1 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 0 0 
0 0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 1 0 0 
0 0 0 1 0 0 0 0 0 1 
0 0 0 0 0 0 1 0 0 0 
0 1 1 0 0 1 0 0 0 0

我想要的是防止系統中每個節點的循環（循環）。例如：節點1：沒有迴路

節點2：2，9，7，8，10，2.這裏存在循環，因爲它以2開始並以2結束。我想要防止循環在這個網絡。這意味着：MyMat（9,1）必須爲0 節點2：2，9，7，8，10，3，2.這意味着MyMat（2,1）必須爲0

節點3：否環

節點4：4，7，8，4。這意味着MyMat（7,3）必須爲0

節點5：5，8，10，6，5這意味着，MyMat（ 5,4）必須爲0

節點6：無環路

節點7：無環

節點8：無環路

節點9：無環路

節點10：無環

4連接，從上述矩陣中刪除。

我已經通過一種稱爲深度優先搜索的技術做到了這一點，但它非常緩慢並且加重了我程序的運行時間，尤其是當我使用60個節點和100個連接時！幾個編程示例可以找到，如果你谷歌它。

有沒有更容易（更快）的方式在Visual Basic或C＃中做到這一點？

來源

2010-08-15 Aharoun Baalan

深度優先搜索不應該花很長時間。

這遍歷每個邊緣一次，所以應該幾乎沒有時間在100條邊的圖形中。

從例如OK（我要重新編號的節點擺脫一個問題，在您的例子中，混淆掉的，我們有

0 1 2 3 4 5 6 7 8 9 
0 0 0 0 0 1 0 0 0 0 0 
1 0 0 0 1 0 0 0 0 1 0 
2 0 1 0 0 0 0 0 0 0 0 
3 0 0 0 0 0 0 1 0 0 0 
4 0 0 0 0 0 0 0 1 0 0 
5 0 0 0 0 1 0 0 0 0 0 
6 0 0 0 0 0 0 0 1 0 0 
7 0 0 0 1 0 0 0 0 0 1 
8 0 0 0 0 0 0 1 0 0 0 
9 0 1 1 0 0 1 0 0 0 0 

we mark all nodes white. 
We start with node 0 
    mark node 0 grey 
    traverse edge (0,4) 
    mark node 4 grey 
     traverse edge (4, 7) 
     mark node 7 grey 
      traverse edge (7, 3) 
      mark node 3 grey 
       traverse edge (3,6) 
       mark node 6 grey 
        delete edge (6, 7) -- node 7 is grey break cycle 7 3 6 7 
       color node 6 black 
      color node 3 black 
      traverse edge (7, 9) 
      mark node 9 grey 
       traverse edge (9, 1) 
       mark node 1 grey 
        skip edge (1,3) -- 3 is black there are no cycles through 3 
        traverse edge (1, 8) 
        mark node 8 grey 
         skip edge (8, 6) 
        color node 8 black 
       color node 1 black 
       traverse edge (9, 2) 
       color node 2 grey 
        skip edge (2,1) 
       color node 2 black 
       traverse edge (9, 5) 
       color node 5 grey 
        delete edge (5, 4) 
       color node 5 black 
      color node 9 black 
     color node 7 black  
    color node 4 black  
color node 0 black  
None of the remening nodes are white so we are done

來源

2010-08-15 15:29:08 deinst

HI 感謝您的回覆。您能否用我的例子來證明您的答案？即使用我在問題中描述的邊和節點矩陣。感謝 – 2010-08-15 15:43:31

我試過，但沒有成功，請指教 LinkToSource（0） GreyList.Add（0）公共職能LinkToSource（BYVAL FROMNODE作爲整數）爲雙對於i = 0到9 如果馬特（FROMNODE，I）> 0，則如果GreyList.Contains（I）然後如果不BlackList.Contains（ⅰ）接着馬特（FROMNODE，I）= 0 BlackList.Add（ⅰ） BlackList.Add（FROMNODE） End If Else GreyList.Add（i） LinkToS wece（i） End If End If Next i End Function – 2010-08-16 18:52:14

我找到了解決辦法。

Public Function DFS3(ByVal V As Integer) As Integer 

    TheList(V) = "G" 
    For U = 0 To NumberofNodes - 1 
     If Matt(V, U) > 0 Then 
      If TheList(U) = "G" Then 
       Matt(V, U) = 0 
       RichTextBox1.AppendText("Link " & V + 1 & " " & U + 1 & " Deleted " & vbNewLine) 
      ElseIf TheList(U) = "W" Then 
       DFS3(U) 
      End If 
     End If 
    Next U 
    TheList(V) = "B" 

End Function

來源

2010-08-18 10:21:29

如何在visual basic中刪除圖形中的循環或循環？

回答

相關問題