Как удалить циклы или петли в графах в Visual Basic?

Question

На этом сайте много статей по моему вопросу.У меня есть матрица, например (10 х 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 Node 2: 2, 9, 7, 8, 10, 3, 2. Это означает, что MyMat (2,1) должно быть 0

Node 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 соединений !!Несколько примеров программирования можно найти в Google.

Есть ли более простой (более быстрый) способ сделать это в Visual Basic или 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 ребрами это почти не займет времени.

ОК из примера (я собираюсь изменить нумерацию узлов, чтобы избавиться от путаницы, вызванной одной проблемой в вашем примере, у нас есть

  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