Graphs Flashcards
Definition
Data structure used to represent complex relationships between items within datasets.
Can be used to represent
Networks, such as transport networks, IT networks and the Internet.
Graphs consist of
Nodes (aka vertices) joined by edges (aka arcs).
Weighted graph definition
Edges are assigned a value - such as representing time , distance or cost.
Unweighted graph definition
Edges have no values.
Two ways to represent a graph
Adjacency matrices
Adjacency lists
Adjacency matrices definition
Tabular representation of a graph. Each node in the graph is assigned a row and column.
Adjacency matrices table cheat sheet.
1 = an edge between those two nodes (TRUE) 0 = no edge between those two nodes (FALSE)
Should have a diagonal line of 0s to show where the row and column represent the same node.
Adjacency matrices table should have
Diagonal symmetry.
What do adjacency matrices use instead of Boolean values to represent a connection within weighted graphs?
The weight of a edge between two nodes
If there is no weighting between two nodes in an adjacency matrices, what is used?
An arbitrarily large value such as (∞) (infinity when written down).
Why is an arbitrarily large value used in adjacency matrices (Weighted)?
To prevent any shortest path algorithm from using any non existent edges.
Adjacency list definition.
Create a list of adjacent nodes for each node in the graph.
Adjacency lists only record
Only record existing connections in a graph, unlike adjacency matrix which stores even those edges that don’t exist.
Are adjacency matrices or lists more efficient?
Adjacency lists are more efficient as they only store edges that exist in the graph, whereas half of the matrix is repeated data due to non existent edges.
