为什么我的链表图中的节点以相反的数字顺序排列？

Question

我正在尝试创建一个带有链表操作的邻接表，但我的图边显示的是倒序数字顺序，而不是按顺序排列。例如，我的输出是 Node 0: 3 2 1 而不是 Node 0: 1 2 3

class Node:
    def __init__(self, value):
        self.vertex = value
        self.next = None

class AdjGraph:
    def __init__(self, data):
        self.data = data
        self.graph = [None] * self.data

    # Add edges
    def addEdge(self, vertice, edge):
        node = Node(edge)
        node.next = self.graph[vertice]
        self.graph[vertice] = node

    # Print the graph
    def printGraph(self):
        adj_list = "Adjacency List"
        for i in range(self.data):
            adj_list += "\n\nNode " + str(i) + ": "
            temp = self.graph[i]
            while temp:
                adj_list += str(temp.vertex) + " "
                temp = temp.next
        return adj_list

Answer 1

您需要对 addEdge 函数做一点小改动。您当前的函数基本上是抓取现有节点并将其附加到新节点，即与我们正在寻找的完全相反。

在查看解决方案之前，先看看您的代码做了什么。让我们插入 0.

## graph[0] = None (since there are no nodes)
node = Node(edge) # Node { vertex: 0 }
node.next = self.graph[vertice] ## Node {vertex:0, next: None} since graph[0] is null right now
self.graph[vertice] = node ## graph[0] = Node {vertex: 0, next: None}

现在让我们插入 1 -

node = Node(edge) ## Node { vertex: 1 }
node.next = self.graph[vertice]  ## Node { vertex: 1, next: { vertex: 0, next: None} } 
## Remember what we got in the previous insertion, graph[0] has the first node
## i.e -> 0
self.graph[vertice] = node

因此，在每次插入时，您都会首先获得最新的元素，因此您的结果与您正在寻找的完全相反。

这是我的解决方案（可能不完美）-

class AdjGraph:
    def addEdge(self, vertice, edge):
        
        currNode = self.graph[vertice] # The existing node at specified index
        newNode = Node(edge)  # Creating a new node
        if currNode == None:  # If there are no elements in this node
            self.graph[vertice] = newNode 
            return
        
        while currNode != None: # Traversing
            if currNode.next == None:
                currNode.next = newNode # Attaching the New Node to the tail of the existing node
                break
            currNode = currNode.next

ag = AdjGraph(1)
ag.addEdge(0,0)
ag.addEdge(0,1)
ag.addEdge(0,2)
ag.addEdge(0,3)
print(ag.printGraph())
## Result
## Adjacency List
## Node 0: 0 1 2 3

为什么我的链表图中的节点以相反的数字顺序排列？

Why are the nodes in my linked list graph going in reverse numerical order?

python

graph

linked-list

adjacency-list