Section 7 Chapter 41 - Graphs
No description yet. This curated deck is ready for daily study.
Card preview (12)
Graph
A set of nodes that are connect by edges. Can be used to represent complex relationships
Weighted Graph
A graph where each edge has a number associated with it. This is often the ‘cost’ to move along that edge
Node
A point on a graph. Nodes are connected to each other by edges and can often represent locations or states.
Edge
An edge connects to nodes. Edges often represent a movement or a change
Undirected graph
Edges are all bidirectional. This means that all edges can be travelled across in both directions
Directed graph
All the edges are one way
Common uses for graphs (4)
• Showing road connections between cities • FSM • Representing a computer network • Showing links between web pages
Adjacency matrix
A table that can be represented with a two dimensional array. It represents the nodes of a graph and the connections between these nodes.
What an undirected graph adjacency matrix will look like
symmetrical
How to represent an unweighted graph with an adjacency matrix
0s and 1s
Adjacency list
A list of all nodes. Each node in the list points to a list of its adjacent nodes and the weights. Can be represented as a list of dictionaries
Adjacency matrix vs adjacency list
Adjacency matrix + Adding an edge is easy + Testing for the presence of an edge is easy - In a graph with lots of nodes but few edges, a adjacency matrix would have a lot of empty wasted space Adjacency list - More space efficient