Αλγόριθμοι γραφημάτων και δομές δεδομένων που εξηγούνται με παραδείγματα Java και C ++

Τι είναι ο αλγόριθμος γραφήματος;

Οι αλγόριθμοι γραφημάτων είναι ένα σύνολο οδηγιών που διασχίζουν (κόμβους επισκέψεων του α) γραφήματος.

Ορισμένοι αλγόριθμοι χρησιμοποιούνται για την εύρεση ενός συγκεκριμένου κόμβου ή της διαδρομής μεταξύ δύο δεδομένων κόμβων.

Γιατί οι αλγόριθμοι γραφημάτων είναι σημαντικοί

Τα γραφήματα είναι πολύ χρήσιμες δομές δεδομένων που μπορούν να διαμορφώσουν διάφορα προβλήματα. Αυτοί οι αλγόριθμοι έχουν άμεσες εφαρμογές σε ιστότοπους κοινωνικής δικτύωσης, μοντελοποίηση State Machine και πολλά άλλα.

Μερικοί συνήθεις αλγόριθμοι γραφημάτων

Μερικοί από τους πιο κοινούς αλγόριθμους γραφημάτων είναι:

  • Πρώτη αναζήτηση Breadth (BFS)
  • Πρώτη αναζήτηση βάθους (DFS)
  • Ντιζκτρά
  • Αλγόριθμος Floyd-Warshall

Ο αλγόριθμος της Bellman Ford

Ο αλγόριθμος Bellman Ford είναι ένας πιο σύντομος αλγόριθμος εύρεσης διαδρομών για γραφήματα που μπορεί να έχουν αρνητικά βάρη. Ο αλγόριθμος του Bellman ford είναι επίσης εξαιρετικός για την ανίχνευση αρνητικών κύκλων βάρους καθώς ο αλγόριθμος συγκλίνει σε μια βέλτιστη λύση στα βήματα O (V * E). Εάν το αποτέλεσμα δεν είναι βέλτιστο, τότε το γράφημα περιέχει έναν αρνητικό κύκλο βάρους.

Εδώ είναι μια εφαρμογή στο 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. 

Πρώτη αναζήτηση βάθους (DFS)

Depth First Search είναι ένας από τους πιο απλούς αλγόριθμους γραφημάτων. Διασχίζει το γράφημα πρώτα ελέγχοντας τον τρέχοντα κόμβο και μετά μετακινείται σε έναν από τους αποδέκτες του για να επαναλάβει τη διαδικασία. Εάν ο τρέχων κόμβος δεν έχει ελεγκτή για έλεγχο, επιστρέφουμε στον προκάτοχό του και η διαδικασία συνεχίζεται (μεταβαίνοντας σε άλλον επιληπτή). Εάν βρεθεί η λύση, η αναζήτηση σταματά.

Οραματισμός

Υλοποίηση (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; } 

Εκτίμηση

Διαστημική πολυπλοκότητα: O (n)

Χειρότερη πολυπλοκότητα χρόνου υπόθεσης: O (n) Βάθος Η πρώτη αναζήτηση ολοκληρώνεται σε ένα πεπερασμένο σύνολο κόμβων. Δουλεύω καλύτερα σε ρηχά δέντρα.

Υλοποίηση του DFS στο 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;i
    
     adj[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; } 
    

Αλγόριθμος Floyd Warshall

Ο αλγόριθμος Floyd Warshall είναι ένας μεγάλος αλγόριθμος για την εύρεση της μικρότερης απόστασης μεταξύ όλων των κορυφών στο γράφημα. Έχει έναν πολύ συνοπτικό αλγόριθμο και την πολυπλοκότητα του O (V ^ 3) (όπου το V είναι αριθμός κορυφών) Μπορεί να χρησιμοποιηθεί με αρνητικά βάρη, αν και οι αρνητικοί κύκλοι βάρους δεν πρέπει να υπάρχουν στο γράφημα.

Εκτίμηση

Διαστημική πολυπλοκότητα: O (V ^ 2)

Χειρότερη πολυπλοκότητα χρόνου υπόθεσης: O (V ^ 3)

Εφαρμογή 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)) 

Πρώτη αναζήτηση Breadth (BFS)

Το Breadth First Search είναι ένας από τους πιο απλούς αλγόριθμους γραφημάτων. Διασχίζει το γράφημα ελέγχοντας πρώτα τον τρέχοντα κόμβο και στη συνέχεια επεκτείνοντάς το προσθέτοντας τους διαδόχους του στο επόμενο επίπεδο. Η διαδικασία επαναλαμβάνεται για όλους τους κόμβους στο τρέχον επίπεδο πριν προχωρήσει στο επόμενο επίπεδο. Εάν βρεθεί η λύση, η αναζήτηση σταματά.

Οραματισμός

Εκτίμηση

Διαστημική πολυπλοκότητα: O (n)

Χειρότερη πολυπλοκότητα χρόνου υπόθεσης: O (n)

Το Breadth First Search είναι πλήρες σε ένα πεπερασμένο σύνολο κόμβων και βέλτιστο εάν το κόστος μετακίνησης από έναν κόμβο σε άλλο είναι σταθερό.

Κωδικός C ++ για εφαρμογή 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; } 

Ο Αλγόριθμος της Dijkstra

Ο Αλγόριθμος της Dijkstra είναι ένας αλγόριθμος γραφημάτων που παρουσιάζεται από τον EW Dijkstra. Βρίσκει τη μικρότερη διαδρομή μίας πηγής σε ένα γράφημα με μη αρνητικά άκρα. (Γιατί;)

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