Python-TypeError: 'Graph' object is not subscriptable

Question

我正在实现一个图表 class 比较广度优先搜索与 Prim 的算法，我有我的代码：

class Graph:
    def __init__(self, n):

        """This is an initialization function to creat a random graph with a specified number of vertices"""
        self.graph = [[inf for i in range(n)] for i in range(n)]
        self.number = n
        self.edge = tuple(range(n))
        for i in self.edge[1:]:
            j = random.randint(1, i)
            k = random.sample(range(i), j)
            for l in k:
                weight = random.randint(1, 100)
                self.graph[i][l] = self.graph[l][i] = weight

    def get_neighbours(self, i):

        """This is a function used to get neighbours of the specified vertex"""
        neighbours = []
        for e in self.edge:
            if self[i][e] < inf:
                neighbours.append(e)
        return neighbours

    def breadth_first_search(self):
        """
        This is a function used to return the total of the weight of the edges from a randomly-selected vertex
        :return: the total of the weight of the edges
        """
        all = set(self.edge)
        q = deque([all.pop()])
        total_weight = 0
        while q:
            i = q.popleft()
            for j in self.get_neighbours(i):
                if j in all:
                    all.remove(j)
                    q.append(j)
                    total_weight = total_weight + self.graph[i][j]
        return total_weight

    def test_bfst(self):
        """
        This function is used to test breadth first search tree
        :return:
        """
        graph = [
            [inf, 15, inf, 7, 10, inf],
            [15, inf, 9, 11, inf, 9],
            [inf, 9, inf, inf, 12, 7],
            [7, 11, inf, inf, 8, 14],
            [10, inf, 12, 8, inf, 8],
            [inf, 9, 7, 14, 8, inf]
        ]
        self.graph = graph
        print(self.breadth_first_search())

    def prime_mst(self):
        """
        This is prime's minimum spanning tree algorithm
        :return: the total of the weight of the edges
        """
        all = set(self.edge)
        list = [inf for i in self.edge]
        i = all.pop()
        total_weight = 0
        while True:
            for j in self.get_neighbours(i):
                if (i in all) and (k := self.graph[i][j] < list[j]):
                    list[j] = k

            if all:
                average_min, min = sorted([(j, list[j]) for j in all], key=lambda group: group[1])[0]
                all.remove(average_min)
                total_weight += min
                i = average_min
            else:
                break

        return total_weight


if __name__ == "__main__":
    times = int(input("please input an positive integer which represents testing times:"))
    for n in [20, 40, 60]:
        graph = Graph(n)
        diff = 0
        for i in range(times):
            bfs = graph.breadth_first_search()
            pmst = graph.prime_mst()
            diff = diff + (bfs - pmst) / pmst
        diff = diff / times
        print(diff)

当我运行代码时，错误是这样的：

Traceback (most recent call last):
  File "C:\Users799\Desktop\Bsf_Prims\BSFvPRIM.py", line 99, in <module>
    bfs = graph.breadth_first_search()
  File "C:\Users799\Desktop\Bsf_Prims\BSFvPRIM.py", line 45, in breadth_first_search
    for j in self.get_neighbours(i):
  File "C:\Users799\Desktop\Bsf_Prims\BSFvPRIM.py", line 31, in get_neighbours
    if self[i][e] < inf:
TypeError: 'Graph' object is not subscriptable

我在想我在获取顶点邻居时可能会出错，但我不知道为什么会出现这个错误。而我的测试图更像是一个包含节点的矩阵。我有点坚持获取邻居，其余两个算法稍后会改进。

Answer 1

当你这样说时：

if self[i][e] < inf:

您正在尝试从对象的实例中获取特定项目，就好像它是一个容器，例如序列或映射类型，例如实现 __getitem__() 方法的东西，例如列表或字典。

值得注意的是，字符串和字节串也被视为序列并实现了 __getitem__() 方法，这意味着它们也是可订阅的：

In [1]: from typing import Sequence                                             

In [2]: string = "something"                                                    

In [3]: isinstance(string, Sequence)                                            
Out[3]: True

In [4]: string[2]                                                              
Out[4]: 'm'

您可能想在这里指定一个特定的属性，例如：

if self.graph[i][e] < inf:

我对你正在做的事情还不够熟悉，无法确定你在这里的意图是什么，但你想要像上面这样的东西。您不想“下标”class 实例本身，而是一些具有可下标容器值的属性。

如果您确实需要 class 可订阅，则需要添加一个 __getitem__() 方法，例如映射或序列。

Python-TypeError: 'Graph' object is not subscriptable

Python-TypeError: 'Graph' object is not subscriptable

python

graph-theory

breadth-first-search