Explication des algorithmes de graphes et des structures de données avec des exemples Java et C ++

Qu'est-ce qu'un algorithme graphique?

Les algorithmes de graphes sont un ensemble d'instructions qui traversent (visitent les nœuds d'un) graphe.

Certains algorithmes sont utilisés pour trouver un nœud spécifique ou le chemin entre deux nœuds donnés.

Pourquoi les algorithmes graphiques sont importants

Les graphiques sont des structures de données très utiles qui peuvent être pour modéliser divers problèmes. Ces algorithmes ont des applications directes sur les sites de réseautage social, la modélisation State Machine et bien d'autres.

Quelques algorithmes de graphes courants

Certains des algorithmes graphiques les plus courants sont:

  • Première recherche en largeur (BFS)
  • Première recherche en profondeur (DFS)
  • Dijkstra
  • Algorithme Floyd-Warshall

Algorithme de Bellman Ford

L'algorithme de Bellman Ford est un algorithme de recherche de chemin le plus court pour les graphiques qui peuvent avoir des poids négatifs. L'algorithme de Bellman ford est également idéal pour détecter les cycles de poids négatifs lorsque l'algorithme converge vers une solution optimale par étapes O (V * E). Si le résultat n'est pas optimal, alors le graphique contient un cycle de poids négatif.

Voici une implémentation 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. 

Première recherche en profondeur (DFS)

Depth First Search est l'un des algorithmes graphiques les plus simples. Il parcourt le graphe en vérifiant d'abord le nœud actuel, puis en se déplaçant vers l'un de ses successeurs pour répéter le processus. Si le nœud actuel n'a pas de successeur à vérifier, nous revenons à son prédécesseur et le processus se poursuit (en passant à un autre successeur). Si la solution est trouvée, la recherche s'arrête.

Visualisation

Implémentation (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; } 

Évaluation

Complexité spatiale: O (n)

Complexité temporelle dans le pire des cas: O (n) La première recherche en profondeur est terminée sur un ensemble fini de nœuds. Je travaille mieux sur les arbres peu profonds.

Implémentation 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; } 

Algorithme Floyd Warshall

L'algorithme Floyd Warshall est un excellent algorithme pour trouver la distance la plus courte entre tous les sommets d'un graphe. Il a un algorithme très concis et une complexité en temps O (V ^ 3) (où V est le nombre de sommets). Il peut être utilisé avec des poids négatifs, bien que les cycles de poids négatifs ne doivent pas être présents dans le graphique.

Évaluation

Complexité spatiale: O (V ^ 2)

Complexité temporelle pire: O (V ^ 3)

Implémentation 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)) 

Première recherche en largeur (BFS)

Breadth First Search est l'un des algorithmes graphiques les plus simples. Il parcourt le graphe en vérifiant d'abord le nœud actuel, puis en le développant en ajoutant ses successeurs au niveau suivant. Le processus est répété pour tous les nœuds du niveau actuel avant de passer au niveau suivant. Si la solution est trouvée, la recherche s'arrête.

Visualisation

Évaluation

Complexité spatiale: O (n)

Complexité temporelle pire: O (n)

La première recherche en largeur est terminée sur un ensemble fini de nœuds et optimale si le coût de déplacement d'un nœud à un autre est constant.

Code C ++ pour l'implémentation 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; } 

Algorithme de Dijkstra

L'algorithme de Dijkstra est un algorithme graphique présenté par EW Dijkstra. Il trouve le chemin le plus court de source unique dans un graphique avec des arêtes non négatives. (Pourquoi?)

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