(a) Use adjacency list, and (b) adjacency matrix to represent the graph Continue

Question

(a) Use adjacency list, and (b) adjacency matrix to represent the graph Continue its graph search by filling the numbers inside the vertices: (d) Draw the resulted tree of such graph search: (e) Classify each edge: (f) Perform sort on both Fig. 6 and Fig. 7-1. Write down the result if it is double. If not, explain why: (g) Find the strongly connected components in Fig. 6. Each of Fig. 7-1 and 7-2 is an intermediate step during MST-building process. Determine if each one is from Prim's or algorithm, and finish their MST building process by ordering the edges.

Explanation / Answer

Answer For Question 6.

Graph is a col­lec­tion of nodes or ver­tices (V) and edges(E) between them. We can tra­verse these nodes using the edges. These edges might be weighted or non-weighted. Now for the figure 6 it is a directed graph and the adjacency matrix for the graph should be 7*7 matrix .

adjMaxtrix[i][j] = 1 when there is edge between Ver­tex i and Ver­tex j, else 0.

So,

Adjacency List

Adja­cency List is the Array[] of Linked List, where array size is same as num­ber of Ver­tices in the graph. Every Ver­tex has a Linked List.

For the figure 6 the adjacency list is ,

a ------> b------>c------>d------>e

b------>c------>e

c------>f------>g

d------>e

e------>d

f------>e------>g

g------>null.,

a b c d e f g a 0 1 0 1 1 0 0 b 0 0 1 0 1 0 0 c 0 0 0 0 0 1 1 d 0 0 0 0 1 0 0 e 0 0 0 1 0 0 0 f 0 0 0 0 1 0 1 g 0 0 0 0 0 0 0

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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