Finden Sie den einfachen Pfad mit mindestens 5 Kanten in gerichteten Graphen

Question

Ich habe eine Frage. Gegeben ist ein gerichteter Graph (G = V, E) und der Quellknoten s aus der V-Gruppe. Wir wollen überprüfen, ob es einen einfachen Pfad (keine Kreise) von s zu irgendeinem Knoten in G mit mindestens 5 Kanten gibt. Bieten Sie so effizient wie möglich einen Algorithmus an, der das Problem für ein Diagramm G löst, das Kreise enthalten kann.

bitte ich brauche deine Hilfe

Dank :-)

Answer 1

Wir brauchen jede 5-edge einfach gerichteten Weg an Vertex s beginnen zu finden. Dieser Pfad wird wie folgt aussehen:

s -> a -> b -> c -> d -> e (all distinct) 

Nun wollen wir die alle möglichen Werte von c durch (jede Vertex neben s) und dann für jeden c Wert, den wir durch alle Kanten gehen können, die nicht s und c Eckpunkte enthalten und für den Rand (x, y) wie folgt vor:

if edge (s, x) exists and edge (y, c) exists 
    put (x, y) in AB edges list 
if edge (c, x) exists 
    put (x, y) in DE edges list 

Dies kann in O(|E|) erfolgen. Dann müssen wir ein Paar Kanten (E1, E2) so finden, dass E1 in AB ist, E2 in 10 ist und sie keinen gemeinsamen Scheitelpunkt teilen. Letzteres kann in O(|E|) erfolgen.

Wir können ein Diagramm G' = (V, DE) nehmen und die Grade der Scheitelpunkte finden. Dann gilt für jede Kante (a, b) von AB brauchen wir, dass

degree(a) + degree(b) = |DE| + x  

wo x = 1 überprüfen, ob (a, b) ist in DE, sonst x = 0. Wenn diese Gleichheit nicht gilt, bedeutet das, dass es eine Kante in gibt, die weder a noch b enthält, und wir können einfach durch die gesamteRIteration gehen, um die Antwort zu finden. Die gesamte Komplexität wird O(|V||E|) mit O(|E|) zusätzlichen Speicher sein.