Graph Implementations Flashcards
What are the two ways of implementing graphs ?
Adjacency matrix , adjacency list.
What is an adjacency matrix
Two dimensional array that records the relationship between each node and all other nodes in the graph .
Explain the adjacency matrix between nodes in an unweighted graph?
1 is used if there is an edge existing between 2 nodes
0 is used when there is no edge between 2 nodes .
How would you determine the presence or absence of an edge ?
You can inspect using the row / column that represents the node.
You may need a dictionary to record which row is used for a specific nodes edge data.
How are the values of weights stores in the adjacency matrix.?
If you don’t have an edge existing between two nodes , a very large number for example the Infinity sign is shown.
What is the role/ point of an adjacency list?
It records the existence of an edge between each node and all of its neighbours.
What happens with the adjacency list if they are unweighted?
Lists each nodes neighbours
How could you store the information in an adjacency list?
Use an array , or a combination of an array of records and a dictionary
What is the adjacency list used for in a weighted graph ?
Used to record the connection between two nodes and their corresponding weights.
Name some differences between adjacency lists vs adjacency matrices ?
