如何在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中删除图形中的循环或循环？

回答

相关问题