隣接リストの実装Python

Question

私はPython（および一般的なコンピュータ科学）の初心者ですので、私に同行してください。

Pythonで隣接リストを実装する際に問題があります。

with open("graph1.txt") as infile: 
    vertices = [] 
    for line in infile: 
     line = line.split() 
     line = [int(i) for i in line] 
     vertices.append(line) 


adj = dict() 

for edge in vertices: 
    x, y = int(edge[0]), int(edge[1]) 
    if x not in adj: adj[x] = set() 
    if y not in adj: adj[y] = set() 
    adj[x].add(y) 
    adj[y].add(x) 
print(adj) 

：私は辞書を通してそれを実装する方法を学びましたが、私はこれが私のコードであるだけで、基本的なリスト（リストのリスト）

を使用してそれを行う方法を知っておく必要があります（私はここを通じて笑方法を学びました）

何か助けていただければ幸いです。 乾杯します

Answer 1

あなたはまだ隣接する頂点のセットを持つ頂点のセットについて考えていますが、より洗練されたsetデータ構造ではなく、リストとしてセットを実装します。トップレベルのセットに素早く索引付けする必要があります。唯一の方法は、整数インデックスを使用することです。したがって、各頂点に（自然または任意の）整数kを割り当て、その頂点の隣接関係集合（リストとして実装）を最上位リストのスロットkに入れたいとします。通常、特定のものを選択するのではなく繰り返し処理するので、第2レベルのリストへの効率的なインデックス作成はあまり重要ではありませんが、Pythonには組み込みのリストがあり、それ？

verticesという変数がエッジを保持すべきではないという意見に同意します。世界の誰もが、あなたは混乱し、後であなたも混乱します。上記のトップレベルのリストにはverticesという名前を使用することをお勧めします。次に、第2レベルのリストは、最上位のインデックスverticesにインデックスを保持できます。 （まあ、あなたもエッジオブジェクトが必要かもしれません - あなたがこれを使っているのか分かりませんが、純粋主義者の隣接リスト表現にはエッジオブジェクトの余地がありません）。

Answer 2

それを持っていますが、とにかくここに隣接リストのための私のpythonの実装です。私はリストのリストを使用しました。 Pythonの2 コード：

class graph(object): 
    def __init__(self, n): 
     self.n=n 
     self.mat=[list() for i in range(n)] 

    def insert(self, u, v, w): 
     t=[v, w] 
     self.mat[u].append(t) 

    def printGraph(self): 
     i=0 
     for i in range(self.n): 
      print i, self.mat[i] 

    def deleteEdge(self, u, v): 
     weight=0 
     for x in self.mat[u]: 
      if x[0]==v: 
       weight=x[1] 
       break 
     self.mat[u].remove([v, weight]) 

g=graph(3) # 3 is the number of vertices 
g.insert(0, 1, 10) # 10 is the weight of the edge 
g.insert(0, 2, 12) 
g.insert(1, 2, 9) 

g.printGraph() 
g.deleteEdge(0, 1) 
g.printGraph()