Em uma primeira árvore de profundidade, existem as bordas que definem a árvore (ou seja, as bordas que foram usadas na traversal).
Existem algumas arestas restantes conectando alguns dos outros nós. Qual é a diferença entre uma borda cruzada e uma borda frontal?
Da wikipedia:
Com base nesta árvore de abrangência, as bordas do grafo original pode ser dividido em três classes: arestas avançadas, que apontam de um nó da árvore para um de seus descendentes, arestas posteriores, que apontam de um nó para um de seus ancestrais, e arestas cruzadas, que não fazem nenhuma das duas coisas. Às vezes, as arestas da árvore, arestas que pertencem à própria árvore de abrangência, são classificadas separadamente das arestas anteriores. Se o gráfico original não está direcionado, então todas as suas arestas são arestas de árvore ou arestas traseiras.
Não é uma aresta que não seja usada na travessia que pontos de um nó para outro estabelecem uma relação pai-filho?
Comentários
- Relacionados: cs.stackexchange.com/questions/99988/… busca estabelecer um algoritmo que, para grafo direcionado, irá preferir fazer arestas à frente, em vez de arestas cruzadas, durante pesquisa em profundidade.
Resposta
A Wikipedia tem a resposta:
Todos os tipos de arestas aparecem nesta imagem. Trace DFS neste gráfico (os nós são explorados em ordem numérica) e veja onde seu a intuição falha.
Isso irá explicar o diagrama: –
Borda frontal: (u, v), onde v é um descendente de u, mas não é uma borda da árvore . É uma borda fora da árvore que conecta um vértice a um descendente em uma árvore DFS.
Borda cruzada: qualquer outra borda. Pode ir entre vértices na mesma árvore de profundidade ou em diferentes árvores de profundidade. (leigo)
É qualquer outra aresta no gráfico G. Ela conecta vértices em duas árvores DFS diferentes ou dois vértices na mesma árvore DFS, nenhum dos quais é o ancestral do outro. (formal)
Comentários
- Por que não é impossível que 6 tenha sido percorrido primeiro (lado direito primeiro)? Se isso tivesse acontecido, como a borda 2- > 3 teria sido chamada?
- @soandos, sugiro que você dedique algum tempo para rastrear o algoritmo. Supondo que os wikipedistas não ‘ cometeram um erro, a imagem descreve uma execução genuína do DFS neste gráfico e, portanto, há uma maneira de ajustar o algoritmo neste rastreamento. Os tipos de arestas são descritos com clareza na Wikipedia, e você também pode consultar este exemplo.
- Entendo que esta é uma maneira válida de fazer um DFS. Estou simplesmente perguntando e se fosse feito de outra maneira.
- Então, os resultados seriam diferentes. Eu ‘ sinto muito, você ‘ teria que resolver isso sozinho.
- @soandos Em geral, há pode muito bem ser várias travessias DFS. As noções usadas aqui são relativas a uma dada travessia e serão diferentes para várias travessias.
Resposta
Um percurso DFS em um grafo não direcionado não deixará uma aresta cruzada, pois todas as arestas que incidem em um vértice são exploradas.
No entanto, em um grafo direcionado, você pode encontrar uma aresta isso leva a um vértice que foi descoberto antes, de modo que esse vértice não é um ancestral ou descendente do vértice atual. Essa borda é chamada de borda cruzada.
Comentários
- Aporov, Obrigado pela resposta. Ainda me parece que quando você chega ao vértice 6 no DFS conforme diagramado na Wikipedia, você tem três arestas para atravessar a partir de 6. Nesse ponto, o vértice 6 é ” atual “. Eventualmente, você vai atravessar a aresta até o vértice 3. Embora 3 já tenha sido visitado, no entanto, como há uma aresta de 6 a 3, então 3 é um descendente da corrente ” ” vértice 6. Se for assim, ele viola a definição de uma aresta cruzada. Deve haver algo mais na definição que não está ‘ sendo tornada muito explícita.
- Na verdade, o DFS contém apenas as arestas da árvore para as arestas posteriores (introdução a Algoritmos Thm. 22.10).
Resposta
Em uma passagem DFS, os nós são concluídos quando todos os seus filhos são finalizado. Se você marcar os tempos de descoberta e término para cada nó durante a travessia, poderá verificar se um nó é descendente comparando os tempos de início e término. Na verdade, qualquer passagem DFS irá particionar suas arestas de acordo com a seguinte regra.
Seja d [nó] o tempo de descoberta do nó, da mesma forma seja f [nó] o tempo de término.
Teorema dos parênteses Para todo u, v, exatamente um dos seguintes se aplica:
1.d [u] < f [u] < d [v] < f [ v] ou d [v] < f [v] < d [u] < f [u] e nenhum de uev é descendente do outro.
d [u] < d [v] < f [v] < f [u] ev é um descendente de u.
d [v] < d [u] < f [u] < f [v] e u são descendentes de v.
Portanto, d [u] < d [v] < f [u] < f [v] não pode acontecer.
Como parênteses: () [], ([]) e [()] estão OK, mas ([)] e [(]) não estão OK.
Por exemplo, considere o gráfico com arestas:
A -> B
A -> C
B -> C
Deixe a ordem de visita ser representada por uma sequência de rótulos de nós, onde “ABCCBA” significa A -> B -> C (finalizado) B (finalizado) A (finalizado), semelhante a ((())).
Portanto, “ACCBBA” poderia ser um modelo para “() ())”.
Exemplos:
“CCABBA”: Então A -> C é uma cruz borda, já que o CC não está dentro de A.
“ABCCBA”: Então A -> C é uma borda dianteira (descendente indireto).
“ACCBBA”: Então A -> C é uma borda da árvore (descendente direto).
Fontes:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Notas da aula http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm