13

こんにちは、隣接リストと行列の概念は理解していますが、Python でそれらを実装する方法について混乱しています。

次の 2 つの例を達成するためのアルゴリズムは達成されますが、例でハードコーディングされているため、最初から入力を知る必要はありません。

隣接リストの場合:

    a, b, c, d, e, f, g, h = range(8) 
    N = [ 
     {b:2, c:1, d:3, e:9, f:4},    # a 
     {c:4, e:3},                   # b 
     {d:8},                        # c 
     {e:7},                        # d 
     {f:5},                        # e 
     {c:2, g:2, h:2},              # f 
     {f:1, h:6},                   # g 
     {f:9, g:8}                    # h 
   ]

隣接行列の場合:

    a, b, c, d, e, f, g, h = range(8) 
    _ = float('inf') 
    #     a b c d e f g h
    W = [[0,2,1,3,9,4,_,_], # a 
        [_,0,4,_,3,_,_,_], # b 
        [_,_,0,8,_,_,_,_], # c 
        [_,_,_,0,7,_,_,_], # d 
        [_,_,_,_,0,5,_,_], # e 
        [_,_,2,_,_,0,2,2], # f 
        [_,_,_,_,_,1,0,6], # g 
        [_,_,_,_,_,9,8,0]] # h

繰り返しますが、どんな助けでも大歓迎です、ありがとう!

4

3 に答える 3

7

仮定:

edges = [('a', 'b'), ('a', 'b'), ('a', 'c')]

マトリックスのコードは次のとおりです。

from collections import defaultdict

matrix = defaultdict(int)
for edge in edges:
    matrix[edge] += 1

print matrix['a', 'b']

2

そして「リスト」の場合：

from collections import defaultdict

adj_list = defaultdict(lambda: defaultdict(lambda: 0))
for start, end in edges:
    adj_list[start][end] += 1

print adj_list['a']

{'c': 1, 'b': 2}
于 2012-11-25T00:52:58.283 に答える
2

データ構造の設定は非常に簡単です。たとえば、隣接リストの例は、次のdefaultdictようなを使用して実装できます。

from collections import defaultdict

N = defaultdict(dict)

次に、入力を取得し始めたら、N[start][end] = weight入力されたエッジごとに実行します。アウトバウンド エッジのないノードがいくつかある場合、ノードのセットを取得するのは少し難しくなります (すべてを確実に取得するには、内側の辞書のキーと外側の辞書のキーを結合する必要があります)。しかし、完全なノード リストがなくても、多くのアルゴリズムは正しく機能します。

隣接行列は、次元を正しく設定するためにノードの数を知る必要があるため、もう少し複雑です。事前に知っていれば、簡単です。

number_of_nodes = 8
_ = float("inf")

N = [[_]*number_of_nodes for i in number_of_nodes]

そうでない場合は、入力として取得したエッジをスキャンして最大番号のノードを見つけ、上記と同じコードを使用して行列を作成することをお勧めします。たとえば、エッジが(start, end, weight)3 タプルのリストとして提供されている場合は、次のように使用できます。

number_of_nodes = max(max(start, end) for start, end, weight in edges)
于 2012-11-25T00:57:16.320 に答える
0

以下の例が、初期化されたグラフとユーザーがカスタマイズしたグラフの両方を持っているのに役立つことを願っています

class Graph:
"""
  Read the Intialized Graph and Create a Adjacency list out of it 
   There could be cases where in the initialized graph <map> link
  issues are not maintained
   for example node 2 to 1 link 
    2->1
   there needs to be a link then since undirected Graph
    1->2
"""

def __init__(self,Graph_init):
    self.edge={}
    for keys,values in Graph_init.items():
         for value in values:
             self.addEdge(keys,value);

"""
Add a vertex to graph map
structure is
int => int list
"""
def addVertex(self,v):
    if v not in self.edge:
        self.edge[v]=[]
"""
Add Edge from both vertex to each other
Make sure the nodes are present

"""
def addEdge(self,u,v): u が self.edge にない場合: self.addVertex(u) v が self.edge にない場合: self.addVertex(v) u が self.edge[v にない場合]: self.edge[v].append(u) v が self.edge[u] にない場合: self.edge[u].append(v)

def isEdge(self,u,v):
    if u not in self.edge:
        return False
    if v not in self.edge:
        return False 
    return  u in self.edge[v] 

def display(self):
    for keys,values in self.edge.items():
        print(keys,":=>",values)

"""A initalized Graph (not in form of adjaceny list"""
Graph_init = {1:[2,3,5],
          2:[1,4],
          3:[1,6]};

"""Default constrcutor takes care of making the initialzed map to adjaceny 
list"""                 
g=Graph(Graph_init)
g.addVertex(1)
g.addVertex(2) 
g.addVertex(3)
g.addEdge(1,2)
g.addEdge(3,2)
g.display();
于 2017-06-27T18:43:32.840 に答える