Qual é a maneira mais eficiente de determinar se um gráfico direcionado é conectado individualmente?

Question

Estou trabalhando em uma tarefa em que um dos problemas pede para derivar um algoritmo para verificar se um gráfico direcionado G=(V,E) está conectado individualmente (há no máximo um caminho simples de você para v para todos os vértices distintos você, v de V.

É claro que você pode verificar com força bruta, que é o que estou fazendo agora, mas quero saber se existe uma maneira mais eficiente.Alguém poderá me indicar a direção correta?

Answer 1

Você tentou Dfs.

Run DFS for every vertex in the graph as source
    If a visited vertex is encountered again, the graph is not singly connected
repeat for every unvisited vertex.
The graph is singly connected.

Complexidade o (v^2), O (v) DFS como nenhuma repetição.

Answer 2

Há uma resposta melhor para esta pergunta. Você pode fazer isso em O (| V |^2). E com mais esforço, você pode fazer isso em tempo linear.

Primeiro, você encontra componentes fortemente conectados de G. Em cada componente forte, procure para encontrar isso: 1) Se houver uma borda para a frente neste componente, ela não estará conectada individualmente, 2) Se houver uma borda cruzada neste componente , não está conectado individualmente, 3) Se houver pelo menos duas bordas nas costas em árvores enraizadas no vértice U, para os ancestrais adequados de você, então não está conectado individualmente.

Isso pode ser feito em O (E). (Acho que, exceto para o caso 3. Não pude implementá -lo bem !!).

Se nenhum dos casos acima ocorreu, você deve verificar se existe uma borda cruzada ou uma borda para a frente no G^SCC (Gráfico G, com componentes fortes substituídos por nós únicos), pois não temos apoio, isso pode ser feito por Repetindo DFs em cada vértice deste gráfico em O (| v |^2).

Answer 3

Ler Este. Realmente explica bem.

Answer 4

Não concordo que sua complexidade seja O (v^2), como no DFS, não o chamamos de todos os vértices, como veja na introdução ao livro de algoritmo também, a sintaxe é dfs (g). Chamamos apenas o DFS para o gráfico inteiro, não para nenhum vértice, diferentemente do BFS. Então, aqui neste caso, de acordo com mim, temos que verificar ligando para o DFS uma vez. ). Portanto, a complexidade será O (V+E). Como aqui e = v, portanto, a complexidade deve ser O (v).

Answer 5

Eu pensei nisso:1) Execute o DFS a partir de qualquer vértice, se todos os vértices estiverem cobertos no DFS sem arestas diretas (não pode haver cruzamento, caso contrário, nem todos os vértices serão cobertos), então pode ser um candidato potencial.

2) Se um vértice (nível j) que é encontrado no DFS tem uma borda posterior ao nível i, então nenhum outro vértice encontrado depois dele deve ter uma borda posterior em direção a qualquer vértice com nível menor que j e cada vértice deve ser acessível ao root (verificado com o segundo DFS).

Isso acontece em tempo linear, se estiver correto.

Answer 6

Dê uma olhada na definição de caminho simples. Um gráfico cíclico pode ser conectado individualmente. DFS não vai funcionar para A->B, B->A, que está conectado individualmente.

O artigo a seguir usa componente fortemente conectado para resolver isso.

https://www.cs.umd.edu/~samir/grant/khuller99.ps

Answer 7

Execute DFS uma vez de cada vértice. O gráfico está conectado individualmente se e somente se não houver bordas para a frente e não houver bordas cruzadas dentro de um componente.

Complexidade: O (VE)