Ich habe ein Problem, wo ich das Minimum finden sollmögliche Tiefe eines Graphen, was bedeutet, dass ich die maximale Tiefe von jedem Knoten finden muss und die kleinste von allen zurückgeben muss. Offensichtlich wird ein einfaches DFS von jedem Knoten den Trick machen, aber wenn die Dinge mit extrem großen Eingaben verrückt werden, wird DFS ineffizient (Zeitlimit). Ich habe versucht, die Entfernung jedes Blattes zu dem Knoten zu halten, der in Erinnerung ist, aber das half nicht viel.
Wie finde ich effizient die minimale Tiefe eines sehr großen Graphen? Es ist bemerkenswert, dass der Graph in Frage hat kein Zyklus.
Antworten:
9 für die Antwort № 1Um das Graphzentrum / Zentrum eines ungerichteten Baumdiagramms zu finden, könnten Sie:
- Führen Sie ein DFS durch, um eine Liste aller Blattknoten zu finden. O (n)
- Entfernen Sie alle diese Blattknoten aus dem Diagramm und notieren Sie beim Löschen, welche neuen Knoten Blattknoten werden
- Wiederholen Sie Schritt 2, bis das Diagramm vollständig gelöscht ist
Die Knoten / Knoten, die in der letzten Stufe des Algorithmus gelöscht wurden, sind die Graphenzentren Ihres Baumes.
Jeder Knoten wird einmal gelöscht, sodass dieser gesamte Prozess in O (n) durchgeführt werden kann.
0 für die Antwort № 2
Was Sie suchen, ist das Durchmesser / 2. Sie könnten den Durchmesser eines Baumes wie folgt berechnen und es als bezeichnen findDiameter(n, null), für einen beliebigen Knoten n des Baumes.
public findDiameter(node n, node from) returns <depth, diameter>
// apply recursively on all children
foreach child in (neighbors(n) minus from) do
<de, di> = findDiameter(child, n)
// depth of this node is 1 more than max depth of children
depth = 1 + max(de)
// max diameter either uses this node, then it is 1 + the 2 largest depths
// or it does not use this node, then it"s the max depth of the neighbors
diameter = max(max(di), 1 + max(de) + oneButLargest(de))
Alles, was Sie tun müssen, ist in der Schleife über die Nachbarn verfolgen den größten Durchmesser und die 2 größten Tiefen.