fig 2018 9 Find the adjacency matrix of the graph in Figure

fig. 20-18

9. Find the adjacency matrix of the graph in Figure 20-18(a).

10. Draw the adjacency list of the graph in Figure 20-18(a).

11. List the nodes of the graph, in Figure 20-18(a), in a depth first traversal.

12. List the nodes of the graph, in Figure 20-18(a), in a breadth first traversal.

13. List the nodes of the graph, in Figure 20-18(b), in a breadth first traversal.

14. List the nodes of the graph, in Figure 20-18(b), in a depth first traversal.

Show transcribed image text

Solution

9

10

11

depth first traversal Fig 20-18(a)

0--2--1--3--5--4

12. Breadth first traversal Fig 20-18(a)

use queue to enter first node ie 0

deque 0 and enque the adjacency list of 0

traversal list

queue = {0}

queue ={2,3} 0

queue = {3,1} 0--2

queue ={1} 0---2---3

queue ={5} 0---2---3

queue ={4} 0--2---3---5

0---2----3---5----4

13. depth first traversal fig 20-18(b)

0---7--2---6---3---11---4----5-----10----9-----8

14. breadth first traversal fig 20-18(b)

using queue and adjacency list

0----1----2---6---7----3----11----4-----5-----8-----9----10----11