Paths in graphs 1

Question 1

How do distances change if a directed graph is made undirected by removing the arrows (directions) from its edges like this?

https://drive.google.com/file/d/1J5dAyrF12lnO2fuyFHL8–PfluHPzN8_/view?usp=sharing

Distance between any pair of vertices in the directed graph is less than o equal to the distance between the same pair of vertices in the corresponding undirected graph

Distance between any pair of vertices in the directed graph is greater than or equal to the distance between the same pair of vertices in the corresponding undirected graph

Distance between a pair of verticies in the directed graph ca be less and can be greated than the distance between the same pai of vertices in the corresponding undirected graph.

Question 2

What will be the number of distance layers in this graph if we select vertex A as the starting vertex vs if we select vertex C as the starting vertex?

https://drive.google.com/file/d/1n4tN91ECSbQJ4CMSM2g1UE2MeLvWZm8J/view?usp=sharing

4 if we selected A and 3 if we select C

5 if we selected A and 5 if we select C

4 if we selected A and 3 if we select C

1 if we selected A and 1 if we select C

Question 3

Will Breadth-First Search work as intended if we use stack instead of queue to store the discovered vertices?

Yes
No

Question 4

What is the efficient way to implement this line of pseudocode?

for all (u,v) in G:

Go through all edges of G and consider only those for which starting vertex is u

Go through the adjacency list of vertex u

Question 5

What are all the vertices in this graph which can be undiscovered by the breadth-first search starting from vertex S by the time vertex B is dequeue?

https://drive.google.com/file/d/1COYNq62BK-DrO_76L8Ozh65c40N162ld/view?usp=sharing

G and H
G,H and F
S, A, C, D, and E
H

Question 6

Consider the shortest-path tree (to the right) built by breadth-first search from vertex S on the graph to the left. What other vertex could potentially be the parent of vertex B in the shortest-path tree built by breadth-first search from S if the edges of the graph were stored in a different order?

https://drive.google.com/file/d/1NBkNKRZlI281VO3w752ovv1vrW2ITvDd/view?usp=sharing

C
D
G
S