特定のルートリストに接続されている都市の最大数を見つける必要があるプログラムを解決しようとしています。
例：指定されたルートが[['1', '2'], ['2', '4'], ['1', '11'], ['4', '11']]
接続されている最大都市の場合、4
すでに訪れた都市を訪れることができないという制約があります。
どのように進歩するかなど、アイデアが必要です。
今のところ、私が考えているのは、都市をキーとして、その値として接続されている他の都市の数を含む辞書を作成できれば、解決策に近づくことができるということです (願っています)。例：私の辞書は{'1': ['2', '11'], '4': ['11'], '2': ['4']}
上記の入力用です。先に進むための支援と、何か不足している場合のガイダンスが必要です。
を使用しdefaultdictて、エッジ/パスのリストから「グラフ」を作成できます。
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()
出力：
[
('1', ['2', '11']),
('11', ['1', '4']),
('2', ['1', '4']),
('4', ['2', '11'])
]
無向グラフを使用しているため、両方向にエッジを追加したことに注意してください。したがって、エッジ (a,b) では、G[a]が含まれb、G[b]含まれますa。
これから、深さ優先検索や幅優先検索などのアルゴリズムを使用して、グラフ内のすべてのパスを検出できます。
次のコードでは、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
あなたが使用できるもの：
G = defaultdict(list)
for (s,t) in edges:
G[s].append(t)
G[t].append(s)
print DFS(G, '1')
出力：
[('1', '2'), ('1', '2', '4'), ('1', '2', '4', '11'), ('1', '11 '), ('1', '11', '4'), ('1', '11', '4', '2')]
したがって、最長パスを示す最後のビットを含む完全なコードは次のとおりです。
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)
出力：
すべてのパス:
[('1', '2'), ('1', '2', '4'), ('1', '2', '4', '11'), ('1', '11 '), ('1', '11', '4'), ('1', '11', '4', '2')]
最長パス:
('1'、'2'、'4'、'11')
('1'、'11'、'4'、'2')
最長パスの長さ:
4
検索の「開始点」は、DFS関数の 2 番目の引数によって指定されることに注意してください。この場合は'1'.
更新: コメントで説明したように、上記のコードは、開始点を念頭に置いていることを前提としています (具体的には、コードは というラベルの付いたノードを使用します'1')。
そのような開始点がない場合のより一般的な方法は、すべてのノードから開始して検索を実行し、全体で最も長くかかることです。（注：実際には、これよりも賢いかもしれません）
ラインの変更
all_paths = DFS(G, '1')
に
all_paths = [p for ps in [DFS(G, n) for n in set(G)] for p in ps]
任意の 2 点間の最長パスが得られます。
(これはばかげたリスト内包表記ですが、更新できるのは 1 行だけです。より明確に言えば、次のようになります。
all_paths = []
for node in set(G.keys()):
for path in DFS(G, node):
all_paths.append(path)
また
from itertools import chain
all_paths = list(chain.from_iterable(DFS(G, n) for n in set(G)))
）。
例の入力に対して機能するコードを次に示しますが、入力を少し調整すると、接続されている都市の数が正しくなりません。
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
#had to do this for the key error that i was getting if the start doesn't
#have any val.
if isinstance(start,str) and start not in graph.keys():
pass
else:
for next in set(graph[start]) - visited:
dfs(graph, next, visited)
return visited
def maxno_city(input1):
totalcities = []
max_nocity = 0
routedic = {}
#dup = []
rou = []
for cities in input1:
cities = cities.split('#')
totalcities.append(cities)
print (totalcities)
for i in totalcities:
if i[0] in routedic.keys():
routedic[i[0]].append(i[1])
else:
routedic.update({i[0]:[i[1]]})
print(routedic)
keys = routedic.keys()
newkeys = []
for i in keys:
newkeys.append(i)
print (newkeys)
newkeys.sort()
print (newkeys)
expath = dfs(routedic,newkeys[0])
return(len(expath))
上記の入力の出力は次のとおりです4が4、入力が次のように変更された場合:
['1#2','2#3','1#11','3#11','4#11','4#5','5#6','5#7','6#7','4#12','8#12','9#12','8#10','9#10',8#9]
私のコードは失敗します。
ありがとう、LearningNinja :D