Grafikonalgoritmusok és adatstruktúrák Java és C ++ példákkal magyarázva

Mi az a grafikon algoritmus?

A gráfalgoritmusok egy olyan utasításkészlet, amely bejárja (meglátogatja az a) gráf csomópontjait.

Néhány algoritmust használnak egy adott csomópont vagy két adott csomópont közötti útvonal megkeresésére.

Miért fontosak a grafikon algoritmusok?

A grafikonok nagyon hasznos adatstruktúrák, amelyek különböző problémák modellezésére szolgálhatnak. Ezeknek az algoritmusoknak közvetlen alkalmazásuk van a közösségi oldalakon, az State Machine modellezés és még sok más.

Néhány közös grafikon algoritmus

Néhány leggyakoribb grafikonalgoritmus a következő:

  • Szélesség első keresése (BFS)
  • Mélység első keresés (DFS)
  • Dijkstra
  • Floyd-Warshall algoritmus

Bellman Ford algoritmusa

Bellman Ford algoritmusa a legrövidebb útkereső algoritmus olyan gráfokhoz, amelyek negatív súlyúak lehetnek. Bellman ford algoritmusa nagyszerű a negatív súlyciklusok detektálására is, mivel az algoritmus O (V * E) lépésekben konvergál az optimális megoldáshoz. Ha az eredmény nem optimális, akkor a grafikon negatív súlyciklust tartalmaz.

Itt van egy megvalósítás a Pythonban:

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. 

Mélység első keresés (DFS)

A Depth First Search az egyik legegyszerűbb grafikonalgoritmus. Átjárja a grafikont úgy, hogy először ellenőrzi az aktuális csomópontot, majd az eljárás egyik megismétléséhez az egyik utódjához lép. Ha az aktuális csomópontnak nincs utódja, amelyet ellenőrizhet, akkor visszalépünk az elődjéhez, és a folyamat folytatódik (egy másik utódra való áttéréssel). Ha megtalálják a megoldást, a keresés leáll.

Megjelenítés

Végrehajtás (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; } 

Értékelés

Tér összetettsége: O (n)

Rosszabb eset időbeli komplexitás: O (n) A mélység első keresése véges csomópontkészleten teljes. Jobban dolgozom sekély fákon.

DFS megvalósítása C ++ nyelven

#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; } 

Floyd Warshall algoritmus

A Floyd Warshall algoritmus remek algoritmus a gráf összes csúcsa közötti legrövidebb távolság megtalálásához. Nagyon tömör algoritmussal és O (V ^ 3) idő komplexitással rendelkezik (ahol V a csúcsok száma). Negatív súlyokkal használható, bár a negatív súlyciklusok nem lehetnek jelen a grafikonon.

Értékelés

Tér összetettsége: O (V ^ 2)

Rosszabb eset időbeli összetettsége: O (V ^ 3)

Python implementáció

# 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)) 

Szélesség első keresése (BFS)

A Breadth First Search az egyik legegyszerűbb grafikonalgoritmus. Átjárja a grafikont úgy, hogy először ellenőrzi az aktuális csomópontot, majd kibővíti az utódok következő szintre emelésével. A folyamat megismétlődik az aktuális szint összes csomópontján, mielőtt a következő szintre lépne. Ha megtalálják a megoldást, a keresés leáll.

Megjelenítés

Értékelés

Tér összetettsége: O (n)

A rosszabb eset időbeli összetettsége: O (n)

A Szélesség első keresése véges csomópontkészleten teljes, és akkor optimális, ha az egyik csomópontról a másikra való költözés költsége állandó.

C ++ kód a BFS megvalósításához

// 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 algoritmusa

A Dijkstra algoritmusa egy grafikon algoritmus, amelyet EW Dijkstra mutat be. Megtalálja az egyetlen forrás legrövidebb útját egy nem negatív élű grafikonon. (Miért?)

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