Herramientas de usuario
algoritmos-oia:grafos:componentes-conexas
Diferencias
Muestra las diferencias entre dos versiones de la página.
|
algoritmos-oia:grafos:componentes-conexas [2020/05/12 22:54] ariel creado |
algoritmos-oia:grafos:componentes-conexas [2020/05/12 23:06] (actual) ariel |
||
|---|---|---|---|
| Línea 15: | Línea 15: | ||
| <code cpp> | <code cpp> | ||
| - | void dfs(int nodo, vector<vector<int>> grafo, vector<int> componente, int componenteActual) { | + | void dfs(int nodo, vector<vector<int>>& grafo, vector<int>& componente, int componenteActual) { |
| // agregamos el nodo a la componente | // agregamos el nodo a la componente | ||
| componente[nodo] = componenteActual; | componente[nodo] = componenteActual; | ||
| Línea 49: | Línea 49: | ||
| </code> | </code> | ||
| + | |||
| + | ==== Análisis de complejidad ==== | ||
| + | |||
| + | Es claro que todo salvo el primer for es $O(n)$ donde $n$ es la cantidad de nodos de $G$. | ||
| + | Para el for que hace los DFs. El DFS lanzado desde $i$ recorre todos los nodos de la componente de $i$ y todas sus aristas y nada más que eso. Luego es $O(n_i + m_i)$ donde $n_i$ y $m_i$ son la cantidad de nodos y aristas respectivamente de la componente de $i$. Luego el costo total del for es $O(n)$ más la suma de $O(n_i + m_i)$ por cada DFS que lanzamos. Pero lanzamos un DFS por componente, luego la suma de los $n_i$ es la suma de las cantidades de nodos de todas las componentes, que es $n$. Y, análogamente la suma de los $m_i$ es la suma de la cantidades de aristas de todas las componentes, que es $m$. Luego el for tiene complejidad $O(n+m)$ y como es lo más costoso del algoritmo, el algoritmo queda $O(n+m)$. | ||
| + | |||
| + | ==== Grafos conexos ==== | ||
| + | Un grafo $G$ es conexo si de cualquier nodo se puede llegar a cualquier otro. Esto es equivalente a decir que hay una sola componente conexa. Luego, podemos chequear si un grafo es conexo usando el algoritmo anterior y chequeando que quede una sola componente. Se puede hace algo mas simple para este caso que es simplemente lanzar un sólo DFS desde cualquier nodo $v$, por ejemplo el nodo $0$, y verificar que visite a todos los nodos del grafo. | ||
algoritmos-oia/grafos/componentes-conexas.1589324078.txt.gz · Última modificación: 2020/05/12 22:54 por ariel
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
