19. Computational Thinking and Problem-Solving
1. Graphs
Graphs:
● Abstract data structures representing complex
relationships between the items of data
● Made a set of vertices or nodes (the circles with
the items of data) connected by edges (the lines)
● Edges may be weighted (where each edge has a
weight/value associated with it), indicating a
cost of traversal
● In an undirected graph, all edges are bidirectional (can travel in both directions); in a directed
graph or digraph, all edges are one-way
Graphs can be implemented using one of two ways:
● Adjacency matrix
● Adjacency list
Adjacency matrix:
● Each row and column represents a node
● The item at [row, column] indicates a connection
○ In an unweighted graph, this can be a 1
○ For a weighted graph, the entries represent the weights
● In an undirected graph, the matrix will be symmetric
● A matrix is essentially the same as a two-dimensional array when coding
→
→
, Adjacency list:
● An adjacency list is an alternative way of representing a graph
● A list of nodes is created, and each node points to a list of adjacent nodes
● This can be implemented using a dictionary
○ For weighted graphs, a dictionary of dictionaries can be used, with each key in the
dictionary being the node, and the value being a dictionary of adjacent nodes and edge
weights
graph = {
‘A’:[‘C’]
‘B’:[‘C’, ‘D’]
‘C’:[‘D’, ‘E’, ‘F’]
‘D’:[‘A’, ‘F’]
‘E’:[]
‘F’:[]
}
There are two ways of traversing a graph:
● Depth-first - go as far as you can down a path before backtracking and going down the next path
● Breadth-first - explore all the neighbours of the current vertex, then the neighbours of each of
those vertices and so on
Applications of graphs:
● AI - Artificial Neural Networks
● Routing packets over the Internet
● Maps/GPS, with nodes as locations and edges as routes
1. Graphs
Graphs:
● Abstract data structures representing complex
relationships between the items of data
● Made a set of vertices or nodes (the circles with
the items of data) connected by edges (the lines)
● Edges may be weighted (where each edge has a
weight/value associated with it), indicating a
cost of traversal
● In an undirected graph, all edges are bidirectional (can travel in both directions); in a directed
graph or digraph, all edges are one-way
Graphs can be implemented using one of two ways:
● Adjacency matrix
● Adjacency list
Adjacency matrix:
● Each row and column represents a node
● The item at [row, column] indicates a connection
○ In an unweighted graph, this can be a 1
○ For a weighted graph, the entries represent the weights
● In an undirected graph, the matrix will be symmetric
● A matrix is essentially the same as a two-dimensional array when coding
→
→
, Adjacency list:
● An adjacency list is an alternative way of representing a graph
● A list of nodes is created, and each node points to a list of adjacent nodes
● This can be implemented using a dictionary
○ For weighted graphs, a dictionary of dictionaries can be used, with each key in the
dictionary being the node, and the value being a dictionary of adjacent nodes and edge
weights
graph = {
‘A’:[‘C’]
‘B’:[‘C’, ‘D’]
‘C’:[‘D’, ‘E’, ‘F’]
‘D’:[‘A’, ‘F’]
‘E’:[]
‘F’:[]
}
There are two ways of traversing a graph:
● Depth-first - go as far as you can down a path before backtracking and going down the next path
● Breadth-first - explore all the neighbours of the current vertex, then the neighbours of each of
those vertices and so on
Applications of graphs:
● AI - Artificial Neural Networks
● Routing packets over the Internet
● Maps/GPS, with nodes as locations and edges as routes
