The problem is under-specified; nonetheless, I will try to help assuming that you are looking for the graph traversal tree.
To obtain such a tree, you can use a graph traversal algorithm such as breadth-first search. You can find a nice implementation of this algorithm in The Algorithm Design Manual by Steven Skiena.
Note that you need to adapt an important aspect of the algorithm:
- Do not set a node as discovered unless the node has been visited from all of its incoming edges. Without this adaptation, each node will only be visited once, and, therefore, the behaviour of the algorithm will be the same as if multi-edges did not exist.
You will also need a data structure to store the tree of interest. In Skiena's implementation, this data structure is an array that is called
parent: if node
i is discovered from node
parent[i] = j.
The vertex that discovered vertex i is defined as parent[i]. Every vertex is discovered during the course of traversal, so, except for the root, every node has a parent. The parent relation defines a tree of discovery with the initial search node as the root of the tree.
Steven Skiena - The Algorithm Design Manual
However, note that you will need a slightly more complex data structure to support duplicated nodes.