Se todas as arestas tiverem o mesmo peso, pode-se usar o BFS para obter uma árvore de abrangência mínima?

Se dado que todas as arestas de um gráfico têm peso igual , pode-se usar a pesquisa de largura em primeiro lugar (BFS) para produzir uma árvore de abrangência mínima em tempo linear ? $G$ $c$

Intuitivamente isto soa corrigir, como BFS não visita um nó duas vezes, e só atravessa do vértice para o vértice sse ela não visitou antes, de modo que não vai ser qualquer ciclo, e se é conectado acabará por visitar todos os nós. Como o peso de todas as arestas é igual, não importa quais arestas o BFS escolheu. $v$ $u$ $u$ $G$

Meu raciocínio faz algum sentido?

algorithms graphs spanning-trees TheNotMe
fonte

Respostas:

Se o seu gráfico não for ponderado, ou equivalente, todas as arestas tiverem o mesmo peso, qualquer árvore de abrangência será uma árvore de abrangência mínima. Como você observou, você pode usar um BFS (ou mesmo DFS) para encontrar uma árvore linear no tempo no número de arestas.

Juho
fonte

Mas, e o exemplo contraditório que o colapsar forneceu?

TheNotMe 28/03/2014

@TheNotMe O BFS geralmente é chamado de algoritmo linear, pois é . No entanto, no pior dos casos (como no exemplo do colapsar), para que o BFS possa ser considerado como . No entanto, os algoritmos de Prim e Kruskal para MSTs também contêmna complexidade do tempo e, portanto, também não são "lineares" no sentido do colapso. Qual algoritmo você está usando como referência? Sua complexidade de tempo inclui? Nesse caso, o BFS não é pior que isso.

O (| V | + | E |)

$O(|V| + |E|)$

| E | = | V |^{2}

$|E| = |V|^2$

O (| V |^{2})

$O(|V|^2)$

| E |

$|E|$

| E |

$|E|$

Patrick87

Se todos os custos de borda forem iguais, qualquer árvore de abrangência também será uma árvore de abrangência mínima. Nesse caso, qualquer algoritmo que resolva a REACHABILITY também resolve o MST.

Let S = {v0} be a set of nodes initially containing v0
Mark v0
Parent[v0] = -1
While S is not empty
  Remove a vertex v from S
  For all edges (v,u)
    If u is unmarked
      Mark it and add it to S
      Parent[u] = v

Você pode recuperar a árvore da Parentrelação. Se S.Removee S.Addlevar tempo constante, o algoritmo tomará onde é o número de vértices e arestas. $\cal O(v+e)=\cal O(v^2)$ $v,e$

saadtaame
fonte

-3

Se todas as arestas tiverem o mesmo peso, podemos usar:

-BFS -DFS - Algoritmo de Dijkstra - algoritmo de -Prim

Mas você não pode usar

algoritmo de -kruskal

Nandkishor Nangre
fonte

Isso não é verdade. Você pode usar o algoritmo de Kruskal.

Mal

Como é possível, porque vai acabar dando todas as arestas quando começamos com o menor peso primeiro !!

Nandkishor Nangre

Ele escolherá um, qualquer um, também pode escolher aleatoriamente.

malvado

Sim, eu tenho o seu ponto !! mas é aplicável em algo kruskal .... porque eu nunca vi qualquer código de kruskal afirmando o fenômeno acima

Nandkishor Nangre

A pergunta feita se podemos usar "BFS" e sua resposta apenas diz "sim" sem dizer mais nada sobre o porquê. Não estamos procurando respostas que apenas afirmem que a resposta é sim. Estamos buscando respostas que forneçam explicações, justificativas, justificativas ou provas de suas conclusões. Convido você a editar sua resposta para explicar o porquê. Além disso, a pergunta não perguntou "como podemos fazê-lo", perguntou se o BFS funcionava, portanto, fornecer outros algoritmos não responde à pergunta que foi feita.