DFS和BFS的结果会是一棵tree,
这棵tree的loot就是source node,
BFS tree 和 DFS tree 有一些性质,同学可以从Textbook查到相关资料。
依照pa3.doc规定:
1. For DFS/BFS trees, when there are multiple vertices too choose,
you should always choose the vertex with minimal index first.
2. When you write an edge, please always put the predecessor vertex
in front of the successor vertex.
所以输出档案 edges顺序 以及 vertices顺序 是"固定"的。
第一个edge的第一个vertex 为 source node。
至于MST output之前有公告过,同学可以不用考虑其输出顺序。
以下是gn4.dot source node为v1的输出结果
DFS:
graph gn4_dfs {
v1