Comment supprimer des cycles ou des boucles dans les graphiques en Visual basic?

Question

Il y a beaucoup d'articles dans ce site concernant ma question. J'ai une matrice par exemple (10 x 10) qui représente 10 nœuds. La matrice appelée MyMat (9,9)

Les lignes de cette matrice représentent le noeud de source (à partir du noeud) et les colonnes représentent noeud cible (To Node). Il a 14 liens qui sont distribués au hasard. Les valeurs non nulles représentent les connexions entre les nœuds.

 
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 

Ce que je veux est d'empêcher les boucles (cycles) pour chaque noeud dans le système. Par exemple: Noeud 1: No loop

Noeud 2: 2, 9, 7, 8, 10, 2. Ici, la boucle existe car elle a commencé par 2 et s'est terminée par 2. Ce que je veux empêcher les boucles ce réseau. Cela signifie que: MyMat (9,1) doit être 0 Nœud 2: 2, 9, 7, 8, 10, 3, 2. Cela signifie que MyMat (2,1) doit être 0

Nœud 3: Non boucle

Node 4: 4, 7, 8, 4. Cela signifie que MyMat (7,3) doit être 0

noeud 5: 5, 8, 10, 6, 5. Cela signifie que MyMat (5,4) doit être 0

Noeud 6: pas de boucle

Noeud 7: pas de boucle

Node 8: pas de boucle

noeud 9: pas de boucle

noeud 10: pas de boucle

4 connexions ci-dessus ont été supprimés de la matrice.

Je l'ai fait par une technique appelée profondeur première recherche, mais il est très lent et charge le temps d'exécution de mon programme surtout quand j'utilise 60 noeuds et 100 connexions !! Plusieurs exemples de programmation peuvent être trouvés si vous l'utilisez.

est-il un moyen plus facile (plus rapide) pour faire cela en Visual Basic ou C#?

Answer 1

Profondeur première recherche ne devrait pas prendre très longtemps à tous.

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

Ceci traverse chaque arête une fois, donc ne devrait pas prendre presque de temps dans un graphique avec 100 arêtes.

OK de l'exemple (je vais numéroter les nœuds pour se débarrasser de la confusion hors d'un problème dans votre exemple, nous avons

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

Je trouve la solution.

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