Python辅导 | Graph with nodes and edges

使用Python完成图的数据结构一系列操作

Graph with nodes and edges

Consider the following directed graph with 6 nodes and 12 edges.

Figure 1. A directed graph with 6 nodes and 12 directed edges (a bidirectional edge is regarded as two directed edges in this question, so there are 12 directed edges in total).

The program source code is shown below.

def main():

command=input().split()

while(command[0]!=”END”):

if (command[0]==”InsertNode”):

InsertNode(int(command[1]),command[2])

elif (command[0]==”InsertEdge”):

InsertEdge(int(command[1]),int(command[2]))

elif (command[0]==”CommonNeighbor”):

CommonNeighbor(int(command[1]),int(command[2]))

elif (command[0]==”ShortestPath”):

ShortestPath(int(command[1]),int(command[2]))

command=input().split()

return

InsertNode 0 Library_Building
InsertNode 1 Hui_Oi_Chow_Science_Building
InsertNode 2 University_Street
InsertNode 3 Kadoorie_Biological_Sciences_Building
InsertNode 4 Haking_Wong_Building
InsertNode 5 Chow_Yei_Ching_Building

Testcases.pdf

InsertEdge 0 1
InsertEdge 1 0
InsertEdge 1 2
InsertEdge 2 1
InsertEdge 0 3
InsertEdge 3 0
InsertEdge 2 4
InsertEdge 4 2
InsertEdge 3 4
InsertEdge 4 3
InsertEdge 4 5
InsertEdge 5 4

CommonNeighbor 1 3
0 Library_Building
CommonNeighbor 1 5
No common neighbor.
CommonNeighbor 1 0
No common neighbor.

ShortestPath 0 4
0 Library_Building
3 Kadoorie_Biological_Sciences_Building
4 Haking_Wong_Building
ShortestPath 1 5
1 Hui_Oi_Chow_Science_Building
2 University_Street
4 Haking_Wong_Building
5 Chow_Yei_Ching_Building

How to find the shortest path? We may use the breadth-first search technique as follow:

Step 1. Initialization.

Figure 2a. Initialization of the searching process.

Step 2. Start searching.

while (visited[des]==False and #len of q is not 0):

Step 1. Pop the first node from q, and store the node in current.

current = q.pop(0)

Step 2. For each neighbor node n of the current node

Step 5. Repeat Step 1. if the destination node is not reached and q is not empty.

Figure 2b. The instance after exploring the neighbor of node 0 (the source node).

Figure 2c. The instance after exploring the neighbor of node 1.

Figure 2d. The instance after exploring the neighbor of node 3, since the destination node is reached, we can break the while loop. The shortest path information is now stored in previous.

題目提供代碼：

node={} #Global variable with key as node ID (an integer), value as name of the node.

edge={} #Global variable with key as the node ID (an integer), value as a set of neighbor node ID(s)

def InsertNode(id,name):

#Empty function, to be implemented by you

def InsertEdge(id1,id2):

#Empty function, to be implemented by you

def CommonNeighbor(id1,id2):

#Empty function, to be implemented by you

def ShortestPath(src,des):

#Empty function, to be implemented by you

def main():

command=input().split()

while(command[0]!=”END”):

if (command[0]==”InsertNode”):

InsertNode(int(command[1]),command[2])

elif (command[0]==”InsertEdge”):

InsertEdge(int(command[1]),int(command[2]))

elif (command[0]==”CommonNeighbor”):

CommonNeighbor(int(command[1]),int(command[2]))

elif (command[0]==”ShortestPath”):

ShortestPath(int(command[1]),int(command[2]))

command=input().split()