在Python中使用字符創建鄰接列表

Question

我習慣於使用字典來表示python中的圖表，但是我遇到了大圖和複雜計算的一些嚴重的性能問題，所以我認爲我應該交叉使用鄰接矩陣來繞過散列表的開銷。我的問題是，如果我有一個形式爲g的圖：{node：{vertex：weight。 。 。 }。 。 。 }，將其轉換爲基於列表的鄰接矩陣的最有效方法是什麼？

Answer 1

可能不是最有效的，但一個簡單的方法來你的格式轉換爲一個列表的基礎上的鄰接矩陣看起來是這樣的：

g = {1:{2:.5, 3:.2}, 2:{4:.7}, 4:{5:.6, 3:.3}} 
hubs = g.items() # list of nodes and outgoing vertices 
size=max(map(lambda hub: max(hub[0], max(hub[1].keys())), hubs))+1 # matrix dimension is highest known node index + 1 
matrix=[[None]*size for row in range(size)] # set up a matrix of the appropriate size 

for node, vertices in hubs: # loop through every node in dictionary 
    for vertice, weight in vertices.items(): # loop through vertices 
     matrix[vertice][node] = weight # define adjacency of both nodes by assigning the vertice's weight 

這適用於向圖假定節點代表只需通過從零開始的索引。這裏是一個可視化和在此示例中處理的圖形生成的矩陣：

 0 1 2 3 4 5 
    ------------------------------ 
0 |        
1 |        
2 |  0.5      
3 |  0.2   0.3  
4 |   0.7     
5 |      0.6  

如果你的圖其實是在指導，我能想到的一些機會來優化的。如果字典containes每個節點與它的上市，就像{1:{2:.2, 3:.3}, 2:{1:.2}, 3:{1:.3}}頂點的關鍵，你可以穿越之前排序相應的列表，並限制了內部循環：通過使用binary search

hubs = sorted(g.items()) 
for node, vertices in hubs: 
    for vertice, weight in reversed(sorted(vertices.items())): 
     if vertice >= node: 
      matrix[vertice][node] = weight 
      matrix[node][vertice] = weight 
     else: # do only care about vertices that haven't been saved before, 
      break # continue with next node when the current one won't introduce any more vertices 

你或許可以有這樣的更加高效。由於產生的矩陣顯然是鏡像對稱的，所以你可以走得更遠，只存儲它的一半。要做到這一點最簡單的方法也許是翻轉它在垂直軸上：

# unlike the one before, this sample doesn't rely on the dictionary containing every vertice twice 
matrix=[[None]*size for row in range(size)] 
for node, vertices in hubs: 
    for vertice, weight in vertices.items(): 
     matrix[vertice][size-node-1] = weight 

由於矩陣的一半被切斷，不是每一個查找的節點之間的頂點(u,v)會工作，所以它必須是確保列的索引大於要查找的單元格的行：

u,v = sorted((u,v)) 
weight = matrix[v][u] 

祝你好運！

Answer 2

那麼要在鄰接列表中實現，您可以創建兩個類，一個用於存儲關於頂點的信息。

# Vertex, which will represent each vertex in the graph.Each Vertex uses a dictionary 
# to keep track of the vertices to which it is connected, and the weight of each edge. 
class Vertex: 

# Initialze a object of this class 
# we use double underscore 
def __init__(self, key): 
    # we identify the vertex with its key 
    self.id = key 
    # this stores the info about the various connections any object 
    # (vertex) of this class has using a dictionary which is called connectedTo. 
    # initially its not connected to any other node so, 
    self.connectedTo={} 

# Add the information about connection between vertexes into the dictionary connectedTo 
def addNeighbor(self,neighbor,weight=0): 
    # neighbor is another vertex we update the connectedTo dictionary (Vertex:weight) 
    # with the information of this new Edge, the key is the vertex and 
    # the edge's weight is its value. This is the new element in the dictionary 
    self.connectedTo[neighbor] = weight 

# Return a string containing a nicely printable representation of an object. 
def __str__(self): 
    return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo]) 

# Return the vertex's self is connected to in a List 
def getConnections(self): 
    return self.connectedTo.keys() 

# Return the id with which we identify the vertex, its name you could say 
def getId(self): 
    return self.id 

# Return the value (weight) of the edge (or arc) between self and nbr (two vertices) 
def getWeight(self,nbr): 
    return self.connectedTo[nbr] 

正如您從註釋中看到，每個頂點存儲有用於識別它， 一個「關鍵」，它有一本字典「connectedTo」，這是關鍵，重量對所有連接的從這個頂點。連接頂點的關鍵和邊緣的權重。

現在，我們可以存儲這樣的頂點的使用可以這樣來實現圖形類的集合，

# The Graph class contains a dictionary that maps vertex keys to vertex objects (vertlist) and a count of the number of vertices in the graph 
class Graph: 

def __init__(self): 
    self.vertList = {} 
    self.numVertices = 0 


# Returns a vertex which was added to the graph with given key 
def addVertex(self,key): 
    self.numVertices = self.numVertices + 1 
    # create a vertex object 
    newVertex = Vertex(key) 
    # set its key 
    self.vertList[key] = newVertex 
    return newVertex 

# Return the vertex object corresponding to the key - n 
def getVertex(self,n): 
    if n in self.vertList: 
     return self.vertList[n] 
    else: 
     return None 

# Returns boolean - checks if graph contains a vertex with key n 
def __contains__(self,n): 
    return n in self.vertList 

# Add's an edge to the graph using addNeighbor method of Vertex 
def addEdge(self,f,t,cost=0): 
    # check if the 2 vertices involved in this edge exists inside 
    # the graph if not they are added to the graph 
    # nv is the Vertex object which is part of the graph 
    # and has key of 'f' and 't' respectively, cost is the edge weight 
    if f not in self.vertList: 
     nv = self.addVertex(f) 
    if t not in self.vertList: 
     nv = self.addVertex(t) 
    # self.vertList[f] gets the vertex with f as key, we call this Vertex 
    # object's addNeighbor with both the weight and self.vertList[t] (the vertice with t as key) 
    self.vertList[f].addNeighbor(self.vertList[t], cost) 

# Return the list of all key's corresponding to the vertex's in the graph 
def getVertices(self): 
    return self.vertList.keys() 

# Returns an iterator object, which contains all the Vertex's 
def __iter__(self): 
    return iter(self.vertList.values()) 

在這裏，我們有持有「numVertices」頂點的數量，有圖類 字典'vertList'，其中有關鍵字和頂點（我們剛製作的類）對象出現在 圖中。 我們可以創建一個圖，如果你想無向圖，然後加入這一行the_graph.addEdge(node2_key,node1_key,cost) 這樣的連接將不被存儲爲一個連接到B，而連接到B和B連接通過調用

# Now lets make the graph 
the_graph=Graph() 

print "enter the number of nodes in the graph" 
no_nodes=int(raw_input()) 

# setup the nodes 
for i in range(no_nodes): 
     print "enter the "+str(i+1)+" Node's key" 
     the_graph.addVertex(raw_input()) 

print "enter the number of edges in the graph" 
no_edges=int(raw_input()) 
print "enter the maximum weight possible for any of edges in the graph" 
max_weight=int(raw_input()) 


# setup the edges 
for i in range(no_edges): 
    print "For the "+str(i+1)+" Edge, " 
    print "of the 2 nodes involved in this edge \nenter the first Node's key" 
    node1_key=raw_input() 
    print "\nenter the second Node's key" 
    node2_key=raw_input() 
    print "\nenter the cost (or weight) of this edge (or arc) - an integer" 
    cost=int(raw_input()) 
    # add the edge with this info 
    the_graph.addEdge(node1_key,node2_key,cost) 

設置它到一個。 還要注意上面兩個類實現的縮進，它可能是不正確的。