SpanningTree.py

adjacencyList = []

numVertices = input("Enter the number of vertices: ")

userFile = input("Enter the filename: ")

inputFile = open(userFile, "r")

for line in inputFile:
    if line != "\n":
        adjacencyList.append(line.split(' '))

n = 0
while n < len(adjacencyList):
    j = 0
    while j < len(adjacencyList[n]):
        adjacencyList[n][j] = int(adjacencyList[n][j])
        j += 1
    n += 1


tree = []  # spanning tree (adjacency list)
vertices = int(numVertices)

for vertexNum in range(vertices):
    tree.append([])

# vertex has been included in the spanning tree? (0 = no, 1 = yes)
treeVertices = vertices * [0]
# start at vertex 0
treeVertices[0] = 1

for vertex in range(0, vertices):
    for adjVertex in adjacencyList[vertex]:
        # check if start of edge is in tree, and end of edge is NOT in tree
        if treeVertices[vertex] == 1 and treeVertices[adjVertex] == 0:
            treeVertices[adjVertex] = 1         # add vertex in tree
            tree[adjVertex].append(vertex)      # update representation of tree
            tree[vertex].append(adjVertex)


print("Adjacency List: ", end="")
print(adjacencyList)
print("Spanning Tree edges: ", end="")
print(tree)
print("vertices in the tree: ", end="")
print(treeVertices)

inputFile.close()

testGraph.txt

0 1

2 1

0 2

1 3