辞書にアイテム間の関係をトレース

Question

私は例えば、関係のセットを定義した辞書を持っている：

relationships = {"Fred": ["Mary, John"], 
       "Mary": ["Fred", "Alex"], 
       "John": ["Fred"] 
       "Alex": ["Mary"]} 

私は名前を与えられた私は、すべてのリストを返し、いくつかの機能を構築したいと思いますその名前に関連付けられた関係。

直接関係はKey：Valueのペアで通知されます（MaryはFredと直接関係しているため）。第2レベルの関係は「友人の友人」タイプの関係を通じて通知されます。だからアレックスとフレッドはメアリーを通して関係を持っています。アレックス - >メアリー - >フレッド。例えば

： 入力：フレッド、 出力：メアリー、ジョン、アレックス

入力：アレックス、 出力：メアリー、フレッド、ジョン

私は学ぶしようとするために、この例を使用しています再帰を念頭に置いて再帰的な解法がありますが、これを繰り返し実行できるかどうか、またはこれを解決するための適切な再帰を構築する方法が不明です。

Answer 1

問題の一般的な解決策として、グラフ検索を試すことができます。次に、それぞれの接続されたコンポーネントは、直接または他の人を介してお互いを知っている人の集合を表します。あなたのケースでは

、グラフは次のようになります。

したがって、クエリで指定された人物から開始し、すべての子孫の頂点を訪れます。

Answer 2

あなたはすべての関係を見つけるためにdictをレベルで検索できます。

relationships = {"Fred": ["Mary", "John"], 
       "Mary": ["Fred", "Alex"], 
       "John": ["Fred"] 
       "Alex": ["Mary"]} 

def findRelation(name): 
    res = relationships.get(name) 
    next = set(res) 
    visited = set() 
    while next: 
     current = [] 
     for friend in next: 
      if friend in visited: continue 
      visited.add(friend) 
      item = relationships.get(friend) 
      if item: 
       res.extend(item) 
       current.extend(item) 
     next = set(current) 
    return set(res)- set([name]) 


findRelation('Fred') 
set(['John', 'Alex', 'Mary']) 

findRelation('Alex') 
set(['John', 'Mary', 'Fred'])