http://homepage.cs.uiowa.edu/~hzhang/c31/ch09-probs.pdfIch arbeite an einem DFS eines gerichteten Graphen, Wie komme ich zu einem Knoten ohne irgendwelche Kanten darauf hingewiesen?
Das Problem ist 9.2 in der PDF oben. Ich bin verwirrt, wie ich zu Knoten E komme, weil er nur Kanten hat, die vom Knoten weg zeigen; Keine sind auf Knoten E gezeigt. Ich schätze die Hilfe.
Wenn Sie alle Knoten nach DFS durchsuchen möchten, müssen Sie für jeden Knoten iterieren und prüfen, ob auf den Knoten zugegriffen wird oder nicht, und den Knoten zum Starten eines DFS verwenden.
procedure DFS(G,v):
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
if vertex w is not labeled as discovered then
recursively call DFS(G,w)
procedure traverse_by_DFS(G):
for v in G:
if v is dicovered:
continue
DFS(G, v)
Es ist eine Trickfrage. Sie treffen Knoten E nicht, weil Sie gezwungen sind, bei Knoten A zu beginnen. Dies ist der Effekt, der einem Startknoten gegeben wird, der nicht der wahre Wurzel ist - das Ergebnis ist eine unvollständige Durchquerung.
Also, meine Baumkanten würden gehen a> b> f> d> c, dann würde ich einen rekursiven Aufruf an DFS (G, e) machen, um meine letzte Baumkante von e> a zu bekommen? Nach meinem ersten Aufruf von DFS habe ich jeden Eckpunkt außer e gefunden. –
@KyleDenHartog Wenn Sie alle Knoten in einer Woche mit verbundenen Graphen durchlaufen möchten, müssen Sie alle Knoten durchlaufen und überprüfen, ob zugegriffen wird oder nicht. Es gibt eine Referenz, https://www.csd.uoc.gr/~hy583/reviewed_notes/dfs_dags.pdf –
@KyleDenHartog DFS kann verwendet werden, um zu überprüfen, ob der Graph ein stark verbundener Graph ist oder nicht. Genau wie in Ihrem Beispiel hat der Knoten e keine In-Kante, wenn Sie von anderen Knoten aus starten, wird er in einem DFS nicht immer auf den Knoten e zugreifen. –