Original article: Graph Algorithms and Data Structures Explained with Java and C++ Examples

¿Qué es un Algoritmo de Grafos?

Los algoritmos de grafos son un conjunto de instrucciones que recorren (visitan los nodos de) un grafo.

Algunos algoritmos son usados para hallar un nodo específico o el camino entre dos nodos dados.

¿Por qué son Importantes los Algoritmos de Grafos?

Los grafos son estructuras de datos muy útiles que se usan para modelar varios problemas. Estos algoritmos tienen aplicaciones directas en sitios de redes sociales, modelado de máquinas de estado y más.

Algunos Algoritmos de Grafos Comunes

Algunos de los algoritmos de grafos más comunes son:

  • Búsqueda en Amplitud o Anchura (Breadth First Search, BFS)
  • Búsqueda en Profundidad (Depth First Search, DFS)
  • Dijkstra
  • Algoritmo de Floyd-Warshall

Algoritmo de Bellman Ford

El algoritmo de Bellman Ford es un algoritmo de búsqueda del camino más corto para grafos que puede tener pesos negativos. El algoritmo de Bellman Ford es también ideal para detectar ciclos de pesos negativos, ya que el algoritmo converge hacia una solución óptima en O(V*E) pasos. Si la resultante no es óptima, entonces el grafo contiene un ciclo de pesos negativos.

Aquí está una implementación en Python:

infinito = 1e10

def bellman_ford(grafo, inicio, fin):
    num_vertices = grafo.get_num_vertices()
    aristas = grafo.get_edges()

    distancia = [infinito para vértice en range(num_vertices)]
    previo = [ninguno para vértice en range(num_vertices)]

    distancia[inicio] = 0
    for i range(fin+1):
        for (u, v) in aristas:
            if distancia[v] > distancia[u] + grafo.get_weight(u, v):
                distancia[v] = distancia[u] + grafo.get_weight(u, v)
                previo[v] = u

    for (u,v) in aristas:
        if distancia[v] > distancia[u] + grafo.get_weight(u, v):
            raise ErrorCicloPesoNegativo()
    return distancia, previo
# 'distancia' es la distancia desde el inicio hasta ese nodo en el camino más corto, útil para imprimir la distancia más corta.
# Previo es un arreglo que muestra el nodo que es anterior al actual, útil para imprimir el camino.

Búsqueda en Profundidad (Depth First Search, DFS)

La Búsqueda en Profundidad es uno de los algoritmos de grafos más sencillos. Recorre el grafo revisando primero el nodo actual y moviéndose después a uno de sus sucesores para repetir el proceso. Si el nodo actual no tiene sucesor a revisar, regresamos a su predecesor y el proceso continúa (moviéndose a otro sucesor). Si la solución es encontrada, la búsqueda termina.

Visualización

Implementación (C++14)

#include <iostream> 
#include <vector> 
#include <queue>  
#include <algorithm>
using namespace std; 
 
class Grafo{ 
   int v;    // número de vértices 
 
   // puntero a un vector que contiene listas de adyacencia
   vector < int > *adj;
public: 
   Grafo(int v);  // Constructor 
 
   // función para añadir una arista al grafo
   void agregar_arista(int v, int w);  
 
   // imprime el recorrido dfs a partir de una fuente `s` dada
   void dfs();
   void dfs_util(int s, vector < bool> &visitado);   
}; 
 
Grafo::Grafo(int v){ 
   this -> v = v; 
   adj = new vector < int >[v]; 
} 
 
void Grafo::agregar_arista(int u, int v){ 
   adj[u].push_back(v); // agregar v a la lista de u
   adj[v].push_back(v); // agregar u a la lista de v (¡elimina esta declaración si el grafo es dirigido!)
} 
void Grafo::dfs(){
   // vector visitado - para llevar registro de los nodos visitados durante la búsqueda en profundidad)
   vector < bool > visitado(v, false);  // marcar todos los nodos/vértices como no visitados
   for(int i = 0; i < v; i++)
       if(!visitado[i])
           dfs_util(i, visitado);
} 
// ¡observa el uso de la llamada por referencia aquí!
void Grafo::dfs_util(int s, vector < bool > &visitado){ 
   // marcar el nodo/vértice actual como visitado
   visitado[s] = true;
    // enviarlo a la salida estándar(pantalla)
   cout << s << " ";
   
   // ¡recorrer su lista de adyacencia y llamar recursivamente a dfs_util para todos sus vecinos! 
   // (¡solo si el vecino aún no ha sido visitado!)
   for(vector < int > :: iterator itr = adj[s].begin(); itr != adj[s].end(); itr++)
       if(!visitado[*itr])
           dfs_util(*itr, visitado); 
} 
 
int main() 
{ 
   // crear un grafo usando la clase Grafo que definimos anteriormente
   Grafo g(4); 
   g.agregar_arista(0, 1); 
   g.agregar_arista(0, 2); 
   g.agregar_arista(1, 2); 
   g.agregar_arista(2, 0); 
   g.agregar_arista(2, 3); 
   g.agregar_arista(3, 3); 
 
   cout << "A continuación el recorrido de la búsqueda en profundidad del grafo proporcionado"
        << "(a partir del vértice 0): "; 
   g.dfs(); 
   // la salida sería: 0 1 2 3
   return 0; 
}

Evaluación

Complejidad del Espacio: O(n)

Complejidad del Tiempo en el Peor de los Casos: O(n) La Búsqueda en Profundidad es completa en un conjunto finito de nodos. Funciona mejor en árboles poco profundos.

Implementación de DFS en C++

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

struct Grafo{
	int v;
	bool **adj;
	public:
		Grafo(int conteov);
		void agregarArista(int u,int v);
		void borrarArista(int u,int v);
		vector<int> DFS(int s);
		void DFSUtil(int s,vector<int> &dfs,vector<bool> &visitado);
};
Grafo::Grafo(int conteov){
	this->v = conteov;
	this->adj=new bool*[conteov];
	for(int i=0;i<conteov;i++)
		this->adj[i]=new bool[conteov];
	for(int i=0;i<conteov;i++)
		for(int j=0;j<conteov;j++)
			adj[i][j]=false;
}

void Grafo::agregarArista(int u,int w){
	this->adj[u][w]=true;
	this->adj[w][u]=true;
}

void Grafo::borrarArista(int u,int w){
	this->adj[u][w]=false;
	this->adj[w][u]=false;
}

void Grafo::DFSUtil(int s, vector<int> &dfs, vector<bool> &visitado){
	visitado[s]=true;
	dfs.push_back(s);
	for(int i=0;i<this->v;i++){
		if(this->adj[s][i]==true && visitado[i]==false)
			DFSUtil(i,dfs,visitado);
	}
}

vector<int> Grafo::DFS(int s){
	vector<bool> visitado(this->v);
	vector<int> dfs;
	DFSUtil(s,dfs,visitado);
	return dfs;
}

Algoritmo de Floyd Warshall

El algoritmo de Floyd Warshall es un gran algoritmo para encontrar la distancia más corta entre todos los vértices del grafo. Tiene un algoritmo muy conciso y complejidad del tiempo O(V^3) (donde V es el número de vértices). Puede ser usado con pesos negativos, aunque los ciclos de pesos negativos no deben estar presentes en el grafo.

Evaluación

Complejidad del Espacio: O(V^2)

Complejidad del Tiempo en el Peor de los Casos: O(V^3)

Implementación en Python

# Un valor grande como infinito
inf = 1e10 

def floyd_warshall(pesos):
    V = len(pesos)
    matriz_distancia = pesos
    for k in range(V):
        siguiente_matriz_distancia = [list(row) for row in matriz_distancia] # hacer una copia de matriz de distancia
        for i in range(V):
            for j in range(V):
                # Elegir si el vértice k puede funcionar como un camino con menor distancia
                siguiente_matriz_distancia[i][j] = min(matriz_distancia[i][j], matriz_distancia[i][k] + matriz_distancia[k][j])
        matriz_distancia = siguiente_matriz_distancia # actualizar
    return matriz_distancia

# Un grafo representado como matriz de adyacencia
grafo = [
    [0, inf, inf, -3],
    [inf, 0, inf, 8],
    [inf, 4, 0, -2],
    [5, inf, 3, 0]
]

print(floyd_warshall(grafo))


Búsqueda en Amplitud o Anchura (Breadth First Search, BFS)

Búsqueda en Amplitud o Anchura es uno de los algoritmos de grafos más sencillo. Recorre el grafo al primero comprobar el nodo actual y luego expandirlo al agregar sus sucesores al siguiente nivel. El proceso se repite para todos los nodos del nivel actual  antes de moverse al siguiente. Si se encuentra la solución, la búsqueda termina.

Visualización

Animated_BFS

Evaluación

Complejidad del Espacio: O(n)

Complejidad del Tiempo en el Peor de los Casos: O(n)

La Búsqueda en Amplitud o Anchura es completa en un conjunto finito de nodos y es óptima si el costo de moverse de un nodo a otro es constante.

Código C++ para la implementación de BFS

// Programa para imprimir el recorrido BFS desde un 
// vértice origen dado. BFS(int s) recorre los vértices  
// alcanzables desde s. 
#include<iostream> 
#include <list> 
  
using namespace std; 
  
// Esta clase representa un grafo dirigido
// utilizando la representación de listas de adyacencias 
class Grafo 
{ 
    int V;    // No. de vértices 
  
    // Puntero a un arreglo que contiene listas de adyacencia
    list<int> *adj;    
public: 
    Grafo(int V);  // Constructor 
  
    // función para agregar una arista al grafo
    void agregarArista(int v, int w);  
  
    // imprime el recorrido de BFS desde una fuente s dada
    void BFS(int s);   
}; 
  
Grafo::Grafo(int V) 
{ 
    this->V = V; 
    adj = new list<int>[V]; 
} 
  
void Grafo::agregarArista(int v, int w) 
{ 
    adj[v].push_back(w); // Agregar w a la lista de v.
} 
  
void Grafo::BFS(int s) 
{ 
    // Marcar todos los vértices como no visitados
    bool *visitado = new bool[V]; 
    for(int i = 0; i < V; i++) 
        visitado[i] = false; 
  
    // Crear una cola para BFS 
    list<int> cola; 
  
    // Marcar el nodo actual como visitado y ponerlo en cola
    visitado[s] = true; 
    cola.push_back(s); 
  
    // 'i' será usado para obtener todos los vértices
    // adyacentes de un vértice 
    list<int>::iterator i; 
  
    while(!cola.empty()) 
    { 
        // Sacar de la cola un vértice e imprimirlo
        s = cola.front(); 
        cout << s << " "; 
        cola.pop_front(); 
  
        // Obtener todos los vértices adyacentes del
        // vértice s sacado de la cola. Si un adyacente
        // no ha sido visitado, entonces marcarlo como 
        // visitado y ponerlo en la cola
        for (i = adj[s].begin(); i != adj[s].end(); ++i) 
        { 
            if (!visitado[*i]) 
            { 
                visitado[*i] = true; 
                cola.push_back(*i); 
            } 
        } 
    } 
} 
  
// Programa controlador para probar métodos de la clase grafo
int main() 
{ 
    // Crear un grafo como el del diagrama anterior
    Grafo g(4); 
    g.agregarArista(0, 1); 
    g.agregarArista(0, 2); 
    g.agregarArista(1, 2); 
    g.agregarArista(2, 0); 
    g.agregarArista(2, 3); 
    g.agregarArista(3, 3); 
  
    cout << "A continuación se muestra el recorrido en amplitud o anchura "
         << "(empezando desde el vértice 2) \n"; 
    g.BFS(2); 
  
    return 0; 
}

Algoritmo de Dijkstra

El Algoritmo de Dijkstra es un algoritmo de grafo presentado por E. W. Dijkstra. Encuentra el camino más corto de origen único en un grafo con aristas no negativas. (¿Por qué?)

Creamos dos arreglos: visitado y distancia, que registran si un vértice es visitado y cuál es la mínima distancia desde el vértice origen, respectivamente. Inicialmente, el arreglo visitado se asigna como falso y distancia como infinito.

Partimos del vértice origen. Dejemos que el vértice actual sea u y sus vértices adyacentes sean v. Ahora, por cada v que es adyacente a u, la distancia se actualiza si no ha sido visitado antes y la distancia desde u es menor que su distancia actual. Luego seleccionamos el siguiente vértice con la menor distancia y que no haya sido visitado.

La Cola de Prioridad se usa a menudo para cumplir este último requerimiento en el menor tiempo posible. Abajo se ve una implementación de la misma idea usando la cola de prioridad en Java.

import java.util.*;
public class Dijkstra {
    class Grafo {
	LinkedList<Pair<Integer>> adj[];
	int n; // Número de vertices.
	Grafo(int n) {
	    this.n = n;
	    adj = new LinkedList[n];
	    for(int i = 0;i<n;i++) adj[i] = new LinkedList<>();
	}
	// agregar una arista dirigida entre los vértices a y b con el costo como peso
	public void agregarAristaDirigida(int a, int b, int costo) {
	    adj[a].add(new Pair(b, costo));
	}
	public void agregarAristaNoDirigida(int a, int b, int costo) {
	    agregarAristaDirigida(a, b, costo);
	    agregarAristaDirigida(b, a, costo);
	}
    }
    class Pair<E> {
	E first;
	E second;
	Pair(E f, E s) {
	    first = f;
	    second = s;
	}
    }

    // Comparador para ordenar Pares en la Cola de Prioridad
    class ComparadorPar implements Comparator<Pair<Integer>> {
	public int comparar(Pair<Integer> a, Pair<Integer> b) {
	    return a.second - b.second;
	}
    }

    // Calcular el camino más corto para cada vértice del origen y devuelve la distancia
    public int[] dijkstra(Grafo g, int src) {
	int distancia[] = new int[g.n]; // la distancia más corta de cada vértice desde src
	boolean visitado[] = new boolean[g.n]; // el vértice es visitado o no
	Arrays.fill(distancia, Integer.MAX_VALUE);
	Arrays.fill(visitado, false);
	PriorityQueue<Pair<Integer>> pq = new PriorityQueue<>(100, new ComparadorPar());
        pq.add(new Pair<Integer>(src, 0));
	distancia[src] = 0;
	while(!pq.isEmpty()) {
	    Pair<Integer> x = pq.remove(); // Extraer el vértice con la distancia más corta desde src
	    int u = x.first;
	    visitado[u] = true;
	    Iterator<Pair<Integer>> iter = g.adj[u].listIterator();
	    // Iterar sobre los vecinos de u y actualizar sus distancias
	    while(iter.hasNext()) {
		Pair<Integer> y = iter.next();
		int v = y.first;
		int peso = y.second;
		// Comprobar si el vértice v no es visitado
		// Si el nuevo camino a través de u ofrece menos costo, entonces actualizar el arreglo de distancia y agregarlo a cp
		if(!visitado[v] && distancia[u]+peso<distancia[v]) {
		    distancia[v] = distancia[u]+peso;
		    pq.add(new Pair(v, distancia[v]));
		}
	    }
	}
	return distancia;
    }

    public static void main(String args[]) {
	Dijkstra d = new Dijkstra();
	Dijkstra.Grafo g = d.new Grafo(4);
	g.agregarAristaNoDirigida(0, 1, 2);
	g.agregarAristaNoDirigida(1, 2, 1);
	g.agregarAristaNoDirigida(0, 3, 6);
	g.agregarAristaNoDirigida(2, 3, 1);
	g.agregarAristaNoDirigida(1, 3, 3);

	int dist[] = d.dijkstra(g, 0);
	System.out.println(Arrays.toString(dist));
    }
}

Algoritmo de Ford  Fulkerson

El algoritmo de Ford Fulkerson resuelve el problema de grafo de flujo máximo. Encuentra la mejor organización del flujo mediante las aristas de grafos, de tal modo que obtienes el flujo máximo de salida en el otro extremo. La fuente tiene una tasa específica de entrada y cada arista tiene un peso asociado que es la sustancia máxima que puede pasar a través de esa arista.

Al algoritmo Ford Fulkerson también se le conoce como algoritmo Edmund-Karp, ya que fue provisto en especificación completa por Jack Edmonds y Richard Karp.

Trabaja creando caminos de aumento, es decir, caminos desde el origen hasta el sumidero que tienen flujo no cero. Pasamos el flujo a través de los caminos y actualizamos los límites. Esto puede llevar a una situación donde no tenemos más movimientos. Es aquí donde la habilidad 'deshacer' de este algoritmo juega un papel importante. En caso de quedarse atorado, disminuimos el flujo y abrimos la arista para pasar nuestra sustancia actual.

Pasos

  1. Establecer flujo cero para todas las aristas.
  2. Mientras haya un camino del origen al hundimiento hacer,
  3. Hallar el peso mínimo en el camino, que sea el límite.
  4. Para todas las aristas (u, v) en el camino hacer,
    1. Agregar límite al flujo de u a v. (Para el movimiento actual)
    2. Restar límite  al flujo de v a u. (Para deshacer en un movimiento posterior)

Evaluación

Complejidad del tiempo: O(V*E^2)

Implementación en Python

# Número grande como infinito
inf = 1e10

def flujo_maximo(grafo, fuente, destino):
  flujo_maximo = 0
  padre = bfs(grafo, fuente, destino)
  while camino:
    limite = inf
    v = destino
    while v != fuente:
        u = padre[s]
        flujo_camino = min(limite, grafo[u][v])
        v = padre[v]
    flujo_maximo += flujo_camino

    v = destino
    while v != fuente:
        u = padre[v]
        grafo[u][v] -= flujo_camino
        grafo[v][u] += flujo_camino
        v = padre[v]

    camino = bfs(grafo, fuente, destino)
  return flujo_maximo