Longest Path（トポロジカルソート）

トポロジカルソート

トポロジカルソート は、グラフ理論において、有向非巡回グラフの各ノードを順序付けして、どのノードもその出力辺の先のノードより前にくるように並べることです。

有向非巡回グラフは必ず トポロジカルソート することができます。

タスク間に依存関係がある場合、どんな順番でタスクをこなせば良いかを決めるのに役立つアルゴリズムです。

問題

頂点数がＮ、辺の数がＭの有向グラフ G があります。 

頂点には 1,2,…,N と番号が振られています。 

各 i (1 ≦ i ≦ M) について、i 番目の有向辺は頂点 x_i から y_i へ張られています。

G は有向閉路を含みません。

G の有向パスのうち、最長のものの長さを求めてください。 

（有向パスの長さとは、有向パスに含まれる辺の本数のことです。）

解法・ソースコード

この問題は、頂点を トポロジカルソート で並べ替えて、その順番に有向パスでの通過数をカウントすることで解くことができます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#--------- 入力例1 ----------
# ノードの数
n = 4
# 全エッジ（ x → y ）
lst = [(1, 2),
       (1, 3),
       (3, 2),
       (2, 4),
       (3, 4)]
#--------- 入力例2 ----------
# # ノードの数
# n = 6
# # 全エッジ（ x → y ）
# lst = [(2, 3),
#        (4, 5),
#        (5, 6)]
#--------- 入力例3 ----------
# # ノードの数
# n = 5
# # 全エッジ（ x → y ）
# lst = [(5, 3),
#        (2, 3),
#        (2, 4),
#        (5, 2),
#        (5, 1),
#        (1, 4),
#        (4, 3),
#        (1, 3)]
#----------------------------
from collections import defaultdict 

# トポロジーソートを行うクラス
class Graph: 
    def __init__(self,vertices): 
        self.graph = defaultdict(list) 
        self.V = vertices
  
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
  
    def topologicalSortUtil(self, v, visited,stack): 
        visited[v] = True
        for i in self.graph[v]: 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        stack.insert(0,v) 
  
    def topologicalSort(self): 
        visited = [False]*self.V 
        stack =[] 
  
        for i in range(self.V): 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
        return stack

g = Graph(n + 1)    # 0スタートなので頂点を１つ多めに
for a, b in lst:
    g.addEdge(a, b)     # 有向パス追加

print ("トポロジカルソートの結果：", g.topologicalSort())

# トポロジカルソート順に通過数をカウント
memo = {}   # カウント（キー：頂点番号、バリュー：通過数）
for x in list(g.topologicalSort()):
    for a, b in lst:
        if x == a:
            memo[b] = memo.get(a, 0) + 1

print('解：', max(memo.values()))

[実行結果(入力例1)]

トポロジカルソートの結果： [1, 3, 2, 4, 0]

解： 3

1→3→2→4 の有向パスが最長になります。

[実行結果(入力例2)]

トポロジカルソートの結果： [4, 5, 6, 2, 3, 1, 0]

解： 2

4→5→6 の有向パスが最長になります。

[実行結果(入力例3)]

トポロジカルソートの結果： [5, 2, 1, 4, 3, 0]

解： 3

5→2→4→3、5→1→4→3 の有向パスが最長になります。