29 août 20193 août 2020 Bastien Pasdeloup A graph traversal is a way to... split the graph in half. explore the graph, one vertex at a time, using knowledge about the neighbors of explored vertices. obtain the list of accessible vertices from an initial one. Let's say we use a DFS from vertex v1 on an unweighted graph. Which of the following propositions are true? We obtain a spanning tree, covering the accessible vertices from v1. We obtain shortest paths from v1 to the accessible vertices of the graph. We follow a trail, as long as there are unexplored vertices to jump to. We go through each edge of the graph exactly one time. Let's say we use a BFS from vertex v1 on an unweighted graph. Which of the following propositions are true? We go through each edge of the graph exactly one time. We follow a trail, as long as there are unexplored vertices to jump to. We obtain shortest paths from v1 to the accessible vertices of the graph. We obtain a spanning tree, covering the accessible vertices from v1. Time is Up!
