Ce este un algoritm grafic?

Algoritmii graficului sunt un set de instrucțiuni care traversează (vizitează nodurile unui) grafic.

Unii algoritmi sunt utilizați pentru a găsi un anumit nod sau calea dintre două noduri date.

De ce sunt importante algoritmii grafici

Graficele sunt structuri de date foarte utile care pot fi pentru a modela diverse probleme. Acești algoritmi au aplicații directe pe site-urile de rețea socială, modelarea mașinii de stat și multe altele.

Câteva algoritmi grafici comuni

Unii dintre cei mai comuni algoritmi de grafic sunt:

  • Breadth First Search (BFS)
  • Căutare în adâncime (DFS)
  • Dijkstra
  • Algoritmul Floyd-Warshall

Algoritmul lui Bellman Ford

Algoritmul lui Bellman Ford este cel mai scurt algoritm de găsire a căilor pentru grafice care pot avea greutăți negative. Algoritmul lui Bellman Ford este, de asemenea, excelent pentru detectarea ciclurilor de greutate negative, deoarece algoritmul converge la o soluție optimă în pași O (V * E). Dacă rezultatul nu este optim, atunci graficul conține un ciclu de greutate negativ.

Iată o implementare în 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.

Căutare în adâncime (DFS)

Căutarea în adâncime este unul dintre cei mai simpli algoritmi grafici. Acesta traversează graficul verificând mai întâi nodul curent și apoi mutându-se la unul dintre succesorii săi pentru a repeta procesul. Dacă nodul curent nu are nici un succesor de verificat, ne întoarcem la predecesorul său și procesul continuă (prin mutarea la un alt succesor). Dacă soluția este găsită, căutarea se oprește.

Vizualizare

1611336545 872 Algoritmi grafici

Implementare (C ++ 14)

#include <iostream> 
#include <vector> 
#include <queue>  
#include <algorithm>
using namespace std; 
 
class Graph{ 
   int v;    // number of vertices 
 
   // pointer to a vector containing adjacency lists 
   vector < int > *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 < bool> &visited);   
}; 
 
Graph::Graph(int v){ 
   this -> v = v; 
   adj = new vector < int >[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 < bool > 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 < bool > &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 < int > :: 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; 
} 

Evaluare

Complexitate spațială: O (n)

Complexitate de timp mai gravă: O (n) Căutarea în adâncime este completă pe un set finit de noduri. Lucrez mai bine la copaci puțin adânci.

Implementarea DFS în C ++

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

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<int> DFS(int s);
		void DFSUtil(int s,vector<int> &dfs,vector<bool> &visited);
};
Graph::Graph(int vcount){
	this->v = vcount;
	this->adj=new bool*[vcount];
	for(int i=0;i<vcount;i++)
		this->adj[i]=new bool[vcount];
	for(int i=0;i<vcount;i++)
		for(int j=0;j<vcount;j++)
			adj[i][j]=false;
}

void Graph::addEdge(int u,int w){
	this->adj[u][w]=true;
	this->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<int> &dfs, vector<bool> &visited){
	visited[s]=true;
	dfs.push_back(s);
	for(int i=0;i<this->v;i++){
		if(this->adj[s][i]==true && visited[i]==false)
			DFSUtil(i,dfs,visited);
	}
}

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

Algoritmul Floyd Warshall

Algoritmul Floyd Warshall este un algoritm excelent pentru a găsi cea mai mică distanță între toate vârfurile din grafic. Are un algoritm foarte concis și complexitatea timpului O (V ^ 3) (unde V este numărul de vârfuri). Poate fi utilizat cu greutăți negative, deși ciclurile de greutate negative nu trebuie să fie prezente în grafic.

Evaluare

Complexitatea spațială: O (V ^ 2)

Complexitate de timp mai gravă: O (V ^ 3)

Implementare 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 First Search (BFS)

Breadth First Search este unul dintre cei mai simpli algoritmi grafici. Acesta traversează graficul verificând mai întâi nodul curent și apoi extinzându-l prin adăugarea succesorilor săi la nivelul următor. Procesul se repetă pentru toate nodurile din nivelul curent înainte de a trece la nivelul următor. Dacă soluția este găsită, căutarea se oprește.

Vizualizare

Algoritmi grafici

Evaluare

Complexitate spațială: O (n)

Complexitate de timp mai gravă: O (n)

Breadth First Search este completă pe un set finit de noduri și optimă dacă costul deplasării de la un nod la altul este constant.

Cod C ++ pentru implementarea BFS

// Program to print BFS traversal from a given 
// source vertex. BFS(int s) traverses vertices  
// reachable from s. 
#include<iostream> 
#include <list> 
  
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<int> *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<int>[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<int> 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<int>::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; 
}

Algoritmul lui Dijkstra

Algoritmul lui Dijkstra este un algoritm grafic prezentat de EW Dijkstra. Găsește cea mai scurtă cale a sursei unice într-un grafic cu muchii non-negative. (De ce?)

Creăm 2 matrice: vizitate și distanță, care înregistrează dacă un vârf este vizitat și, respectiv, care este distanța minimă față de vârful sursă. Matricea vizitată inițial este atribuită ca falsă și distanța ca infinită.

Începem de la vârful sursă. Fie că vârful curent să fie u și vârfurile sale adiacente să fie v. Acum, pentru fiecare v care este adiacent lui u, distanța este actualizată dacă nu a fost vizitată anterior și distanța de la u este mai mică decât distanța sa actuală. Apoi selectăm următorul vârf cu cea mai mică distanță și care nu a fost vizitat.

Coada prioritară este adesea utilizată pentru a îndeplini această ultimă cerință în cel mai mic timp. Mai jos este o implementare a aceleiași idei folosind coada prioritară în Java.

import java.util.*;
public class Dijkstra {
    class Graph {
	LinkedList<Pair<Integer>> adj[];
	int n; // Number of vertices.
	Graph(int n) {
	    this.n = n;
	    adj = new LinkedList[n];
	    for(int i = 0;i<n;i++) adj[i] = new LinkedList<>();
	}
	// add a directed edge between vertices a and b with cost as weight
	public void addEdgeDirected(int a, int b, int cost) {
	    adj[a].add(new Pair(b, cost));
	}
	public void addEdgeUndirected(int a, int b, int cost) {
	    addEdgeDirected(a, b, cost);
	    addEdgeDirected(b, a, cost);
	}
    }
    class Pair<E> {
	E first;
	E second;
	Pair(E f, E s) {
	    first = f;
	    second = s;
	}
    }

    // Comparator to sort Pairs in Priority Queue
    class PairComparator implements Comparator<Pair<Integer>> {
	public int compare(Pair<Integer> a, Pair<Integer> 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<Pair<Integer>> pq = new PriorityQueue<>(100, new PairComparator());
        pq.add(new Pair<Integer>(src, 0));
	distance[src] = 0;
	while(!pq.isEmpty()) {
	    Pair<Integer> x = pq.remove(); // Extract vertex with shortest distance from src
	    int u = x.first;
	    visited[u] = true;
	    Iterator<Pair<Integer>> iter = g.adj[u].listIterator();
	    // Iterate over neighbours of u and update their distances
	    while(iter.hasNext()) {
		Pair<Integer> 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<distance[v]) {
		    distance[v] = distance[u]+weight;
		    pq.add(new Pair(v, distance[v]));
		}
	    }
	}
	return distance;
    }

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

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

Algoritmul Ford Fulkerson

Algoritmul Ford Fulkerson rezolvă problema graficului de debit maxim. Acesta găsește cea mai bună organizare a fluxului prin marginile graficelor, astfel încât să obțineți debit maxim pe celălalt capăt. Sursa are o rată specifică de intrare și fiecare margine are o greutate asociată cu ea, care este substanța maximă care poate fi trecută prin acea margine.

Algoritmul Ford Fulkerson este, de asemenea, numit algoritm Edmund-Karp, deoarece algoritmul a fost furnizat în specificații complete de Jack Edmonds și Richard Karp.

Funcționează prin crearea de căi de mărire, adică de la sursă la scufundare, care au un flux diferit de zero. Trecem fluxul prin căi și actualizăm limitele. Acest lucru poate duce la situația în care nu mai avem mișcări. Acolo capacitatea de „anulare” a acestui algoritm joacă un rol important. În caz de blocare, reducem fluxul și deschidem marginea pentru a trece substanța noastră actuală.

Pași

  1. Setați fluxul zero pentru toate marginile.
  2. Deși există o cale de la sursă la scufundare,
  3. Găsiți greutatea minimă pe cale, lăsați-o să fie limit .
  4. Pentru toate muchiile (u, v) de pe cale,
    1. Adăugați limit a curge de la u la v. (Pentru mutarea curentă)
    2. Scade limit de la fluxul de la v la u. (Pentru anulare în mutare ulterioară)

Evaluare

Complexitatea timpului: O(V*E^2)

Implementare Python

# 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