6. Given the graph shown below, answer the following questions (4 marks) Illustr

Question

6. Given the graph shown below, answer the following questions

(4 marks) Illustrate the sequence of vertices of this graph visited using depth-first search traversal starting at vertex g.

(4 marks) Illustrate the sequence of vertices of this graph visited using breadth-first search traversal starting at vertex b.

(7 marks) Illustrate adjacency list representation and adjacency matrix representation, respectively, for this graph. What are the advantages and disadvantages of those two representations?

Explanation / Answer

A
depth-first search (DFS)
- in an undirected graph G is like wandering in a labyrinth with a string and a can of red paint without getting lost.
- We start at vertex s , tying the end of our string to the point and painting s “visited”. Next we label s as our current vertex called u .
- Now we travel along an arbitrary edge ( u,v ).
- If edge ( u , v ) leads us to an already visited vertex v we return to u .
- If vertex v is unvisited, we unroll our string and move to v , paint v “visited”, set v as our current vertex, and repeat the previous
steps.
- Eventually, we will get to a point where all incident. Edges on u lead to visited vertices. We then backtrack by unrolling our string to
a previously visited vertex v.Then v becomes our current vertex and we repeat the previous steps.
- Then, if we all incident edges on v lead to visited vertices, we backtrack as we did before. We continue to backtrack along the path we
have traveled, finding and exploring unexplored edges, and repeating the procedure.
- When we backtrack to vertex s and there are no more unexplored edges incident on s , we have finished our DFS search.

Algorithm DFS ( v );
Input : A vertex v in a graph
Output : A labeling of the edges as “discovery” edges and “backedges”
for each edge e incident on v do
if edge e is unexplored then
let w be the other endpoint of e
if vertex w is unexplored then
label e as a discovery edge
recursively call
DFS ( w )
else
label e as a backedge

Breadth-First Search

- a Breadth-First Search ( BFS ) traverses a connected component of a graph, and in doing so defines a spanning tree with several useful
properties
- The starting vertex s has level 0, and, as in DFS, defines that point as an “anchor.”
- In the first round, the string is
unrolled the length of one edge, and all of the edges that are only one edge away from the anchor are visited.
- These edges are placed
into level 1 - In the second round, all the new edges that can be reached by unrolling the string 2 edges are visited and placed in level
- This continues until every vertex has been assigned a level.
- The label of any vertex v corresponds to the length of the shortest path from s to v .

Algorithm BFS ( s ):
Input : A vertex s in a graph
Output : A labeling of the edges as “discovery” edges and “cross edges”
initialize container L 0 to contain vertex s
i <- 0
while L i is not empty do
create container L i+1 to initially be empty
for each vertex v in L i do
if edge e incident on v do
let w be the other endpoint of e
if vertex w is unexplored then label e as a discovery edge insert w into L i+1
else
label e as a cross edge i <- i + 1

3)

An adjacency matrix uses O(n*n) memory. It has fast lookups to check for presence or absence of a specific edge, but slow to iterate over all edges.

Adjacency lists use memory in proportion to the number edges, which might save a lot of memory if the adjacency matrix is sparse. It is fast to iterate over all edges, but finding the presence or absence specific edge is slightly slower than with the matrix.

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.