I'm currently learning how to implement Prim's spanning tree algorithm on an graph using an adjacency list. However, I encountered an error

AttributeError: 'list' object has no attribute 'keys'

This is my code.

import heapq
from collections import defaultdict

class Edge:
    def __init__(self, startIndex, endIndex, weight):
        self.startIndex = startIndex
        self.endIndex = endIndex
        self.weight = weight
        self.next = None

    def __str__(self):
        return "["   str(self.startIndex)   ","   str(self.endIndex)   ","   str(self.weight)   "]"


class WGraph:
    def __init__(self, size=10):
        self.size = 10
        self.nodeList = {}
        self.adjacencyMatrix = [[0] * size for i in range(size)]

    def addNode(self, name):
        """Adds node to adjacency list"""
        self.nodeList[name] = []

    def addEdge(self, startIndex, endIndex, weight):
        """Add edges for adjacency list and matrix"""
        edge1 = [endIndex, weight]
        self.nodeList[startIndex].append(edge1)
        edge2 = [startIndex, weight]
        self.nodeList[endIndex].append(edge2)

        keys = sorted(self.nodeList.keys())  # sort keys in adjacency list
        size = len(keys)  # get length of keys
        index1 = list(self.nodeList.keys()).index(startIndex)
        index2 = list(self.nodeList.keys()).index(endIndex)
        self.adjacencyMatrix[index1][index2] = weight


    def listNodes(self):
        """Display nodes in list format"""
        theList = ""
        for node in self.nodeList:
            theList  = str(node)
            theList  = " "
        return theList

    def displayAdjacency(self):
        for k, v in self.nodeList.items():
            print(str(k)   ":", end="")
            for edge in v:
                print(edge, end="")
            print()

    def minCostTree(self, vertex):
        mst = defaultdict(set)
        visited = {vertex}
        edges = [
            (cost, vertex, to)
            for to, cost in self.nodeList[vertex].items()]
        heapq.heapify(edges)

        while edges:
            cost, frm, to = heapq.heappop(edges)
            if to not in visited:
                visited.add(to)
                mst[frm].add(to)
                for to_next, cost in self.nodeList[to].items():
                    if to_next not in visited:
                        heapq.heappush(edges, (cost, to, to_next))
        return mst

graph = WGraph()
graph.addNode('A')
graph.addNode('B')
graph.addNode('C')
graph.addNode('D')
graph.addNode('E')
graph.addNode('F')
graph.addNode('G')
graph.addNode('H')
graph.addNode('I')
graph.addNode('J')

graph.addEdge('A', 'B', 4)
graph.addEdge('A', 'H', 8)
graph.addEdge('B', 'C', 8)
graph.addEdge('B', 'H', 11)
graph.addEdge('C', 'D', 7)
graph.addEdge('C', 'F', 4)
graph.addEdge('C', 'I', 2)
graph.addEdge('D', 'E', 9)
graph.addEdge('D', 'F', 14)
graph.addEdge('E', 'F', 10)
graph.addEdge('F', 'G', 2)
graph.addEdge('G', 'H', 1)
graph.addEdge('G', 'I', 6)
graph.addEdge('H', 'I', 7)

print("The min cost tree starting at A ")
print(" Expected A: A-B A-H H-G G-F F-C C-I C-D D-E Unreached J")
print(" Actually "   graph.minCostTree('A'), end="\n")

This is where the error happens

for to, cost in self.nodeList[vertex].items()]

The adjacency list is initialized as a dictionary. When I add nodes to the dictionary, it creates another list that's used to store the edges and weight. I suspect that having a list inside a dictionary and using the index() function to return the object caused this error. My goal is to return a string showing a minimum cost spanning tree with the starting node as root. However, I'm unable to figure out a way to fix this error. Any help would be appreciated!

CodePudding user response：

The error you are seeing is because you are trying to call the keys() method on a list object, but list objects do not have a keys() method.

You are trying to iterate over the items in the nodeList dictionary using for to, cost in self.nodeList[vertex].items():, but the values in the nodeList dictionary are lists, not dictionaries.

To fix this error, you can change the code to iterate over the values in the lists in the nodeList dictionary like this:

for edge in self.nodeList[vertex]:
    to, cost = edge
    if to not in visited:
        heapq.heappush(edges, (cost, to, to_next))

This way, you are getting the to and cost values from the tuples in the lists instead of trying to use the items() method on a list object.