Как удалить циклы или циклы в графиках в визуальном базовом?

Question

На мой сайт есть много статей, посвященных моему вопросу. У меня есть матрица, например (10 x 10), которая представляет 10 узлов. Матрица под названием MyMat (9,9)

Строки этой матрицы представляют собой исходный узел (из узла), а столбцы представляют собой целевой узел (для узла). Он имеет 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: Нет Loop

Узел 7: Нет Loop

Узел 8: Нет Петля

Узел 9: Нет Петля

Узла 10: Нет петлю

-соединения были удалены из матрицы выше.

Я сделал это с помощью метода под названием Глубина первого поиска, но он очень медленный и нагрузка на время работы моей программы, особенно когда я использую 60 узлов и 100 соединений! Несколько примеров программирования можно найти, если вы Google это.

Есть ли более простой (быстрый) способ для этого в визуальном базовом или C#?

Answer 1

Глубина первого поиска не должна длиться очень долго.

Procedure Depth_First_Clean(graph, v){ 
    color v grey 
    for each edge (v,u){ 
    if u is grey 
     delete edge (v,u) 
    else if u is white 
     Depth_First_Clean(graph, u) 
    } 
    color v black 
} 

Procedure Clean_all(graph) { 
    Mark all nodes white 
    While there are white nodes left { 
    v = a white node 
    Depth_First_Clean(graph, v) 
    } 

Это пересекает каждый край один раз, поэтому на графике со 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 

Answer 2

Я нашел решение.

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