GATE CSE 1987 | Question: 9d

Question

Specify an adjacency-lists representation of the undirected graph given above.

Answer 1

An adjacency list is an array $A$ of separate lists.

Each element of the array $A_{i}$ is a list, which contains all the vertices that are adjacent to vertex $i$.

• $A_{1}\rightarrow2\rightarrow3\rightarrow5$
• $A_{2}\rightarrow1\rightarrow3$
• $A_{3}\rightarrow1\rightarrow2\rightarrow4\rightarrow5$
• $A_{4}\rightarrow3\rightarrow5$
• $A_{5}\rightarrow1\rightarrow3\rightarrow4$

Comments

order doesn’t matter!

---

nice explaination

---

Matrix Representation would be :

$\left[ \begin{array}{r | cc} & 1 & 2 & 3 & 4 & 5 \\ 1 & 0 & 1 & 1 & 0 & 1 \\ 2 & 1 & 0 & 1 & 0 & 0 \\ 3 & 1 & 1 & 0 & 1 & 1 \\ 4 & 0 & 0 & 1 & 0 & 1 \\ 5 & 1 & 0 & 1 & 1 & 0 \end{array} \right]$

---

Representation	Best For
Adjacency List     -	Sparse graphs (less edges)
Adajcency Matrix   -	Dense graphs