如何用点数组和边数组创建邻接矩阵，Python

Question

我有一个图像，我收集了一些点，它们代表了图中顶点所在区域的质心。 我的点列表如下所示：

[(455, 472), (343, 472), (208, 471), (478, 456), (460, 441), (428, 439), 
 (413, 458), (48, 439), (107, 460), (130, 413), (179, 385), (250, 396), 
 (20, 373), (431, 381), (483, 355), (342, 390), (441, 343), (312, 344), 
 (283, 336), (259, 342), (409, 329),..............................]

现在我寻找一些边，并在代码中进行一些操作，生成这种类型的（p1，p2）列表，其中p1----p2是边：

[((343, 472), (342, 390)), ((343, 472), (312, 344)), 
 ((343, 472), (337, 302)), ((478, 456), (460, 441)),...................]

现在我想实现一些算法，比如Dijksra或BFS。 在其他SO问题和实现中，我注意到大多数图都表示为邻接矩阵。 我考虑了直接将边添加到哈希表或dictionary对象中，而不是像我那样添加边。问题是-我给顶点取什么名字？假设我有(343,472)，我不明白如何去做，变成这样的dict：{A : [p1,p2...], B: [p3,....], ... }

做这件事的好方法是什么？我添加了一个代码，显示了当前如何创建边表示：

def makeEdgesFromSpots(centroids, imageForEdges):
edges = []
for c1 in centroids:
    for c2 in centroids:
        if(c1[0] == c2[0] and c1[1] == c2[1]):
            continue
        else:
            //checkPointsForPath does some testing, 
           //  to check if I want these points as an edge.
            isLine = checkPointsForPath(c1,c2,imageForEdges)
            if isLine == True:
                edges.append((c1,c2))
return edges

Answer 1

如果图形未加权且没有多重边，则可以使用^{}和set值：

from collections import defaultdict
import pprint

edges = [((343, 472), (342, 390)), ((343, 472), (312, 344)),
         ((343, 472), (337, 302)), ((478, 456), (460, 441))]
adj_matrix = defaultdict(set)

for x, y in edges:
    adj_matrix[x].add(y)
    adj_matrix[y].add(x) # Assuming undirected graph

pprint.pprint(adj_matrix)

输出：

defaultdict(<class 'set'>,
            {(312, 344): {(343, 472)},
             (337, 302): {(343, 472)},
             (342, 390): {(343, 472)},
             (343, 472): {(312, 344), (337, 302), (342, 390)},
             (460, 441): {(478, 456)},
             (478, 456): {(460, 441)}})

不需要为顶点命名，除非您明确需要为某些特定目的命名。你知道吗