Cycles dans un graphe non orienté

Question

Étant donné un graphe non orienté G \=( V , E ) avec n sommets (| V | = n ), comment trouver s'il contient un cycle en O ( n ) ?

Answer 1

La réponse est, en réalité, la recherche en largeur d'abord (ou en profondeur d'abord, cela n'a pas vraiment d'importance). Les détails résident dans l'analyse.

Maintenant, quelle est la vitesse de l'algorithme ?

Tout d'abord, imaginez que le graphe n'a pas de cycles. Le nombre d'arêtes est alors O(V), le graphe est une forêt, but atteint.

Maintenant, imaginez que le graphe a des cycles, et que votre algorithme de recherche se termine et signale un succès dans le premier d'entre eux. Le graphe n'est pas dirigé, et donc, lorsque l'algorithme inspecte une arête, il n'y a que deux possibilités : Soit il a visité l'autre extrémité de l'arête, soit il l'a fait et alors, cette arête ferme un cercle. Et dès qu'il voit l'autre sommet de l'arête, ce sommet est "inspecté", il n'y a donc que O(V) de ces opérations. Le deuxième cas ne sera atteint qu'une seule fois tout au long de l'exécution de l'algorithme.

Answer 2

Un simple DFS permet de vérifier si le graphe non orienté donné possède un cycle ou non.

Voici le code C++ de la même chose.

En idée utilisée dans le code ci-dessus es:

Si un nœud qui a déjà été découvert/visité est retrouvé et est n'est pas le nœud parent, alors nous avons un cycle.

Cela peut également être expliqué comme suit (mentionné par @Rafał Dowgird).

Si une arête non explorée mène à un nœud déjà visité, alors le graphe contient un cycle.

Answer 3

APPROCHE DFS AVEC UNE CONDITION(parent != noeud suivant) Voyons le code et comprenons ensuite ce qui se passe :

bool Graph::isCyclicUtil(int v, bool visited[], int parent) 
{ 
    // Mark the current node as visited 
    visited[v] = true; 

    // Recur for all the vertices adjacent to this vertex 
    list<int>::iterator i; 
    for (i = adj[v].begin(); i != adj[v].end(); ++i) 
    { 
        // If an adjacent is not visited, then recur for that adjacent 
        if (!visited[*i]) 
        { 
           if (isCyclicUtil(*i, visited, v)) 
              return true; 
        } 

        // If an adjacent is visited and not parent of current vertex, 
        // then there is a cycle. 
        else if (*i != parent) 
           return true; 
    } 
    return false; 
} 

Le code ci-dessus s'explique de lui-même mais je vais essayer d'expliquer une condition, à savoir *i != parent Ici, si nous supposons que le graphique est

1--2

Ensuite, lorsque nous sommes à 1 et que nous allons à 2, le parent de 2 devient 1 et lorsque nous revenons à 1, comme 1 est dans la matrice adj de 2, puisque le sommet suivant 1 est également le parent de 2, le cycle ne sera pas détecté pour le parent immédiat dans cette approche DFS. Le code fonctionne donc bien.

Answer 4

Je pense que l'hypothèse que le graphe est connecté peut être manipulée. ainsi, vous pouvez utiliser la preuve montrée ci-dessus, que le temps d'exécution est O(|V|). si non, alors |E|>|V|. rappel : le temps d'exécution de DFS est O(|V|+|E|) .

Answer 5

Voici le code que j'ai écrit en C basé sur DFS pour déterminer si un graphe donné est connecté/cyclique ou non. Avec quelques exemples de résultats à la fin. J'espère qu'il vous sera utile :)

#include<stdio.h>
#include<stdlib.h>

/****Global Variables****/
int A[20][20],visited[20],v=0,count=0,n;
int seq[20],s=0,connected=1,acyclic=1;

/****DFS Function Declaration****/
void DFS();

/****DFSearch Function Declaration****/
void DFSearch(int cur);

/****Main Function****/
int main() 
   {    
    int i,j;

    printf("\nEnter no of Vertices: ");
    scanf("%d",&n);

    printf("\nEnter the Adjacency Matrix(1/0):\n");
    for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
        scanf("%d",&A[i][j]);

    printf("\nThe Depth First Search Traversal:\n");

    DFS();

    for(i=1;i<=n;i++)
        printf("%c,%d\t",'a'+seq[i]-1,i);

    if(connected && acyclic)    printf("\n\nIt is a Connected, Acyclic Graph!");
    if(!connected && acyclic)   printf("\n\nIt is a Not-Connected, Acyclic Graph!");
    if(connected && !acyclic)   printf("\n\nGraph is a Connected, Cyclic Graph!");
    if(!connected && !acyclic)  printf("\n\nIt is a Not-Connected, Cyclic Graph!");

    printf("\n\n");
    return 0;
   }

/****DFS Function Definition****/
void DFS()
    { 
    int i;
    for(i=1;i<=n;i++)
        if(!visited[i])
          {
        if(i>1) connected=0;
        DFSearch(i);    
              } 
    }

/****DFSearch Function Definition****/
void DFSearch(int cur) 
    {
    int i,j;
    visited[cur]=++count;

        seq[count]=cur; 
        for(i=1;i<count-1;i++)
                if(A[cur][seq[i]]) 
                   acyclic=0;

    for(i=1;i<=n;i++)
        if(A[cur][i] && !visited[i])
           DFSearch(i);

    }

---

/*Sortie de l'échantillon :

majid@majid-K53SC:~/Desktop$ gcc BFS.c

majid@majid-K53SC:~/Desktop$ ./a.out
************************************

Enter no of Vertices: 10

Enter the Adjacency Matrix(1/0):

0 0 1 1 1 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 
0 0 0 1 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 1 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 1 0 0 0 

The Depdth First Search Traversal:
a,1 c,2 d,3 f,4 b,5 e,6 g,7 h,8 i,9 j,10    

It is a Not-Connected, Cyclic Graph!

majid@majid-K53SC:~/Desktop$ ./a.out
************************************

Enter no of Vertices: 4

Enter the Adjacency Matrix(1/0):
0 0 1 1
0 0 1 0
1 1 0 0
0 0 0 1

The Depth First Search Traversal:
a,1 c,2 b,3 d,4 

It is a Connected, Acyclic Graph!

majid@majid-K53SC:~/Desktop$ ./a.out
************************************

Enter no of Vertices: 5

Enter the Adjacency Matrix(1/0):
0 0 0 1 0
0 0 0 1 0
0 0 0 0 1
1 1 0 0 0 
0 0 1 0 0

The Depth First Search Traversal:
a,1 d,2 b,3 c,4 e,5 

It is a Not-Connected, Acyclic Graph!

*/