/ / Jak usunąć cykle lub pętle na wykresach w Visual Basic? - .net, visual-studio-2008, wykres

Jak usunąć cykle lub pętle na wykresach w Visual Basic? - .net, visual-studio-2008, wykres

Na mojej stronie jest wiele artykułów dotyczących mojego pytania. Mam na przykład macierz (10 x 10), która reprezentuje 10 węzłów. Macierz o nazwie MyMat (9,9)

Wiersze tej macierzy reprezentują węzeł źródłowy(Z węzła) i kolumny reprezentują węzeł docelowy (Do węzła). Ma 14 linków, które są losowo rozmieszczone. Wartości niezerowe reprezentują połączenia między węzłami.

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

To, czego chcę, to zapobiec pętlom (cyklom) dla każdego węzła w systemie. Na przykład: Węzeł 1: Brak pętli

Węzeł 2: 2, 9, 7, 8, 10, 2. Tutaj pętla istnieje, ponieważ zaczyna się od 2 i kończy się na 2. Co chcę, aby zapobiec pętli w tej sieci. Oznacza to, że: MyMat (9,1) musi wynosić 0 Węzeł 2: 2, 9, 7, 8, 10, 3, 2. Oznacza to, że MyMat (2,1) musi mieć wartość 0

Węzeł 3: Brak pętli

Węzeł 4: 4, 7, 8, 4. Oznacza to, że MyMat (7,3) musi mieć wartość 0

Węzeł 5: 5, 8, 10, 6, 5. Oznacza to, że MyMat (5,4) musi wynosić 0

Węzeł 6: Bez pętli

Węzeł 7: Bez pętli

Węzeł 8: Bez pętli

Węzeł 9: Bez pętli

Węzeł 10: Bez pętli

4 połączenia zostały usunięte z powyższej macierzy.

Zrobiłem to dzięki technice zwanej Depthpierwsze wyszukiwanie, ale jest bardzo powolne i obciąża czas działania mojego programu, szczególnie gdy używam 60 węzłów i 100 połączeń !! Można znaleźć kilka przykładów programowania, jeśli je Google.

Czy jest łatwiejszy (szybszy) sposób to zrobić w visual basic lub C #?

Odpowiedzi:

1 dla odpowiedzi № 1

Głębokość pierwszego wyszukiwania nie powinna zająć bardzo długo.

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)
}

Przekracza to każdą krawędź raz, więc na wykresie z 100 krawędziami prawie nie ma czasu.

OK z przykładu (zamierzam zmienić numerację węzłów, aby pozbyć się pomieszania przez jeden problem w twoim przykładzie, który mamy

  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

0 dla odpowiedzi nr 2

Znalazłem rozwiązanie.

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