I have this piece of code above:

N = 8
inf = 99

graph = [[0,0,6,7,0,8,0,0], #1
         [0,0,0,3,4,2,0,0], #2
         [6,0,0,0,0,3,0,7], #3
         [7,3,0,0,9,0,0,0], #4
         [0,4,0,9,0,0,5,0], #5
         [8,2,3,0,0,0,9,3], #6
         [0,0,0,0,5,9,0,0], #7
         [0,0,7,0,0,3,0,0]] #8

# Матрица инцидентности для остовного дерева (задаётся пустой)
spanning_tree_graph = [[0,0,0,0,0,0,0,0] for node in range(N)]

selected_nodes = [False for node in range(N)] # какие вершины включены, какие нет

while(False in selected_nodes): # Пока есть невключенные вершины:
    minimum = inf

    start = 0
    end = 0

    for i in range(0, N):
        if selected_nodes[i]:
            for j in range(0 i, N):
                if(not selected_nodes[j] and graph[i][j] > 0):
                    if graph[i][j] < minimum:
                        minimum = graph[i][j]
                        start, end = i, j
    selected_nodes[end] = True
    spanning_tree_graph[start][end] = minimum

    if minimum == inf:
        spanning_tree_graph[start][end] = 0

    spanning_tree_graph[end][start] = spanning_tree_graph[start][end]

print(spanning_tree_graph)

But output is empty, and I don't know why.

I'm trying to render the sorted graph. Like this

[[0, 8, 2, 4, 0, 0, 0, 0], [8, 0, 0, 0, 0, 0, 0, 0], [2, 0, 0, 0, 0, 5, 0, 4], [4, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0, 4, 0], [0, 0, 5, 0, 0, 0, 0, 0], [0, 0, 0, 0, 4, 0, 0, 0], [0, 0, 4, 0, 0, 0, 0, 0]]

CodePudding user response：

Here is what I believe to be a fixed implementation.

N = 8
inf = 99

graph = [[0,0,6,7,0,8,0,0], #1
         [0,0,0,3,4,2,0,0], #2
         [6,0,0,0,0,3,0,7], #3
         [7,3,0,0,9,0,0,0], #4
         [0,4,0,9,0,0,5,0], #5
         [8,2,3,0,0,0,9,3], #6
         [0,0,0,0,5,9,0,0], #7
         [0,0,7,0,0,3,0,0]] #8

# Матрица инцидентности для остовного дерева (задаётся пустой)
spanning_tree_graph = [[0,0,0,0,0,0,0,0] for node in range(N)]

selected_nodes = [False for node in range(N)] # какие вершины включены, какие нет
selected_nodes[0] = True

while(False in selected_nodes): # Пока есть невключенные вершины:
    minimum = inf

    start = 0
    end = 0

    for i in range(0, N):
        if selected_nodes[i]:
            for j in range(0, N):
                if(not selected_nodes[j] and graph[i][j] > 0):
                    if graph[i][j] < minimum:
                        minimum = graph[i][j]
                        start, end = i, j
    selected_nodes[end] = True
    spanning_tree_graph[start][end] = minimum

    if minimum == inf:
        spanning_tree_graph[start][end] = 0
        break

    spanning_tree_graph[end][start] = spanning_tree_graph[start][end]

for g in spanning_tree_graph:
    print(g)

Here were the bugs that I fixed.

1. You have to start with a node (any node) in the spanning tree graph for it to get going.
2. You're looping through pairs to find i a selected node and j not. You were not willing to consider j < i but it might be.
3. If minimum == inf then the next loop iteration will find the same, and you have an infinite loop. So break with the partial tree.
4. I modified the print at the end to display in a more convenient format.