Existem muitos artigos neste site sobre a minha pergunta. Eu tenho uma matriz, por exemplo (10 x 10), que representa 10 nós. A matriz chamada MyMat (9,9)
As linhas dessa matriz representam o nó de origem(Do nó) e as colunas representam o nó de destino (para o nó). Tem 14 links que são distribuídos aleatoriamente. Os valores não zero representam as conexões entre os nós.
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
O que eu quero é evitar os loops (ciclos) para cada nó no sistema. Por exemplo: Nó 1: sem loop
Nodo 2: 2, 9, 7, 8, 10, 2. Aqui o loop existe porque começou com 2 e terminou com 2. O que eu quero evitar os loops nesta rede. Isso significa que: MyMat (9,1) deve ser 0 Nó 2: 2, 9, 7, 8, 10, 3, 2. Isso significa que MyMat (2,1) deve ser 0
Nó 3: sem loop
Nó 4: 4, 7, 8, 4. Isso significa que MyMat (7,3) deve ser 0
Nó 5: 5, 8, 10, 6, 5. Isso significa que MyMat (5,4) deve ser 0
Nó 6: sem loop
Nó 7: sem loop
Nó 8: sem loop
Nó 9: sem loop
Nó 10: sem loop
4 conexões foram deletadas da matriz acima.
Eu fiz isso através de uma técnica chamada Profundidadeprimeira pesquisa, mas é muito lento e sobrecarregar o tempo de execução do meu programa, especialmente quando eu uso 60 nós e 100 conexões! Vários exemplos de programação podem ser encontrados no Google.
Existe uma maneira mais fácil (mais rápida) de fazer isso em visual basic ou C #?
Respostas:
1 para resposta № 1A primeira pesquisa de profundidade não deve levar muito tempo a todos.
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)
}
Isso percorre cada borda uma vez, portanto, não deve demorar quase nada em um gráfico com 100 arestas.
OK do exemplo (eu estou indo para renumerar os nós para se livrar do confuso por um problema em seu exemplo, temos
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 para resposta № 2
Eu encontrei a solução.
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