Détection de cycles dans une matrice d'adjacence

Laisser A être la matrice d'adjacence du graphe G = (V,E). A(i,j) = 1 si les nœuds i et j sont reliés par une arête, A(i,j) = 0 autrement.

Mon objectif est celui de savoir si la G est acyclique ou pas. Un cycle est défini de la manière suivante:

  • i et j sont connectés: A(i,j) = 1
  • j et k sont connectés: A(j,k) = 1
  • k et i sont connectés: A(k,i) = 1

J'ai mis en œuvre une solution qui navigue dans la matrice comme suit:

  • Démarrer à partir d'un bord (i,j)
  • Sélectionnez le jeu O de bords, qui sont les sortants de jc'est à dire, toutes les 1s dans le j-ième ligne de A
  • Naviguer O dans un DFS de mode
  • Si l'un des chemins générés à partir de cette navigation mène vers le nœud ipuis un cycle est détecté

Évidemment, cette solution est très lent, depuis que j'ai ont à évaluer tous les chemins d'accès dans la matrice. Si A est très grand, les frais généraux est très grand. Je me demandais si il existe un moyen de naviguer sur la matrice de contiguïté, de manière à trouver des cycles sans l'aide d'un coûteux algorithme tel que DFS.

J'aimerais implémenter ma solution dans MATLAB.

Merci d'avance,

Eleanore.

source d'informationauteur Eleanore