Back to the full dot-point answer
SingaporeComputer ScienceQuick questions
Data Structures
Quick questions on Graph representation explained: H2 Computing
6short Q&A pairs drawn directly from our worked dot-point answer. For full context and worked exam questions, read the parent dot-point page.
What is graph terminology?Show answer
A graph is a set of vertices (nodes) connected by edges. Key terms:
What is adjacency matrix?Show answer
An adjacency matrix is a grid where cell is 1 (or the weight) if an edge runs from to , else 0. For an undirected graph the matrix is symmetric:
What is adjacency list?Show answer
An adjacency list stores, for each vertex, a list of its neighbours:
What is q1?Show answer
State the space complexity of an adjacency matrix and of an adjacency list. [2 marks]
What is q2?Show answer
Which representation answers "is there an edge from u to v?" in ? [1 mark]
What is q3?Show answer
Why is an adjacency list preferred for a sparse graph? [2 marks]
Have a question we have not covered?
This dot-point answer is short enough that we have not extracted many short questions yet. Read the full dot-point answer or ask Mo, our study assistant, in the chat for follow ups.