algorithm
Graphique

Introduction

Remarques

Tri topologique

Un ordre topologique, ou un tri topologique, ordonne les sommets dans un graphe acyclique dirigé sur une ligne, c'est-à-dire dans une liste, de sorte que tous les bords dirigés vont de gauche à droite. Un tel ordre ne peut exister si le graphique contient un cycle dirigé, car il est impossible de continuer sur une ligne et de revenir à votre point de départ.

Formellement, dans un graphe G = (V, E) , un ordre linéaire de tous ses sommets est tel que si G contient une arête (u, v) ∈ E du sommet u au sommet v alors u précède v dans l’ordre.

Il est important de noter que chaque DAG a au moins un tri topologique.

Il existe des algorithmes connus pour construire un ordre topologique de n'importe quel DAG en temps linéaire, par exemple:

1. Appelez depth_first_search(G) pour calculer les temps de finition vf pour chaque sommet v
2. Au fur et à mesure que chaque sommet est terminé, insérez-le au début d'une liste chaînée
3. la liste des sommets liés, telle qu'elle est maintenant triée.

Un tri topologique peut être effectué en temps ϴ(V + E) , puisque l'algorithme de recherche en profondeur prend ϴ(V + E) et nécessite Ω(1) (temps constant) pour insérer chacun de |V| sommets dans le front d'une liste chaînée.

De nombreuses applications utilisent des graphiques acycliques dirigés pour indiquer les priorités parmi les événements. Nous utilisons un tri topologique pour obtenir un ordre de traitement de chaque sommet avant chacun de ses successeurs.

Les sommets d'un graphique peuvent représenter des tâches à exécuter et les arcs peuvent représenter des contraintes qu'une tâche doit être exécutée avant une autre; un ordre topologique est une séquence valide pour effectuer l'ensemble de tâches décrit dans V

Instance de problème et sa solution

Soit un vertice v décrire une Task(hours_to_complete: int) , c. -à- Task(4) décrit un Task de qui prend 4 heures pour terminer, et un bord e décrivent un Cooldown(hours: int) de Cooldown(3) Cooldown(hours: int) de telle sorte que de Cooldown(3) présente une durée de temps de refroidir après une tâche terminée.

Soit notre graphe appelé dag (puisque c'est un graphe acyclique dirigé), et laissez-le contenir 5 sommets:

A <- dag.add_vertex(Task(4)); 
B <- dag.add_vertex(Task(5));
C <- dag.add_vertex(Task(3)); 
D <- dag.add_vertex(Task(2));
E <- dag.add_vertex(Task(7));

où nous connectons les sommets avec des arêtes dirigées telles que le graphique est acyclique,

// A ---> C ----+
// |      |     |
// v      v     v
// B ---> D --> E
dag.add_edge(A, B, Cooldown(2));
dag.add_edge(A, C, Cooldown(2));
dag.add_edge(B, D, Cooldown(1));
dag.add_edge(C, D, Cooldown(1));
dag.add_edge(C, E, Cooldown(1));
dag.add_edge(D, E, Cooldown(3));

il y a alors trois ordres topologiques possibles entre A et E ,

1. A -> B -> D -> E
2. A -> C -> D -> E
3. A -> C -> E

L'algorithme de Thorup

L'algorithme de Thorup pour le chemin le plus court à source unique pour le graphe non dirigé a la complexité temporelle O (m), inférieure à celle de Dijkstra.

Les idées de base sont les suivantes. (Désolé, je n'ai pas encore essayé de l'implémenter, alors certains détails mineurs me manqueront. Et le papier original est protégé par un mur de paye, alors j'ai essayé de le reconstituer à partir d'autres sources. Supprimez ce commentaire si vous pouvez vérifier.)

• Il existe des moyens de trouver l'arbre couvrant dans O (m) (non décrit ici). Vous devez "faire croître" le spanning tree du bord le plus court au plus long, et ce serait une forêt avec plusieurs composants connectés avant sa pleine croissance.
• Sélectionnez un entier b (b> = 2) et ne considérez que les forêts couvrantes avec une limite de longueur b ^ k. Fusionnez les composants qui sont exactement les mêmes mais avec un k différent, et appelez le minimum k le niveau du composant. Faites ensuite logiquement des composants dans un arbre. u est le parent de vsi u est le plus petit composant distinct de v qui contient entièrement v. La racine est le graphe entier et les feuilles sont des sommets simples dans le graphe original (avec le niveau d'infini négatif). L'arbre n'a encore que des noeuds O (n).
• Maintenir la distance de chaque composant à la source (comme dans l'algorithme de Dijkstra). La distance d'un composant avec plusieurs sommets est la distance minimale de ses enfants non développés. Définissez la distance du sommet source sur 0 et mettez à jour les ancêtres en conséquence.
• Considérez les distances dans la base b. Lorsque vous visitez un nœud du niveau k la première fois, placez ses enfants dans des compartiments partagés par tous les nœuds de niveau k (comme dans le type seau, remplaçant le tas dans l'algorithme de Dijkstra) par le chiffre k et supérieur. À chaque fois que vous visitez un nœud, considérez uniquement ses premiers segments, visitez chacun d'eux et supprimez-les, mettez à jour la distance du nœud actuel et reliez le nœud actuel à son propre parent en utilisant la nouvelle distance et attendez la prochaine visite pour les éléments suivants. seaux.
• Lorsqu'une feuille est visitée, la distance actuelle est la distance finale du sommet. Développez tous les bords du graphique d'origine et mettez à jour les distances en conséquence.
• Visitez le nœud racine (graphe entier) à plusieurs reprises jusqu'à ce que la destination soit atteinte.

Il est basé sur le fait qu’il n’existe pas d’extrémité de longueur inférieure à 1 entre deux composants connectés de la forêt couvrant avec une limite de longueur l, donc, à partir de la distance x, vous pouvez vous concentrer sur un seul composant la distance x + l. Vous visiterez des sommets avant que les sommets de plus courte distance ne soient tous visités, mais cela n'a aucune importance car on sait qu'il n'y aura pas de chemin plus court vers ces sommets. D'autres parties fonctionnent comme le tri par base de type compartiment / MSD et, bien sûr, elles requièrent l'arbre couvrant O (m).

Détecter un cycle dans un graphe orienté à l'aide de la méthode Traject First Traversal

Il existe un cycle dans un graphe orienté s’il existe un bord arrière découvert lors d’un DFS. Un bord arrière est une arête d'un nœud à lui-même ou à l'un des ancêtres d'une arborescence DFS. Pour un graphique déconnecté, nous obtenons une forêt DFS, vous devez donc parcourir tous les sommets du graphique pour trouver des arborescences DFS disjointes.

Implémentation C ++:

    #include <iostream>
     #include <list>
        
    using namespace std; 
    
    #define NUM_V   4

    bool helper(list<int> *graph, int u, bool* visited, bool* recStack)
    {
        visited[u]=true;
        recStack[u]=true;
        list<int>::iterator i;
        for(i = graph[u].begin();i!=graph[u].end();++i)
        {  
            if(recStack[*i]) //if vertice v is found in recursion stack of this DFS traversal
                return true;
            else if(*i==u) //if there's an edge from the vertex to itself
                return true;
            else if(!visited[*i])
            {   if(helper(graph, *i, visited, recStack))
                   return true;
            }
        }
        recStack[u]=false;
        return false;
    }
    /*
    /The wrapper function calls helper function on each vertices which have not been visited. Helper function returns true if it detects a back edge in the subgraph(tree) or false.
*/
    bool isCyclic(list<int> *graph, int V)
    {
      bool visited[V];  //array to track vertices already visited
      bool recStack[V]; //array to track vertices in recursion stack of the traversal.

      for(int i = 0;i<V;i++)
       visited[i]=false, recStack[i]=false;  //initialize all vertices as not visited and not recursed

      for(int u = 0; u < V; u++) //Iteratively checks if every vertices have been visited
      {   if(visited[u]==false)
          {  if(helper(graph, u, visited, recStack)) //checks if the DFS tree from the vertex contains a cycle
               return true;
          }
      }
       return false;
    }
    /*
    Driver function
    */
    int main()
    {
        list<int>* graph = new list<int>[NUM_V];
        graph[0].push_back(1);
        graph[0].push_back(2);
        graph[1].push_back(2);
        graph[2].push_back(0);
        graph[2].push_back(3);
        graph[3].push_back(3);
        bool res = isCyclic(graph, NUM_V);
        cout<<res<<endl;
    }

Résultat: comme indiqué ci-dessous, il y a trois bords arrière dans le graphique. Un entre les sommets 0 et 2; entre les sommets 0, 1 et 2; et sommet 3. La complexité temporelle de la recherche est O (V + E) où V est le nombre de sommets et E est le nombre d'arêtes.

Introduction à la théorie des graphes

La théorie des graphes est l'étude des graphes, qui sont des structures mathématiques utilisées pour modéliser les relations par paires entre les objets.

Saviez-vous que presque tous les problèmes de la planète Terre peuvent être transformés en problèmes de routes et de villes et résolus? La théorie des graphes a été inventée il y a plusieurs années, même avant l'invention de l'ordinateur. Leonhard Euler a écrit un article sur les sept ponts de Königsberg, considéré comme le premier article de la théorie des graphes. Depuis lors, les gens se sont rendu compte que si nous pouvions convertir n'importe quel problème à ce problème City-Road, nous pourrons le résoudre facilement grâce à la théorie des graphes.

La théorie des graphes a de nombreuses applications. L'une des applications les plus courantes consiste à trouver la distance la plus courte entre une ville et une autre. Nous savons tous que pour accéder à votre PC, cette page Web devait parcourir de nombreux routeurs à partir du serveur. La théorie des graphes l'aide à trouver les routeurs à croiser. Pendant la guerre, quelle rue doit être bombardée pour déconnecter la capitale des autres, cela peut aussi être découvert en utilisant la théorie des graphes.

Laissez-nous d'abord apprendre quelques définitions de base sur la théorie des graphes.

Graphique:

Disons que nous avons 6 villes. Nous les marquons comme 1, 2, 3, 4, 5, 6. Nous connectons maintenant les villes qui ont des routes entre elles.

Ceci est un graphique simple où certaines villes sont affichées avec les routes qui les connectent. Dans la théorie des graphes, nous appelons chacune de ces villes Nœud ou Sommet et les routes sont appelées Edge. Le graphique est simplement une connexion de ces nœuds et arêtes.

Un nœud peut représenter beaucoup de choses. Dans certains graphiques, les nœuds représentent des villes, certains représentent des aéroports, certains représentent un carré dans un échiquier. Edge représente la relation entre chaque nœud. Cette relation peut être le moment d'aller d'un aéroport à un autre, les déplacements d'un chevalier d'un carré à tous les autres carrés, etc.

Chemin du chevalier dans un échiquier

Dans les mots simples, un nœud représente n'importe quel objet et Edge représente la relation entre deux objets.

Noeud adjacent:

Si un nœud A partage un bord avec le nœud B , alors B est considéré comme adjacent à A. En d'autres termes, si deux nœuds sont directement connectés, ils sont appelés nœuds adjacents. Un nœud peut avoir plusieurs nœuds adjacents.

Graphique dirigé et non dirigé:

Dans les graphes dirigés, les arêtes ont des signes de direction sur un côté, ce qui signifie que les arêtes sont unidirectionnelles . Par ailleurs, les arêtes des graphes non orientés ont des signes de direction des deux côtés, ce qui signifie qu'ils sont bidirectionnels . Les graphes non dirigés sont généralement représentés sans signe des deux côtés des arêtes.

Supposons qu'il y ait une fête en cours. Les membres du groupe sont représentés par des nœuds et il y a un avantage entre deux personnes s'ils se serrent la main. Ensuite, ce graphique n'est pas dirigé car toute personne A serre la main de la personne B si et seulement si B serre la main avec A. En revanche, si les bords d'une personne A à une autre personne B correspond à admirer B de A, ce graphique est dirigé, parce que l' admiration est pas nécessairement un mouvement alternatif. Le premier type de graphe est appelé graphe non dirigé et les arêtes sont appelées arêtes non dirigées tandis que le dernier type de graphe est appelé graphe orienté et les arêtes sont appelées arêtes dirigées.

Graphique pondéré et non pondéré:

Un graphique pondéré est un graphique dans lequel un nombre (le poids) est attribué à chaque arête. Ces pondérations peuvent représenter, par exemple, les coûts, les longueurs ou les capacités, en fonction du problème rencontré.

Un graphique non pondéré est simplement l'inverse. Nous supposons que le poids de toutes les arêtes est le même (probablement 1).

Chemin:

Un chemin représente un moyen de passer d'un nœud à un autre. Il consiste en une séquence de bords. Il peut y avoir plusieurs chemins entre deux nœuds.

Dans l'exemple ci-dessus, il existe deux chemins de A à D. A-> B, B-> C, C-> D est un chemin. Le coût de ce chemin est 3 + 4 + 2 = 9 . Encore une fois, il y a un autre chemin A-> D. Le coût de ce chemin est de 10 . Le chemin qui coûte le plus bas est appelé le plus court chemin .

Degré:

Le degré d'un sommet est le nombre d'arêtes qui lui sont connectées. S'il y a un bord qui se connecte au sommet aux deux extrémités (une boucle) est compté deux fois.

Dans les graphes dirigés, les nœuds ont deux types de degrés:

• In-degree: nombre d'arêtes pointant vers le nœud.
• Out-degree: nombre de fronts qui pointent du nœud vers d'autres nœuds.

Pour les graphiques non orientés, ils sont simplement appelés degré.

Quelques algorithmes liés à la théorie des graphes

• Algorithme Bellman – Ford
• L'algorithme de Dijkstra
• Algorithme Ford – Fulkerson
• L'algorithme de Kruskal
• Algorithme du plus proche voisin
• L'algorithme de Prim
• Profondeur première recherche
• Recherche en largeur

Stockage de graphiques (matrice d'adjacence)

Pour stocker un graphique, deux méthodes sont communes:

• Matrice d'adjacence
• Liste d'adjacence

Une matrice d'adjacence est une matrice carrée utilisée pour représenter un graphe fini. Les éléments de la matrice indiquent si les paires de sommets sont adjacentes ou non dans le graphique.

Adjacent signifie «à côté ou à côté de quelque chose» ou à côté de quelque chose. Par exemple, vos voisins sont adjacents à vous. En théorie des graphes, si on peut aller au nœud B du nœud A , on peut dire que le nœud B est adjacent au nœud A. Nous allons maintenant apprendre à stocker quels nœuds sont adjacents à celui via Adjacency Matrix. Cela signifie que nous allons représenter les nœuds partageant un bord entre eux. Ici, la matrice signifie un tableau 2D.

Ici vous pouvez voir un tableau à côté du graphique, c'est notre matrice d'adjacence. Ici, la matrice [i] [j] = 1 représente un bord entre i et j . S'il n'y a pas de bord, nous mettons simplement Matrix [i] [j] = 0 .

Ces arêtes peuvent être pondérées, comme si elles pouvaient représenter la distance entre deux villes. Ensuite, nous mettrons la valeur dans Matrix [i] [j] au lieu de mettre 1.

Le graphe décrit ci-dessus est bidirectionnel ou non dirigé , ce qui signifie que si nous pouvons aller au nœud 1 du nœud 2 , nous pouvons également aller au nœud 2 du nœud 1 . Si le graphique était dirigé , il y aurait eu un signe de flèche sur un côté du graphique. Même dans ce cas, nous pourrions le représenter en utilisant une matrice de contiguïté.

Nous représentons les nœuds qui ne partagent pas l'arête à l' infini . Une chose à noter est que si le graphe n'est pas orienté, la matrice devient symétrique .

Le pseudo-code pour créer la matrice:

Procedure AdjacencyMatrix(N):    //N represents the number of nodes
Matrix[N][N]
for i from 1 to N
    for j from 1 to N
        Take input -> Matrix[i][j]
    endfor
endfor

Nous pouvons également remplir la matrice en utilisant cette méthode commune:

Procedure AdjacencyMatrix(N, E):    // N -> number of nodes
Matrix[N][E]                        // E -> number of edges
for i from 1 to E
    input -> n1, n2, cost
    Matrix[n1][n2] = cost
    Matrix[n2][n1] = cost
endfor

Pour les graphes dirigés, nous pouvons supprimer Matrix [n2] [n1] = ligne de coût .

Les inconvénients de l'utilisation d'Adjacency Matrix:

La mémoire est un énorme problème. Peu importe le nombre d'arêtes présentes, nous aurons toujours besoin d'une matrice de taille N * N où N est le nombre de nœuds. S'il y a 10000 nœuds, la taille de la matrice sera de 4 * 10000 * 10000 autour de 381 mégaoctets. Ceci est un énorme gaspillage de mémoire si l'on considère les graphiques qui ont quelques bords.

Supposons que nous voulions savoir à quel nœud nous pouvons aller depuis un nœud u . Nous devons vérifier toute la rangée de u , ce qui coûte beaucoup de temps.

Le seul avantage est que nous pouvons facilement trouver la connexion entre les nœuds uv et leur coût en utilisant Adjacency Matrix.

Code Java implémenté en utilisant le pseudo-code ci-dessus:

import java.util.Scanner;
 
public class Represent_Graph_Adjacency_Matrix 
{
    private final int vertices;
    private int[][] adjacency_matrix;
 
    public Represent_Graph_Adjacency_Matrix(int v) 
    {
        vertices = v;
        adjacency_matrix = new int[vertices + 1][vertices + 1];
    }
 
    public void makeEdge(int to, int from, int edge) 
    {
        try 
        {
            adjacency_matrix[to][from] = edge;
        }
        catch (ArrayIndexOutOfBoundsException index) 
        {
            System.out.println("The vertices does not exists");
        }
    }
 
    public int getEdge(int to, int from) 
    {
        try 
        {
            return adjacency_matrix[to][from];
        }
        catch (ArrayIndexOutOfBoundsException index) 
        {
            System.out.println("The vertices does not exists");
        }
        return -1;
    }
 
    public static void main(String args[]) 
    {
        int v, e, count = 1, to = 0, from = 0;
        Scanner sc = new Scanner(System.in);
        Represent_Graph_Adjacency_Matrix graph;
        try 
        {
            System.out.println("Enter the number of vertices: ");
            v = sc.nextInt();
            System.out.println("Enter the number of edges: ");
            e = sc.nextInt();
 
            graph = new Represent_Graph_Adjacency_Matrix(v);
 
            System.out.println("Enter the edges: <to> <from>");
            while (count <= e) 
            {
                to = sc.nextInt();
                from = sc.nextInt();
 
                graph.makeEdge(to, from, 1);
                count++;
            }
 
            System.out.println("The adjacency matrix for the given graph is: ");
            System.out.print("  ");
            for (int i = 1; i <= v; i++)
                System.out.print(i + " ");
            System.out.println();
 
            for (int i = 1; i <= v; i++) 
            {
                System.out.print(i + " ");
                for (int j = 1; j <= v; j++) 
                    System.out.print(graph.getEdge(i, j) + " ");
                System.out.println();
            }
 
        }
        catch (Exception E) 
        {
            System.out.println("Somthing went wrong");
        }
 
        sc.close();
    }
}

Exécution du code: Enregistrez le fichier et compilez en utilisant javac Represent_Graph_Adjacency_Matrix.java

Exemple:

$ java Represent_Graph_Adjacency_Matrix
Enter the number of vertices:
4
Enter the number of edges:
6
Enter the edges: <to> <from>
1 1
3 4
2 3
1 4
2 4
1 2
The adjacency matrix for the given graph is:
  1 2 3 4
1 1 1 0 1
2 0 0 1 1
3 0 0 0 1
4 0 0 0 0

Stockage de graphiques (liste d'adjacence)

La liste d'adjacence est une collection de listes non ordonnées utilisées pour représenter un graphe fini. Chaque liste décrit l'ensemble des voisins d'un sommet dans un graphique. Il faut moins de mémoire pour stocker des graphiques.

Voyons un graphique et sa matrice d'adjacence:

Maintenant, nous créons une liste en utilisant ces valeurs.

Ceci s'appelle la liste de contiguïté. Il montre quels nœuds sont connectés à quels nœuds. Nous pouvons stocker ces informations en utilisant un tableau 2D. Mais cela nous coûtera la même mémoire que la matrice d'adjacence. Au lieu de cela, nous allons utiliser la mémoire allouée dynamiquement pour stocker celle-ci.

De nombreuses langues prennent en charge Vector ou List, que nous pouvons utiliser pour stocker la liste d’adjacences. Pour ceux-ci, nous n'avons pas besoin de spécifier la taille de la liste . Il suffit de spécifier le nombre maximum de nœuds.

Le pseudo-code sera:

Procedure Adjacency-List(maxN, E):       // maxN denotes the maximum number of nodes
edge[maxN] = Vector()                    // E denotes the number of edges
for i from 1 to E
    input -> x, y                        // Here x, y denotes there is an edge between x, y
    edge[x].push(y)
    edge[y].push(x)
end for
Return edge

Comme celui-ci est un graphe non orienté, il y a un bord de x à y , il y a aussi un bord de y à x . Si c'était un graphique dirigé, nous omettions le second. Pour les graphiques pondérés, nous devons également stocker les coûts. Nous allons créer un autre vecteur ou une liste nommée cost [] pour les stocker. Le pseudo-code:

Procedure Adjacency-List(maxN, E):
edge[maxN] = Vector()
cost[maxN] = Vector()
for i from 1 to E
    input -> x, y, w
    edge[x].push(y)
    cost[x].push(w)
end for
Return edge, cost

De celui-ci, nous pouvons facilement trouver le nombre total de nœuds connectés à un nœud, et ce que sont ces nœuds. Cela prend moins de temps que la matrice d'adjacence. Mais si nous devions trouver s'il y avait un bord entre u et v , cela aurait été plus facile si nous conservions une matrice d'adjacence.