Data Structures
Lecture 08: Graphs
Edirlei Soares de Lima
<edirlei.lima@universidadeeuropeia.pt>
Graphs
Edge
•
G = (V, E)
–
–
–
G: graph;
V: set of vertices;
E: set of edges;
Vertex
Graphs
•
Directed graph: a graph in which edges have orientations.
–
An edge (u, v) leaves vertex u and enters vertex v.
•
Vertex v is adjacent to vertex u.
–
Edges from a vertex to itself are allowed (self-loops).
Graphs
•
Undirected graph: a graph in which edges have orientations.
–
Edges (u, v) and (v, u) are considered as a single edge. The adjacency
relationship is symmetric.
–
Self-loops are not allowed.
Graphs
•
Weighted graph: directed on undirected graph in which a
number (the weight) is assigned to each edge.
Graphs
•
Degree of a vertex:
–
–
–
In undirected graphs: is the number of edges that are incident to the
vertex.
In directed graphs: is the number of edges that leave the vertex (out-
degree) plus the number of edges that enter the vertex (in-dregree).
A vertex of degree zero is called isolated or unconnected.
Graphs
•
Path between vertices:
–
–
–
A path of length k from a vertex x to a vertex y in a graph G = (V, A) is a
sequence of vertices (v0, v1, v2, ... , vk) such that x = v0 and y = vk, and vi ∈
V for i = 1, 2, ... , k.
The length of a path is the number of edges on it, that is, the path
contains the vertices v0, v1, v2, ... , vk and the edges (v0, v1), (v1, v2), ... ,
(vk-1, vk).
If there is a path c from x to y then y is reachable from x via c.
Graphs
•
Cycles:
–
In a directed graph: a path (v0, v1, ... , vk) forms a cycle if v0 = vk and the
path contains at least one edge.
•
The self-loop is a size 1 loop.
–
In an undirected graph: a path (v0, v1, ... , vk) forms a cycle if v0 = vk and
the path contains at least three edges.
Graphs
•
Connected components:
–
An undirected graph is connected if each pair of vertices is connected by
a path.
–
–
Connected components are the connected parts of a graph.
An undirected graph is connected if it has exactly one connected
component.
Graphs
•
Strongly connected components:
–
–
–
A directed graph G = (V, A) is strongly connected if any two vertices are
reachable from each other.
The strongly connected components of a directed graph are sets of
vertices under the relationship “are mutually reachable”.
A strongly connected directed graph has only one strongly connected
component.
Graph – Representation
•
Adjacency list:
–
Uses an array or linked list Adj with |V| adjacency lists, one for
each vertex v ∈ V.
–
For each u ∈ V, Adj[u] contains references to all vertices v such
that (u, v) ∈ A. That is, Adj[u] contains all adjacency vertices of u.
Graph – Representation
•
Adjacency matrix:
–
Given a graph G = (V, E), we assume that vertices are labeled with
numbers 1, 2, . . . , |V|.
–
The adjacency matrix is a matrix Aij of dimensions |V| × |V|,
where:
1
0
ꢃꢄ ꢃ, ꢅ ∈ ꢀ
ꢆꢇℎꢈꢉꢊꢃꢋꢈ
ꢀꢁꢂ
= ቊ
Graph Vertex – Generic Class
public class GraphVertex<T>
{
private LinkedList<GraphVertex<T>> edges;
private T data;
public GraphVertex(T t){
edges = new LinkedList<GraphVertex<T>>();
data = t;
}
public void AddEdge(GraphVertex<T> v){
edges.InsertAtEnd(v);
}
public LinkedList<GraphVertex<T>> Edges{
get { return edges; }
set { edges = value; }
}
public T Data{
get { return data; }
set { data = value; }
}
}
Graph – Generic Class
public enum GraphType { Directed, Undirected };
public class Graph<T>
{
private LinkedList<GraphVertex<T>> vertices;
public GraphType graphType;
public Graph(GraphType t){
vertices = new LinkedList<GraphVertex<T>>();
graphType = t;
}
.
..
Graph
•
Basic operations:
–
–
–
CreateVertex: creates a vertex and adds it to the list of vertices of the
graph.
AddEdge: adds an edge (u, v) to the graph (connecting vertex u to
vertex v).
Traversal/Search: traverses or search for the path to a certain element
in the graph. Several traversal strategies can be used:
•
•
•
•
•
Breadth-first search (BFS);
Depth-First Search (DFS);
Dijkstra algorithm;
A* algorithm;
…
Graph – CreateVertex
•
Creates a vertex and adds it to the list of vertices of the
graph.
public GraphVertex<T> CreateVertex(T t)
{
GraphVertex<T> vertex = new GraphVertex<T>(t);
vertices.InsertAtEnd(vertex);
return vertex;
}
Graph – AddEdge
•
Adds an edge (u, v) to the graph (connecting vertex u to
vertex v).
–
If the graph is undirected, also connects vertex v to vertex u.
public void AddEdge(GraphVertex<T> v, GraphVertex<T> u)
{
if (graphType == GraphType.Directed)
{
v.AddEdge(u);
}
if (graphType == GraphType.Undirected)
{
v.AddEdge(u);
u.AddEdge(v);
}
}
Graph – Creating a Directed Graph
•
Example:
Graph<string> directedGraph = new Graph<string>(GraphType.Directed);
GraphVertex<string> u = directedGraph.CreateVertex("u");
GraphVertex<string> v = directedGraph.CreateVertex("v");
GraphVertex<string> w = directedGraph.CreateVertex("w");
GraphVertex<string> x = directedGraph.CreateVertex("x");
GraphVertex<string> y = directedGraph.CreateVertex("y");
GraphVertex<string> z = directedGraph.CreateVertex("z");
directedGraph.AddEdge(u, v);
directedGraph.AddEdge(u, x);
directedGraph.AddEdge(x, v);
directedGraph.AddEdge(v, y);
directedGraph.AddEdge(y, x);
directedGraph.AddEdge(w, y);
directedGraph.AddEdge(w, z);
directedGraph.AddEdge(z, z);
Graph – Creating a Undirected Graph
•
Example:
Graph<int> undirectedGraph = new Graph<int>(GraphType.Undirected);
GraphVertex<int> v1 = undirectedGraph.CreateVertex(1);
GraphVertex<int> v2 = undirectedGraph.CreateVertex(2);
GraphVertex<int> v3 = undirectedGraph.CreateVertex(3);
GraphVertex<int> v4 = undirectedGraph.CreateVertex(4);
GraphVertex<int> v5 = undirectedGraph.CreateVertex(5);
GraphVertex<int> v6 = undirectedGraph.CreateVertex(6);
undirectedGraph.AddEdge(v1, v2);
undirectedGraph.AddEdge(v1, v4);
undirectedGraph.AddEdge(v2, v3);
undirectedGraph.AddEdge(v4, v5);
undirectedGraph.AddEdge(v4, v6);
undirectedGraph.AddEdge(v5, v6);
Breadth-First Search (BFS)
•
•
BFS is one of the simplest algorithms for exploring a graph.
–
Given a graph G = (V, E) and a vertex s, called the source, the algorithm
systematically explores the edges of G in order to visit all vertices that
are reachable from s.
The algorithm expands the boundary between discovered and
undiscovered vertices evenly across the width of the
boundary.
–
The algorithm discovers all vertices at a distance k from the origin
vertex before discovering any vertices at a distance k + 1.
•
The graph can be directed or undirected.
Breadth-First Search (BFS)
•
Strategy:
–
The algorithm discovers all vertices at a distance k from the origin
vertex before discovering any vertices at a distance k + 1.
A
B
C
D
E
F
G
Breadth-First Search (BFS)
•
Algorithm:
–
To control the search, the BFS algorithm paints each vertex
white, gray or black.
–
All vertices start white and can later become gray and then
black.
•
•
•
White: not visited;
Gray: visited;
Black: completely explored (all adjacent nodes were visited).
Breadth-First Search (BFS)
BFS(G, s)
for each u ∈ V[G]
c[u] ← white
d[u] ← ∞
ꢌ[u] ← NULL
c[s] ← gray
d[s] ← 0
Q ← {s} //Queue Structure
while Q ≠ ∅
u ← head[Q]
for each v ∈ E[u]
if c[v] = white
c[v] ← gray
d[v] ← d[u] + 1
ꢌ[v] ← u
enqueue(Q,v)
dequeue(Q)
c[u] ← black
Breadth-First Search (BFS)
for each u ∈ V[G]
c[u] ← white
d[u] ← ∞
ꢌ[u] ← NULL
c[s] ← gray
d[s] ← 0
Q ← {s} //Queue
Breadth-First Search (BFS)
u ← head[Q]
for each v ∈ E[u]
if c[v] = white
c[v] ← gray
d[v] ← d[u] + 1
ꢌ[v] ← u
enqueue(Q,v)
dequeue(Q)
c[u] ← black
Breadth-First Search (BFS)
u ← head[Q]
for each v ∈ E[u]
if c[v] = white
c[v] ← gray
d[v] ← d[u] + 1
ꢌ[v] ← u
enqueue(Q,v)
dequeue(Q)
c[u] ← black
Breadth-First Search (BFS)
u ← head[Q]
for each v ∈ E[u]
if c[v] = white
c[v] ← gray
d[v] ← d[u] + 1
ꢌ[v] ← u
enqueue(Q,v)
dequeue(Q)
c[u] ← black
Breadth-First Search (BFS)
u ← head[Q]
for each v ∈ E[u]
if c[v] = white
c[v] ← gray
d[v] ← d[u] + 1
ꢌ[v] ← u
enqueue(Q,v)
dequeue(Q)
c[u] ← black
Breadth-First Search (BFS) – Analysis
BFS(G, s)
for each u ∈ V[G]
c[u] ← white
d[u] ← ∞
ꢌ[u] ← NULL
c[s] ← gray
d[s] ← 0
Q ← {s} //Queue Structure
while Q ≠ ∅
•
•
Each vertex of V is placed on queue Q at
most once: O(V);
The adjacency list of any vertex of u is
traversed only when the vertex is
removed from the queue;
•
The sum of all adjacent lists is O(E), so
the total time spent on the adjacent lists
is O(E);
u ← head[Q]
for each v ∈ E[u]
if c[v] = white
c[v] ← gray
d[v] ← d[u] + 1
ꢌ[v] ← u
•
•
Queuing and dequeuing cost O(1);
BFS complexity: O(V + E)
enqueue(Q,v)
dequeue(Q)
c[u] ← black
Breadth-First Search (BFS) – C#
public Dictionary<GraphVertex<T>, GraphVertex<T>> BFS(GraphVertex<T> s)
{
Dictionary<GraphVertex<T>, int> d = new Dictionary<GraphVertex<T>, int>();
Dictionary<GraphVertex<T>, int> c = new Dictionary<GraphVertex<T>, int>();
Dictionary<GraphVertex<T>, GraphVertex<T>> pi = new
Dictionary<GraphVertex<T>, GraphVertex<T>>();
Queue<GraphVertex<T>> Q = new Queue<GraphVertex<T>>();
foreach (GraphVertex<T> u in vertices)
{
c[u] = 0; //white
d[u] = int.MaxValue;
pi[u] = null;
}
c[s] = 1; //gray
d[s] = 0;
Q.Enqueue(s);
while (!Q.IsEmpty())
{
QueueNode<GraphVertex<T>> u = Q.Dequeue();
.
..
Breadth-First Search (BFS) – C#
.
..
foreach (GraphVertex<T> v in u.Data.Edges)
{
if (c[v] == 0) //white
{
c[v] = 1;
d[v] = d[u.Data] + 1;
pi[v] = u.Data;
Q.Enqueue(v);
}
}
c[u.Data] = 2; //black
}
return pi;
}
Breadth-First Search (BFS)
•
It is possible to reconstruct the search tree with the information
of π i:
Breadth-First Search (BFS)
•
It is possible to reconstruct the search tree with the information
of π i:
Assignment 1 – Graphs
1
) Create a function to use the information stored in π to print
the path from the start vertex to another vertex of the graph.
–
–
The path must be displayed in the correct order.
Hint: when reading the information from π, the path will be inverted,
but you can use a stack structure to store the vertices from π and
easily retrieve them in the correct order.
Depth-First Search (DFS)
•
•
The DFS strategy is to seek the deepest vertex in the graph
whenever possible:
–
Edges are explored from the most recently discovered vertex v that
still has unexplored edges.
When all edges of v have been explored, the search moves
backwards to explore the edges of the vertex from which v
was discovered (backtracking).
Depth-First Search (DFS)
•
Strategy:
–
Edges are explored from the most recently discovered vertex v that
still has unexplored edges.
A
B
D
C
E
F
M
N
P
Q
Depth-First Search (DFS)
•
Algorithm:
–
To control the search, the BFS algorithm paints each vertex
white, gray or black.
–
All vertices start white and can later become gray and then
black.
•
•
•
White: not visited;
Gray: visited;
Black: completely explored (all adjacent nodes were visited).
Depth-First Search (DFS)
•
Algorithm:
–
The DFS algorithm marks each vertex with a timestamp.
–
Each vertex has two timestamps:
•
•
d[v]: indicates the time when v was visited (painted with grey);
f[v]: indicates the time when v was completely explored (all
adjacent nodes were visited) (painted black).
Depth-First Search (DFS)
DFS(G)
for each u ∈ V[G]
c[u] ← white
ꢌ[u] ← NULL
time ← 0
for each u ∈ V[G]
if c[u] = white
Visit(u)
Visit(u)
c[u] ← gray
d[u] ← time ← time + 1
for each v ∈ E[u]
if c[v] = white
ꢌ[v] ← u
Visit(v)
c[u] ← black
f[u] ← time ← time + 1
Depth-First Search (DFS)
for each u ∈ V[G]
c[u] ← white
ꢌ[u] ← NULL
time ← 0
for each u ∈ V[G]
if c[u] = white
Visit(u)
u
w
/
v
w
/
y
w
/
x
w
/
w
w
/
z
w
/
c
ꢌ
d
f
Depth-First Search (DFS)
c[u] ← gray
d[u] ← time ← time + 1
for each v ∈ E[u]
if c[v] = white
ꢌ[v] ← u
Visit(v)
c[u] ← black
f[u] ← time ← time + 1
u
g
/
v
w
/
y
w
/
x
w
/
w
w
/
z
w
/
c
ꢌ
d
f
1
Depth-First Search (DFS)
c[u] ← gray
d[u] ← time ← time + 1
for each v ∈ E[u]
if c[v] = white
ꢌ[v] ← u
Visit(v)
c[u] ← black
f[u] ← time ← time + 1
u
g
/
v
g
u
2
y
w
/
x
w
/
w
w
/
z
w
/
c
ꢌ
d
f
1
Depth-First Search (DFS)
c[u] ← gray
d[u] ← time ← time + 1
for each v ∈ E[u]
if c[v] = white
ꢌ[v] ← u
Visit(v)
c[u] ← black
f[u] ← time ← time + 1
u
g
/
v
g
u
2
y
g
v
3
x
w
/
w
w
/
z
w
/
c
ꢌ
d
f
1
Depth-First Search (DFS)
c[u] ← gray
d[u] ← time ← time + 1
for each v ∈ E[u]
if c[v] = white
ꢌ[v] ← u
Visit(v)
c[u] ← black
f[u] ← time ← time + 1
u
g
/
v
g
u
2
y
g
v
3
x
g
y
4
w
w
/
z
w
/
c
ꢌ
d
f
1
Depth-First Search (DFS)
c[u] ← gray
d[u] ← time ← time + 1
for each v ∈ E[u]
if c[v] = white
ꢌ[v] ← u
Visit(v)
c[u] ← black
f[u] ← time ← time + 1
u
g
/
v
g
u
2
y
g
v
3
x
b
y
4
5
w
w
/
z
w
/
c
ꢌ
d
f
1
Depth-First Search (DFS)
c[u] ← gray
d[u] ← time ← time + 1
for each v ∈ E[u]
if c[v] = white
ꢌ[v] ← u
Visit(v)
c[u] ← black
f[u] ← time ← time + 1
u
g
/
v
g
u
2
y
b
v
3
6
x
b
y
4
5
w
w
/
z
w
/
c
ꢌ
d
f
1
Depth-First Search (DFS)
c[u] ← gray
d[u] ← time ← time + 1
for each v ∈ E[u]
if c[v] = white
ꢌ[v] ← u
Visit(v)
c[u] ← black
f[u] ← time ← time + 1
u
g
/
v
b
u
2
7
y
b
v
3
6
x
b
y
4
5
w
w
/
z
w
/
c
ꢌ
d
f
1
Depth-First Search (DFS)
c[u] ← gray
d[u] ← time ← time + 1
for each v ∈ E[u]
if c[v] = white
ꢌ[v] ← u
Visit(v)
c[u] ← black
f[u] ← time ← time + 1
u
b
/
v
b
u
2
7
y
b
v
3
6
x
b
y
4
5
w
w
/
z
w
/
c
ꢌ
d
f
1
8
Depth-First Search (DFS)
for each u ∈ V[G]
c[u] ← white
ꢌ[u] ← NULL
time ← 0
for each u ∈ V[G]
if c[u] = white
Visit(u)
u
b
/
v
b
u
2
7
y
b
v
3
6
x
b
y
4
5
w
w
/
z
w
/
c
ꢌ
d
f
1
8
Depth-First Search (DFS)
c[u] ← gray
d[u] ← time ← time + 1
for each v ∈ E[u]
if c[v] = white
ꢌ[v] ← u
Visit(v)
c[u] ← black
f[u] ← time ← time + 1
u
b
/
v
b
u
2
7
y
b
v
3
6
x
b
y
4
5
w
g
/
z
w
/
c
ꢌ
d
f
1
8
9
Depth-First Search (DFS)
c[u] ← gray
d[u] ← time ← time + 1
for each v ∈ E[u]
if c[v] = white
ꢌ[v] ← u
Visit(v)
c[u] ← black
f[u] ← time ← time + 1
u
b
/
v
b
u
2
7
y
b
v
3
6
x
b
y
4
5
w
g
/
z
g
c
ꢌ
d
f
w
10
1
8
9
Depth-First Search (DFS)
c[u] ← gray
d[u] ← time ← time + 1
for each v ∈ E[u]
if c[v] = white
ꢌ[v] ← u
Visit(v)
c[u] ← black
f[u] ← time ← time + 1
u
b
/
v
b
u
2
7
y
b
v
3
6
x
b
y
4
5
w
b
z
b
c
ꢌ
d
f
/
w
10
12
1
8
9
11
Depth-First Search (DFS) – Analysis
DFS(G)
for each u ∈ V[G]
c[u] ← white
ꢌ[u] ← NULL
•
The Visit function is called exactly once
for each vertex u ∈ V (visit is called only
for white vertices and the first action is
to paint the vertex gray). Therefore:
O(V);
time ← 0
for each u ∈ V[G]
if c[u] = white
Visit(u)
•
•
The main loop of Visit function is O(E);
Visit(u)
c[u] ← gray
DFS complexity: O(V + E)
d[u] ← time ← time + 1
for each v ∈ E[u]
if c[v] = white
ꢌ[v] ← u
Visit(v)
c[u] ← black
f[u] ← time ← time + 1
Depth-First Search (DFS) – C#
public Dictionary<GraphVertex<T>, GraphVertex<T>> DFS(GraphVertex<T> s)
{
Dictionary<GraphVertex<T>, int> d = new Dictionary<GraphVertex<T>, int>();
Dictionary<GraphVertex<T>, int> c = new Dictionary<GraphVertex<T>, int>();
Dictionary<GraphVertex<T>, int> f = new Dictionary<GraphVertex<T>, int>();
Dictionary<GraphVertex<T>, GraphVertex<T>> pi = new
Dictionary<GraphVertex<T>, GraphVertex<T>>();
int time = 1;
foreach (GraphVertex<T> u in vertices)
{
c[u] = 0; //white
d[u] = int.MaxValue;
f[u] = int.MaxValue;
pi[u] = null;
}
foreach (GraphVertex<T> u in vertices)
{
if (c[u] == 0){ //white
DFSVisit(u, ref time, d, c, f, pi);
}
}
return pi;
}
Depth-First Search (DFS) – C#
private void DFSVisit(GraphVertex<T> u, ref int time,
Dictionary<GraphVertex<T>, int> d,
Dictionary<GraphVertex<T>, int> c,
Dictionary<GraphVertex<T>, int> f,
Dictionary<GraphVertex<T>, GraphVertex<T>> pi)
{
c[u] = 1; //gray
d[u] = time++;
foreach (GraphVertex<T> v in u.Edges)
{
if (c[v] == 0) //white
{
pi[v] = u;
DFSVisit(v, ref time, d, c, f, pi);
}
}
c[u] = 2; //black
f[u] = time++;
}
Applications in Game Programming
•
Pathfinding: while simple movements can be manually
defined (patrol routes or wander regions), more complex
movements must be computed during the game. Pathfinding
algorithms rely on graph structures to represent the level
structure.
•
•
Finite State Machines: are used control the behavior of
characters and are modeled as graph structures. Actions are
associated with state (vertices) and transitions (edges) have
set of associated conditions.
Problem-solving: puzzle games can generally be solved by
searching in the state space for a set of actions that lead from
the current state to a goal state.
Assignment 2 – Graphs
1
) In the class of Game Frameworks, you have learned how to
implement pathfinding in a tilemap using an existing A*
function. Based on the structure of that example, adapt the
BFS and DFS functions to use them to perform the pathfinding
in a tilemap.
–
Important: the current versions of the BFS and DFS functions are
exploring the entire graph structure. But for pathfinding, the process
must stop when the target vertex is found.
–
The tilemap matrix can be interpreted as a graph structure:
Further Reading
•
•
Penton, R. (2002). Data Structures for Game Programmers.
Muska & Lipman/Premier-Trade. ISBN: 978-1931841948
–
Chapter 17: Graphs
Sherrod, A. (2007). Data Structures and Algorithms for
Game Developers. Charles River Media. ISBN: 978-
1584504955
–
Chapter 11: Graphs