Ci sono molti articoli in questo sito riguardanti la mia domanda. Ho una matrice per esempio (10 x 10) che rappresenta 10 nodi. La matrice denominata MyMat (9,9)
Le righe di questa matrice rappresentano il nodo di origine(Dal nodo) e le colonne rappresentano il nodo di destinazione (al nodo). Ha 14 collegamenti che sono distribuiti casualmente. I valori diversi da zero rappresentano le connessioni tra i nodi.
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
Quello che voglio è prevenire i cicli (cicli) per ogni nodo nel sistema. Per esempio: Nodo 1: nessun loop
Nodo 2: 2, 9, 7, 8, 10, 2. Qui il ciclo esiste perché è iniziato con 2 e ha terminato con 2. Cosa voglio impedire i loop in questa rete. Ciò significa che: MyMat (9,1) deve essere 0 Nodo 2: 2, 9, 7, 8, 10, 3, 2. Ciò significa che MyMat (2,1) deve essere 0
Nodo 3: nessun loop
Nodo 4: 4, 7, 8, 4. Ciò significa che MyMat (7,3) deve essere 0
Nodo 5: 5, 8, 10, 6, 5. Ciò significa che MyMat (5,4) deve essere 0
Nodo 6: nessun loop
Nodo 7: nessun loop
Nodo 8: nessun loop
Nodo 9: nessun loop
Nodo 10: nessun loop
4 connessioni sono state cancellate dalla matrice superiore.
L'ho fatto tramite una tecnica chiamata Depthprima ricerca ma è molto lento e oneroso il tempo di esecuzione del mio programma soprattutto quando uso 60 nodi e 100 connessioni !! Diversi esempi di programmazione possono essere trovati se lo fai su Google.
C'è un modo più semplice (più veloce) per farlo in Visual Basic o C #?
risposte:
1 per risposta № 1La prima ricerca della profondità non dovrebbe richiedere molto tempo.
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)
}
Questo attraversa ogni spigolo una volta, quindi non dovrebbe impiegare quasi tempo in un grafico con 100 spigoli.
OK dall'esempio (ho intenzione di rinumerare i nodi per sbarazzarsi della confusione di un problema nel tuo esempio che abbiamo
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 per risposta № 2
Ho trovato la soluzione.
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