Algoritmos de gráficos y estructuras de datos explicados con ejemplos de Java y C ++

¿Qué es un algoritmo gráfico?

Los algoritmos de gráficos son un conjunto de instrucciones que atraviesan (visitan los nodos de un) gráfico.

Algunos algoritmos se utilizan para encontrar un nodo específico o la ruta entre dos nodos dados.

Por qué son importantes los algoritmos de gráficos

Los gráficos son estructuras de datos muy útiles que pueden servir para modelar varios problemas. Estos algoritmos tienen aplicaciones directas en sitios de redes sociales, modelado de máquinas de estado y muchos más.

Algunos algoritmos de gráficos comunes

Algunos de los algoritmos de gráficos más comunes son:

  • Primera búsqueda de amplitud (BFS)
  • Primera búsqueda en profundidad (DFS)
  • Dijkstra
  • Algoritmo Floyd-Warshall

Algoritmo de Bellman Ford

El algoritmo de Bellman Ford es un algoritmo de búsqueda de ruta más corta para gráficos que pueden tener pesos negativos. El algoritmo de Bellman ford también es excelente para detectar ciclos de peso negativos a medida que el algoritmo converge a una solución óptima en pasos O (V * E). Si el resultado no es óptimo, entonces el gráfico contiene un ciclo de peso negativo.

Aquí hay una implementación en Python:

infinity = 1e10 def bellman_ford(graph, start, end): num_vertices = graph.get_num_vertices() edges = graph.get_edges() distance = [infinity for vertex in range(num_vertices)] previous = [None for vertex in range(num_vertices)] distance[start] = 0 for i range(end+1): for (u, v) in edges: if distance[v] > distance[u] + graph.get_weight(u, v): distance[v] = distance[u] + graph.get_weight(u, v) previous[v] = u for (u,v) in edges: if distance[v] > distance[u] + graph.get_weight(u, v): raise NegativeWeightCycleError() return distance, previous # 'distance' is the distance from start to that node in the shortest path, useful for printing the shortest distance. # Previous is an array that tells the node that comes previous to current, useful for printing out the path. 

Primera búsqueda en profundidad (DFS)

Depth First Search es uno de los algoritmos de gráficos más simples. Atraviesa el gráfico comprobando primero el nodo actual y luego moviéndose a uno de sus sucesores para repetir el proceso. Si el nodo actual no tiene un sucesor para verificar, volvemos a su predecesor y el proceso continúa (moviéndonos a otro sucesor). Si se encuentra la solución, la búsqueda se detiene.

Visualización

Implementación (C ++ 14)

#include  #include  #include  #include  using namespace std; class Graph{ int v; // number of vertices // pointer to a vector containing adjacency lists vector  *adj; public: Graph(int v); // Constructor // function to add an edge to graph void add_edge(int v, int w); // prints dfs traversal from a given source `s` void dfs(); void dfs_util(int s, vector  &visited); }; Graph::Graph(int v){ this -> v = v; adj = new vector [v]; } void Graph::add_edge(int u, int v){ adj[u].push_back(v); // add v to u’s list adj[v].push_back(v); // add u to v's list (remove this statement if the graph is directed!) } void Graph::dfs(){ // visited vector - to keep track of nodes visited during DFS vector  visited(v, false); // marking all nodes/vertices as not visited for(int i = 0; i < v; i++) if(!visited[i]) dfs_util(i, visited); } // notice the usage of call-by-reference here! void Graph::dfs_util(int s, vector  &visited){ // mark the current node/vertex as visited visited[s] = true; // output it to the standard output (screen) cout << s << " "; // traverse its adjacency list and recursively call dfs_util for all of its neighbours! // (only if the neighbour has not been visited yet!) for(vector  :: iterator itr = adj[s].begin(); itr != adj[s].end(); itr++) if(!visited[*itr]) dfs_util(*itr, visited); } int main() { // create a graph using the Graph class we defined above Graph g(4); g.add_edge(0, 1); g.add_edge(0, 2); g.add_edge(1, 2); g.add_edge(2, 0); g.add_edge(2, 3); g.add_edge(3, 3); cout << "Following is the Depth First Traversal of the provided graph" << "(starting from vertex 0): "; g.dfs(); // output would be: 0 1 2 3 return 0; } 

Evaluación

Complejidad espacial: O (n)

En el peor de los casos, complejidad temporal: O (n) Profundidad Primero La búsqueda se completa en un conjunto finito de nodos. Funciono mejor en árboles poco profundos.

Implementación de DFS en C ++

#include #include #include using namespace std; struct Graph{ int v; bool **adj; public: Graph(int vcount); void addEdge(int u,int v); void deleteEdge(int u,int v); vector DFS(int s); void DFSUtil(int s,vector &dfs,vector &visited); }; Graph::Graph(int vcount){ this->v = vcount; this->adj=new bool*[vcount]; for(int i=0;iadj[i]=new bool[vcount]; for(int i=0;iadj[w][u]=true; } void Graph::deleteEdge(int u,int w){ this->adj[u][w]=false; this->adj[w][u]=false; } void Graph::DFSUtil(int s, vector &dfs, vector &visited){ visited[s]=true; dfs.push_back(s); for(int i=0;iv;i++){ if(this->adj[s][i]==true && visited[i]==false) DFSUtil(i,dfs,visited); } } vector Graph::DFS(int s){ vector visited(this->v); vector dfs; DFSUtil(s,dfs,visited); return dfs; } 

Algoritmo Floyd Warshall

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

Evaluación

Complejidad espacial: O (V ^ 2)

Complejidad temporal en el peor de los casos: O (V ^ 3)

Implementación de Python

# A large value as infinity inf = 1e10 def floyd_warshall(weights): V = len(weights) distance_matrix = weights for k in range(V): next_distance_matrix = [list(row) for row in distance_matrix] # make a copy of distance matrix for i in range(V): for j in range(V): # Choose if the k vertex can work as a path with shorter distance next_distance_matrix[i][j] = min(distance_matrix[i][j], distance_matrix[i][k] + distance_matrix[k][j]) distance_matrix = next_distance_matrix # update return distance_matrix # A graph represented as Adjacency matrix graph = [ [0, inf, inf, -3], [inf, 0, inf, 8], [inf, 4, 0, -2], [5, inf, 3, 0] ] print(floyd_warshall(graph)) 

Primera búsqueda de amplitud (BFS)

Breadth First Search es uno de los algoritmos de gráficos más simples. Atraviesa el gráfico comprobando primero el nodo actual y luego expandiéndolo añadiendo sus sucesores al siguiente nivel. El proceso se repite para todos los nodos del nivel actual antes de pasar al siguiente nivel. Si se encuentra la solución, la búsqueda se detiene.

Visualización

Evaluación

Complejidad espacial: O (n)

Complejidad temporal en el peor de los casos: O (n)

La búsqueda primero en amplitud se completa en un conjunto finito de nodos y es óptima si el costo de pasar de un nodo a otro es constante.

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

// Program to print BFS traversal from a given // source vertex. BFS(int s) traverses vertices // reachable from s. #include #include  using namespace std; // This class represents a directed graph using // adjacency list representation class Graph { int V; // No. of vertices // Pointer to an array containing adjacency // lists list *adj; public: Graph(int V); // Constructor // function to add an edge to graph void addEdge(int v, int w); // prints BFS traversal from a given source s void BFS(int s); }; Graph::Graph(int V) { this->V = V; adj = new list[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Add w to v’s list. } void Graph::BFS(int s) { // Mark all the vertices as not visited bool *visited = new bool[V]; for(int i = 0; i < V; i++) visited[i] = false; // Create a queue for BFS list queue; // Mark the current node as visited and enqueue it visited[s] = true; queue.push_back(s); // 'i' will be used to get all adjacent // vertices of a vertex list::iterator i; while(!queue.empty()) { // Dequeue a vertex from queue and print it s = queue.front(); cout << s << " "; queue.pop_front(); // Get all adjacent vertices of the dequeued // vertex s. If a adjacent has not been visited, // then mark it visited and enqueue it for (i = adj[s].begin(); i != adj[s].end(); ++i) { if (!visited[*i]) { visited[*i] = true; queue.push_back(*i); } } } } // Driver program to test methods of graph class int main() { // Create a graph given in the above diagram Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); cout << "Following is Breadth First Traversal " << "(starting from vertex 2) \n"; g.BFS(2); return 0; } 

Algoritmo de Dijkstra

El algoritmo de Dijkstra es un algoritmo gráfico presentado por EW Dijkstra. Encuentra la ruta más corta de una sola fuente en un gráfico con bordes no negativos (¿por qué?)

We create 2 arrays : visited and distance, which record whether a vertex is visited and what is the minimum distance from the source vertex respectively. Initially visited array is assigned as false and distance as infinite.

We start from the source vertex. Let the current vertex be u and its adjacent vertices be v. Now for every v which is adjacent to u, the distance is updated if it has not been visited before and the distance from u is less than its current distance. Then we select the next vertex with the least distance and which has not been visited.

Priority Queue is often used to meet this last requirement in the least amount of time. Below is an implementation of the same idea using priority queue in Java.

import java.util.*; public class Dijkstra { class Graph { LinkedList adj[]; int n; // Number of vertices. Graph(int n) { this.n = n; adj = new LinkedList[n]; for(int i = 0;i { public int compare(Pair a, Pair b) { return a.second - b.second; } } // Calculates shortest path to each vertex from source and returns the distance public int[] dijkstra(Graph g, int src) { int distance[] = new int[g.n]; // shortest distance of each vertex from src boolean visited[] = new boolean[g.n]; // vertex is visited or not Arrays.fill(distance, Integer.MAX_VALUE); Arrays.fill(visited, false); PriorityQueue pq = new PriorityQueue(100, new PairComparator()); pq.add(new Pair(src, 0)); distance[src] = 0; while(!pq.isEmpty()) { Pair x = pq.remove(); // Extract vertex with shortest distance from src int u = x.first; visited[u] = true; Iterator iter = g.adj[u].listIterator(); // Iterate over neighbours of u and update their distances while(iter.hasNext()) { Pair y = iter.next(); int v = y.first; int weight = y.second; // Check if vertex v is not visited // If new path through u offers less cost then update distance array and add to pq if(!visited[v] && distance[u]+weight

Ford Fulkerson algorithm

Ford Fulkerson's algorithm solves the maximum flow graph problem. It finds the best organisation of flow through the edges of graphs such that you get maximum flow out on the other end. The source has a specific rate of input and each edge has a weight associated with it which is the maximum substance that can be passed through that edge.

Ford Fulkerson algorithm is also called Edmund-Karp algorithm as the algorithm was provided in complete specification by Jack Edmonds and Richard Karp.

It works by creating augmenting paths i.e. paths from source to sink that have a non-zero flow. We pass the flow through the paths and we update the limits. This can lead to situation where we have no more moves left. That's where the 'undo' ability of this algorithm plays a big role. In case of being stuck, we decrease the flow and open up the edge to pass our current substance.

Steps

  1. Set zero flow for all edges.
  2. While there is a path from source to sink do,
  3. Find the minimum weight on the path, let it be  limit .
  4. For all edges (u, v) on the path do,

    1. Add  limit  to flow from u to v. (For current move)

    2. Subtract  limit  from flow from v to u. (For undo in later move)

Evaluation

Time Complexity: O(V*E^2)

Python implementation

# Large number as infinity inf = 1e10 def maximum_flow(graph, source, sink): max_flow = 0 parent = bfs(graph, source, sink) while path: limit = inf v = sink while v != source: u = parent[s] path_flow = min(limit, graph[u][v]) v = parent[v] max_flow += path_flow v = sink while v != source: u = parent[v] graph[u][v] -= path_flow graph[v][u] += path_flow v = parent[v] path = bfs(graph, source, sink) return max_flow 

Original text