Suche nach längster Pfad in einem Graphen

Können Sie eine defaultdict, erstellen Sie Ihre "Grafik" aus der Liste der Kanten/Wege:

edges = [['1', '2'], ['2', '4'], ['1', '11'], ['4', '11']]

G = defaultdict(list)
for (s,t) in edges:
    G[s].append(t)
    G[t].append(s)

print G.items()

Ausgabe:

[ 
('1', ['2', '11']), 
('11', ['1', '4']), 
('2', ['1', '4']), 
('4', ['2', '11']) 
] 

Hinweis, dass ich die Kanten in beiden Richtungen, da Sie arbeiten mit einem ungerichteten Graphen. Also mit der Kante (a,b) G[a] gehören b und G[b] gehören a.

Können Sie verwenden einen Algorithmus, wie Tiefe-zuerst-Suche oder Breite-zuerst-Suche zu entdecken, alle Pfade im Graphen.

In der folgende code, die ich verwendet, DFS:

def DFS(G,v,seen=None,path=None):
    if seen is None: seen = []
    if path is None: path = [v]

    seen.append(v)

    paths = []
    for t in G[v]:
        if t not in seen:
            t_path = path + [t]
            paths.append(tuple(t_path))
            paths.extend(DFS(G, t, seen[:], t_path))
    return paths

Die Sie verwenden können, mit:

G = defaultdict(list)
for (s,t) in edges:
    G[s].append(t)
    G[t].append(s)

print DFS(G, '1')

Ausgabe:

[('1', '2'), ('1', '2', '4'), ('1', '2', '4', '11'), ('1', '11'), ('1', '11', '4'), ('1', '11', '4', '2')] 

So ist der vollständige code, der mit dem letzten bit, die zeigt, dass der längste Pfad:

from collections import defaultdict

def DFS(G,v,seen=None,path=None):
    if seen is None: seen = []
    if path is None: path = [v]

    seen.append(v)

    paths = []
    for t in G[v]:
        if t not in seen:
            t_path = path + [t]
            paths.append(tuple(t_path))
            paths.extend(DFS(G, t, seen[:], t_path))
    return paths


# Define graph by edges
edges = [['1', '2'], ['2', '4'], ['1', '11'], ['4', '11']]

# Build graph dictionary
G = defaultdict(list)
for (s,t) in edges:
    G[s].append(t)
    G[t].append(s)

# Run DFS, compute metrics
all_paths = DFS(G, '1')
max_len   = max(len(p) for p in all_paths)
max_paths = [p for p in all_paths if len(p) == max_len]

# Output
print("All Paths:")
print(all_paths)
print("Longest Paths:")
for p in max_paths: print("  ", p)
print("Longest Path Length:")
print(max_len)

Ausgabe:

Alle Pfade: 
[('1', '2'), ('1', '2', '4'), ('1', '2', '4', '11'), ('1', '11'), ('1', '11', '4'), ('1', '11', '4', '2')] 
Längste Wege: 
('1', '2', '4', '11') 
('1', '11', '4', '2') 
Längste Pfadlänge: 
4 

Hinweis, der "Ausgangspunkt" der Suche angegeben wird, indem Sie das zweite argument der DFS Funktion, in diesem Fall, es ist '1'.

Update: Wie bereits in den Kommentaren der obige code setzt Voraus, Sie haben einen Ausgangspunkt in mind (speziell der code verwendet die Knoten beschriftet '1').

Einer allgemeineren Methode, in dem Fall, dass Sie keine solchen Ausgangspunkt wäre, um die Suche durchzuführen, beginnend bei jeder Knoten, und nehmen Sie die insgesamt längste.
(Anmerkung: In Wirklichkeit, Sie könnte schlauer sein als diese)

Ändern der Zeile

all_paths = DFS(G, '1')

zu

all_paths = [p for ps in [DFS(G, n) for n in set(G)] for p in ps]

geben würde, Sie den längsten Pfad zwischen alle zwei Punkte.

(Das ist eine dumme Liste zu begreifen, aber es erlaubt mir, zu aktualisieren nur eine einzige Linie. Mehr klar, es ist äquivalent zu den folgenden:

all_paths = []
for node in set(G.keys()):
    for path in DFS(G, node):
        all_paths.append(path)

oder

from itertools import chain
all_paths = list(chain.from_iterable(DFS(G, n) for n in set(G)))

).