Grafo conexo
En teoría de grafos, un grafo se dice conexo si, para cualquier par de vértices a y b en G, existe al menos una trayectoria (una sucesión de vértices adyacentes que no repita vértices) de a a b.
Conceptos relacionados
Un grafo dirigido tal que para cualesquiera dos vértices a y b existe un camino dirigido de ida y de regreso se dice grafo fuertemente conexo.
Un conjunto de corte de vértices U en un grafo G, es un conjunto de vértices de G, tal que G-U no es conexo o trivial. Similarmente, un conjunto de corte de aristas F es un conjunto de aristas tal que G-F no es conexo.
Solución computacional
El problema computacional de determinar si un grafo es conexo puede ser resuelto con algunos algoritmos como el MFMC (max-flow, min-cut).
Algoritmo
Ejemplo de algoritmo iterativo implementado en C++ para determinar si un grafo es conexo utilizando búsqueda en profundidad, donde _n es la cantidad de vértices y _graph denota la matriz de adyacencia.
bool Graph::is_connected()
{
if (_n <= 1)
return true;
vector<bool> visit(_n);
vector<bool>::iterator iter;
for(iter = visit.begin(); iter != visit.end(); iter++)
*iter = false;
set<int> forvisit;
set<int>::iterator current;
forvisit.insert(0);
while (!forvisit.empty())
{
current = forvisit.begin();
if (!visit[*current])
{
for (int i = 0; i < _n; i++)
{
if (_graph[*current][i] == 1 && !visit[i])
forvisit.insert(i);
}
}
visit[*current] = true;
forvisit.erase(current);
}
bool result;
for (iter = visit.begin(); iter != visit.end(); iter++)
result = result && *iter;
return result;
}