Trouver une source d'un graphique acyclique dirigé en temps linéaire

Étant donné un graphique acyclique dirigé $D = (V,A)$ , un sommet $v \in V$ est une source si son indegree est nul, ce qui signifie qu'il n'a que des arcs sortants.

Existe-t-il un algorithme de temps linéaire pour trouver une source dans un graphe acyclique dirigé donné?

Question de suivi: peut-on trouver en temps linéaire toutes les sources?

algorithms graph-theory breezeintopl
la source

Par racine, voulez-vous dire un nœud qui a tous les fronts sortants et aucun front entrant? Si c'est le cas, il peut y avoir plus d'une racine.

Paresh

Oui, tu as raison. C'est pourquoi je dis "une racine" mais pas "la racine".

breezeintopl

Dans ce cas, la définition n'est-elle pas suffisante pour un algorithme de temps linéaire?

Paresh

Quelle est la structure des données? Vous donne-t-on une matrice d'adjacence, des listes de voisinage, une liste d'adjacence ou quoi? Pouvez-vous vérifier le voisinage (entrant) d'un sommet en temps proportionnel à sa taille?

Pål GD

Si vous voulez dire linéaire dans le nombre de sommets, vous devez l'indiquer. De plus, les listes de contiguïté sont ambiguës pour les graphiques dirigés - listez-vous les bords entrants, les bords sortants, les deux dans des listes séparées, ou les deux ensemble?

Yuval Filmus

Réponses:

Comme le mentionne Yuval, la structure de données est importante ici. Je vais essayer de donner une solution pour certains des types de listes d'adjacence:

Liste des bords entrants : Pour chaque nœud, il existe une liste de sommets à partir desquels il y a un bord entrant vers ce nœud. Vous pouvez simplement scanner tous les sommets et vérifier si la taille de leur liste d'adjacence est $0$ ou pas. Une taille $0$ liste signifie pas de fronts entrants, donc le nœud est soit une source, soit déconnecté. En supposant un graphique connecté, ce balayage de chaque sommet vous donnera une liste de toutes les sources (ou vous pouvez arrêter après en avoir trouvé un) dans $O(|V|)$ temps - linéaire dans le nombre de sommets .
Liste des arêtes sortantes : Pour chaque nœud, il existe une liste de sommets vers lesquels il existe une arête dirigée à partir de ce nœud. Conservez une chaîne de bits avec chaque bit représentant un sommet, initialisé à 0. À partir du premier nœud, commencez à parcourir sa liste pour les sommets auxquels il y a un bord sortant. Chacun de ces nœuds (voisins) ne peut pas être une source, alors continuez à définir leur bit correspondant dans la chaîne de bits. À la fin, tous les sommets dont les bits correspondants ne sont toujours pas définis sont les sommets source. Vous pouvez le faire en temps linéaire dans la taille du graphique - $O(|V| + |E|)$ .
Les deux listes ensemble : Pour chaque sommet, il existe une liste mixte de sommets qui ont une arête vers ou depuis ce sommet, avec un autre attribut indiquant lequel des deux est réellement le cas. L'approche est similaire à 2 ci-dessus, avec l'ajout que tout bord entrant exclut immédiatement le sommet actuel (et vous pouvez marquer son ensemble de bits). Contrairement au point 2 où vous devez parcourir tous les sommets, ici, vous pourriez trouver une source plus tôt. Si vous ne vous arrêtez pas, vous aurez toutes les sources. Dans les deux cas, le temps est à nouveau linéaire dans la taille du graphique - $O(|V| + |E|)$ .
Les deux listes séparément : choisissez simplement la liste des bords entrants et suivez 1.

En remarque, si le choix de la structure de données est entre vos mains, vous voudrez peut-être analyser quelles sont toutes les opérations que vous avez l'intention d'effectuer, et à quelle fréquence, et choisir une structure de données appropriée.

Edit: pour le cas 1, si vous avez un dag où le nombre de sources est très petit par rapport à $|V|$ (par exemple, dans un arbre avec une seule source), et où la distance moyenne d'un sommet à une source est petite par rapport à $|V|$ et si vous ne voulez qu'une seule source, vous pouvez utiliser un algorithme plus rapide en moyenne (bien que la pire complexité asymptotique soit la même). Sélectionnez n'importe quel sommet au hasard et accédez à l'un de ses parents (dans la liste des arêtes entrantes), puis à son parent et ainsi de suite, jusqu'à ce que vous atteigniez un nœud qui n'a pas de parent - une source. Ce petit gain d'efficacité concerne des types de graphes très limités avec un algorithme légèrement plus complexe.

Paresh
la source

Pour les listes de bords entrants, au cas où vous n'auriez besoin que de trouver une seule source, ne serait-il pas plus rapide de simplement suivre un bord arbitraire pour obtenir le prédécesseur, jusqu'à ce que vous atteigniez une source? Surtout si le graphique est plat, c'est-à-dire que la distance moyenne à chaque source de chaque sommet est beaucoup plus petite que

| V |

$|V|$ .

Simon S

@SimonS Même si la pire complexité est la même (par exemple, une chaîne linéaire), vous pouvez la rendre plus rapide si le graphique a très peu de sources (par rapport à

| V |

$|V|$ ) et la distance moyenne d'un sommet à une source est très petite - par exemple. un graphique en étoile avec le centre comme source. Seule la condition que vous mentionnez n'est pas suffisante - par exemple 1-> 2, 1-> 3, 4-> 2, 4-> 3 - (vous pouvez avoir un graphique avec une distance moyenne de 0,5 et des sources | V | / 2) la distance moyenne est petite, mais les deux algorithmes donneront un temps prévu identique / similaire. Je vais cependant l'ajouter à ma réponse.

Paresh

Merci pour votre réponse! Je pense que ce que je veux dire est le deuxième cas, la liste sortante. BTW, pourquoi c'est O (| V | + | E |)? Je sais | E |, parce que vous devez balayer tous les bords, mais où le | V | de? Je vous remercie!

breezeintopl

@breezeintopl C'est un moyen de représentation. Vous vérifiez chaque arête une fois et chaque sommet aussi un nombre constant de fois. À tout le moins, à la fin, vous devez balayer tous les sommets une fois pour voir quels bits ne sont pas définis. Une autre façon de voir les choses est qu’une liste de contiguïté utilise

Θ (| V | + | E |)

$\Theta(|V| + |E|)$ espace - stocke un sommet et sa liste d'arêtes. Et vous parcourez toute la liste. Bien sûr, depuis

| E |

$|E|$ peut aller de

O (| V |)

$O(|V|)$ à

O (| V |^{2})

$O(|V|^2)$ , vous pouvez simplement sauter

| V |

$|V|$ partie. Voir un exemple pour BFS .

Paresh

Prenons une question plus simple. Supposons que vous savez que votre graphique est un arbre. Ensuite, vous pouvez trouver le nœud source en temps linéaire. Sélectionnez simplement un nœud aléatoire, si c'est la racine, alors vous avez votre réponse, sinon ce devrait être un enfant ou un parent, puis revenez en arrière jusqu'à ce que vous atteigniez la racine. Cela peut être fait en $O(|V|-1)$ .

Reza
la source

Si votre structure de données n'inclut pas de liste des bords entrants pour un nœud, alors la recherche du parent prend déjà O (m) (dans les arbres, donc le temps O (n). Puisque le chemin vers la racine de l'arbre peut être linéaire long, ce n'est qu'une solution quadratique. Mais si vous avez des contours, alors trouver un nœud avec 0 dans les contours est trivial.

adrianN

-1

En supposant que vous avez un graphique G = (V, E) donné au format de liste d'adjacence. (pour être clair ici, la liste contient tous les bords sortants de la source). Vous pouvez construire l'inverse du graphe G en temps linéaire. Ensuite, vous pouvez parcourir le graphique inverse et collecter tous les sommets qui ont une liste d'adjacence vide. Ces sommets n'ont pas de bord sortant dans le graphique inverse, ce qui signifie qu'ils n'ont pas de bord entrant dans le graphique d'origine, ce sont donc vos sommets source.

Le temps de course est linéaire. La construction de l'inverse du graphique prend un maximum de temps O (| V | + | E |). Itérer sur l'inverse du graphe prend O (| V |) temps.

MGB
la source

Honnêtement, le calcul de l'inverse du graphique semble être un problème plus difficile que de trouver les sources. Je doute que quelqu'un qui ne sait pas comment obtenir les sources puisse trouver comment inverser tous les bords.

David Richerby

@DavidRicherby vous avez dit que le calcul de l'inverse du graphique est plus difficile. Comment définissez-vous plus difficile? Si c'est la complexité temporelle, cela peut être fait en temps linéaire. vous pouvez rechercher la solution ici [lien] ( stackoverflow.com/questions/40378152/… ). La question concerne une solution temporelle linéaire qui trouve la source d'un graphique et ma solution proposée le fait. Si vous pensez que ce n'est pas le cas, pouvez-vous être précis et me dire comment mon algorithme ne satisfait pas à l'exigence de temps linéaire?

MGB

Je veux dire conceptuellement plus difficile. Vous dites que, pour résoudre cet exercice, le demandeur a juste besoin de résoudre un autre exercice, mais cet autre exercice semble plus difficile que le premier.

David Richerby