7 août 20193 août 2020 Bastien Pasdeloup Imagine a graph where u and v are vertices, and there is no path for which u and v are extremities. If we run a DFS from u, which of the following propositions are true? At the end of the DFS, v has not been explored. The DFS is not well defined and cannot be processed. The resulting tree is made exclusively of shortest paths from u to the accessible vertices of the graph. Imagine we run a DFS (respectively a BFS) from any vertex u of a complete graph of order n. How many vertices are neighbors of u in the resulting tree? n-1 (respectively 1). n(n-1)/2 in both cases. 1 (respectively n-1). Imagine a graph with vertices V = {v1, v2, v3, v4}, in which {v1, v2}, {v1, v3}, and {v1, v4} are edges. Which of the following are correct? To traverse this graph using a DFS from v1, we use a LIFO. v2, v3, and v4 (in this order) are added to the LIFO, and none of them have been previously visited. As a consequence, the next vertex to be visited is v4. To traverse this graph using a BFS from v1, we use a FIFO. v2, v3, and v4 (in this order) are added to the FIFO, and none of them have been previously visited. As a consequence, the next vertex to be visited is v2. To traverse this graph using a DFS from v1, we use a LIFO. v2, v3, and v4 (in this order) are added to the LIFO, and none of them have been previously visited. As a consequence, the next vertex to be visited is v1. Imagine a graph with vertices V = {v1, v2, v3, v4, v5}. A graph traversal algorithm from v1 has produced the following routing table (second row): [undefined, v3, v1, v2, v1]. What is the corresponding path between v1 and v4? {v1, v2}, {v2, v3}, {v3, v4}. {v1, v3}, {v3, v5}, {v4, v5}. {v1, v2}, {v2, v4}. {v1, v3}, {v2, v3}, {v2, v4}. Time is Up!
