Graphs (Γράφοι)
K08 Δομές Δεδομένων και Τεχνικές Προγραμματισμού
Κώστας Χατζηκοκολάκης
Graphs
 Graphs are collections of nodes in which various pairs are
connected by line segments. The nodes are usually called
vertices (κορυφές) and the line segments edges (ακμές).
 Graphs are more general than trees. Graphs are allowed to have
cycles and can have more than one connected component.
 Some authors use the terms nodes (κόμβοι) and arcs (τόξα)
instead of vertices and edges.
Example of Graphs (Directed)
Example of Graphs (Undirected)
Examples of Graphs
 Transportation networks
 Interesting problem: What is the path with one or more stops of
shortest overall distance connecting a starting city and a
destination city?
Examples
 A network of oil pipelines
 Interesting problem: What is the maximum possible overall flow
of oil from the source to the destination?
Examples
 The Internet
 Interesting problem: Deliver an email from user A to user B
Examples
 The Web
 Interesting problem: What is the PageRank of a Web site?
Examples
 The Facebook social network
 Interesting problem: Are John and Mary connected? What
interesting clusters exist?
 A graph $G = (V, E)$ consists of a set of vertices $V$ and a set of
edges $E$, where the edges in $E$ are formed from pairs of
distinct vertices in $V$.
 If the edges have directions then we have a directed graph
(κατευθυνόμενο γράφο) or digraph. In this case edges are
ordered pairs of vertices e.g., $(u,v)$ and are called directed. If $(u,v)$ is a
directed edge then $u$ is called its origin and $v$ is called its
destination.
 If the edges do not have directions then we have an undirected
graph (μηκατευθυνόμενος γράφο). In this case edges are unordered
pairs of vertices e.g., {$u,v$} and are called undirected.
 For simplicity, we will use the directed pair notation noting that
in the undirected case $(u,v)$ is the same as $(v,u)$ .
 When we say simply graph, we will mean an undirected graph.
Example of a Directed Graph
$G = (V, E)$
$V ={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}$
$E~=~{(1,2),(1,3),(2,5),(3,4),(5,4),(5,6),(6,70,(8,9),(8,10),(10,11)}$
Example of an Undirected Graph
$G = (V, E)$
$V ={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}$
$E~=~{(1,2),(1,3),(2,5),(3,4),(5,4),(5,6),(6,70,(8,9),(8,10),(10,11)}$
More Definitions

Two different vertices $v_i ,v_j$ in a graph $G = (V, E)$ are said to be adjacent
(γειτονικές) if there exists an edge $(v_i , v_j) \in E$.

An edge is said to be incident (προσπίπτουσα) on a vertex if the
vertex is one of the edge's endpoints.

A path (μονοπάτι) $p$ in a graph $G = (V, E)$, is a sequence of vertices of
$V$ of the form $p = v_1v_2 … v_n, (n\geq2)$ in
which each vertex $v_i$,
is adjacent to the next one $v_{i+1}$ (for $1 \leq i \leq n1$ ).

The length of a path is the number of edges in it.

A path is simple if each vertex in the path is distinct.

A cycle is a path $p = v_1 v_2 … v_n$ of length greater than one that begins and
ends at the same vertex (i.e., $v_1=v_n$ ).
Definitions
 A directed path is a path such that all edges are directed and
are traversed along their direction.
 A directed cycle is similarly defined.
Definitions
 A simple cycle is a path that travels through three or more
distinct vertices and connects them into a loop.
Example
Four simple cycles: (1,2,3,1) (4,5,6,7,4) (4,5,6,4) (4,6,7,4)
Example
Two nonsimple cycles: (1,2,1) (4,5,6,4,7,6,4)
Example
A path that is not a cycle: (1,2,4,6,8)
Connectivity and Components
 Two vertices in a graph $G = (V,E)$ are said to be connected (συνδεδεμένες)
if there is a path from the first to the second in $G$
 Formally, if $x \in V \text{ and } y \in V \text{, where } x \neq y$ , then $x$ and $y$ are connected if there
exists a path $p = v_1v_2 … v_n \in G$ in such that $x=v_1$ and
$y=v_n$
Connectivity and Components
 In the graph $G=(V,E)$ , a connected component (συνεκτική συνιστώσα) is a
subset $S$ of the vertices $V$ that are all connected to one another.
 A connected component $S$ of $G$ is a maximal connected component (μέγιστη
συνεκτική συνιστώσα) provided there is no bigger subset $T$ of
vertices in $V$ such that $T$ properly contains $S$ and such that $T$ itself is a
connected component of $G$.
 An undirected graph $G$ can always be separated into maximal connected
components $S_1,S_2 ,… ;,S_n$ such that $S_i\cap S_j = \varnothing$ whenever $i \neq j$.
Example of Undirected Graph and its Separation into Two Maximal Connected Components
Connectivity and Components in Directed Graphs
 A subset $S$ of vertices in a directed graph $G$ is strongly connected
(ισχυρά συνεκτικό) if for each pair of distinct vertices $(v_i,v_j)$ in $S$, $v_i$ is
connected to $v_j$ and $v_j$ is connected to $v_i$.
 A subset $S$ of vertices in a directed graph $G$ is weakly connected
(ασθενώς συνεκτικό) if for each pair of distinct vertices $(v_i,v_j)$in $S$, $v_i$ is
connected to $v_j$ or $v_j$ is connected to $v_i$.
Example: A Strongly Connected Digraph
Example: A Weakly Connected Digraph
Degree in Undirected Graphs
 In an undirected graph $G$ the degree (βαθμός) of vertex $x$ is the
number of edges $e$ in which $x$ is one of the endpoints of $e$.
 The degree of a vertex $x$ is denoted by $\mathrm{deg}(x)$.
Example
The degree of node 1 is 2.
The degree of node 4 is 4.
The degree of node 8 is 1.
Predecessors and Successors in Directed Graphs
 If $x$ is a vertex in a directed graph $G=(V,E)$ then the set of
predecessors (προηγούμενων) of $x$ denoted by $\mathrm{Pred}(x)$ is the set of all
vertices $y \in V$ such that $(y,x) \in E$.
 Similarly the set of successors (επόμενων) of $x$ denoted by $\mathrm{Succ}(x)$ is the
set of all vertices $y \in V$ such that $(x,y) \in E$.
InDegree and OutDegree in Directed Graphs
 The indegree of a vertex $x$ is the number of predecessors of $x$
 The outdegree of a vertex $x$ is the number of successors of $x$
 We can also define the indegree and the outdegree by referring to
the incoming and outgoing edges of a vertex.
 The indegree and outdegree of a vertex $x$ are denoted by $\mathrm{indeg}(x)$ and $\mathrm{outdeg}(x)$
respectively.
Example
The indegree of node 4 is 2. The outdegree of node 4 is 1.
Proposition
 If $G$ is an undirected graph with $m$ edges, then $$ \sum_{v \in G} \mathrm{deg}(v)=$$.
 Proof?
 Each edge is counted twice
Proposition

If is a directed graph with edges, then
$$ \sum_{v \in G} \mathrm{indeg}(v) =
\sum_{v \in G} \mathrm{outdeg}(v) = m$$

Proof?
 Each edge is counted once
Proposition
 Let $G$ be a graph with $n$ vertices and $m$ edges. If $G$ is undirected, then $ m \leq \frac {n(n1)}{2}$ and
if $G$ is directed, then $m \leq n(n1)$.
 Proof?
 If $G$ is undirected then the maximum degree of a vertex is $n1$. Therefore,
from the previous proposition about the sum of the degrees, we have $2m \leq n(n1).$
 If $G$ is directed then the maximum indegree of a vertex is $n1$.
Therefore, from the previous proposition about the sum of the
indegrees, we have $m \leq n(n1)$.
More definitions
 A subgraph (υπογράφος) of a graph $G$ is a graph $H$ whose vertices and
edges are subsets of the vertices and edges of $G$ respectively.
 A spanning subgraph (υπογράφος επικάλυψης) of $G$ is a subgraph of
$G$ that contains all the vertices of $G$.
 A forest (δάσος) is a graph without cycles.
 A free tree (ελεύθερο δένδρο) is a connected forest i.e., a
connected graph without cycles. The trees that we studied in earlier
lectures are rooted trees (δένδρα με ρίζα) and they are
different than free trees.
 A spanning tree (δένδρο επικάλυψης) of a graph is a spanning
subgraph that is a free tree.
Example
The thick green lines define a spanning tree of the graph.
Example
The thick green lines define a forest which consists of two free trees.
Graph Representations: Adjacency Matrices
 Let $G=(V,E)$ be a graph. Suppose we number the vertices in $V$ as $v_1,v_2…v_n$
 The adjacency matrix (πίνακας γειτνίασης) corresponding to $G$ is an $n \times n$
matrix such that $T[i,j] = 1$ if there is an edge $(v_i,v_j) \in E$, and $T[i,j] = 0$ if there is no such edge
in $E$.
Example
Adjacency Matrices
 The adjacency matrix of an undirected graph $G$ is a symmetric
matrix i.e., $T[i,j]=T[j,i]$ for all and in the range $ 1 \leq i,j \leq n$
 The adjacency matrix for a directed graph need not be symmetric.
Adjacency Matrices
 The diagonal entries in an adjacency matrix (of a directed or
undirected graph) are zero, since graphs as we have defined them
are not permitted to have looping selfreferential edges that
connect a vertex to itself.
Example
Adjacency Sets
 Another way to define a graph $G=(V,E)$ is to specify adjacency sets (σύνολα
γειτνίασης) for each vertex in $V$.
 Let $V_x$ stand for the set of all vertices adjacent to $x$ in an
undirected graph $G$ or the set of all vertices that are successors
of $x$ in a directed graph $G$.
 If we give both the vertex set $v$ and the collection $A=\{ V_x x \in V \}$ of adjacency sets
for each vertex in then we have given enough information to define
the graph $G$.
Graph Representations: Adjacency Lists
 Another family of representations for a graph uses adjacency
lists (λίστες γειτνίασης) to represent the adjacency set $V_x$ for
each vertex $x$ in the graph.
Example Directed Graph
Example Directed Graph
Example Undirected Graph
Graph Searching
 To search a graph $G$, we need to visit all vertices of $G$ in some
systematic order.
 Each vertex $v$ can be a structure with a
bool
valued member
$v$. Visited which is initially false
for all vertices of $G$. When we
visit $v$, we will set it to true
.
An Algorithm for Graph Searching
// Ψευδοκώδικας, επίσκεψη όλων των κόμβων του γράφου
void graph_search(G) {
Let G = (V,E) be a graph
Let C be an empty container
for (each vertex x in V) {
x.visited = false;
}
Insert v into C;
while (C is nonempty) {
Remove a vertex x from container C;
if (!x.visited) {
visit(x);
x.visited = true;
for (each vertex w adjacent to x) {
if (!w.visited))
Insert w into C;
}
}
}
}
Graph Searching
Interesting case: the container $C$ is a stack.
In what order vertices are visited?
Graph Searching
Eg. the container $C$ is a stack.
The vertices are visited in the order 1, 4, 8, 7, 3, 2, 6, 5.
DepthFirst Search (DFS)
 When $C$ is a stack, the tree in the previous example is searched
in depthfirst order.
 Depthfirst search (αναζήτηση πρώτα κατά βάθος) at a vertex
always goes down (by visiting unvisited children) before going
across (by visiting unvisited brothers and sisters).
 Depthfirst search of a graph is analogous to a preorder
traversal of an ordered tree.
Graph Searching
Another interestg case: the container $C$ is a queue.
What is the order vertices are visited?
Graph Searching
Another interestg case: the container $C$ is a queue.
The vertices are visited in the order 1, 2, 3, 4, 5, 6, 7 and 8.
BreadthFirst Search (BFS)
 When $C$ is a queue, the tree in the previous example is searched
in breadthfirst order.
 Breadthfirst search (αναζήτηση πρώτα κατά πλάτος) at a vertex
always goes broad before going deep.
 Breadthfirst traversal of a graph is analogous to a traversal of an
ordered tree that visits the nodes of the tree in levelorder.
 BFS subdivides the vertices of a graph in levels. The starting
vertex is at level 0, then we have the vertices adjacent to the
starting vertex at level 1, then the vertices adjacent to these
vertices at level 2 etc.
Example
What is the order of visiting vertices for DFS?
Example
Depthfirst search visits the vertices in the order 1, 4, 8, 6, 5, 7, 3 and 2
Example
What is the order of visit for BFS?
Example
Breadthfirst search visits the vertices in the order 1, 2, 3, 4, 5, 6,
7 and 8.
Exhaustive Search
 Either the stack version or the queue version of the algorithm
GraphSearch
will visit every vertex in a graph $G$ provided that $G$
consists of a single strongly connected component.
 If this is not the case, then we can enumerate all the vertices of $G$
and run
GraphSearch
starting from each one of them in order to visit
all the vertices of $G$.
Exhaustive Search
void graph_exhaustive_search(G) {
Let G = (V,E) be a graph.
for (each vertex v in G) {
graph_search(G, v)
}
}
Recursive DFS
 DFS can be also written recursively
 The stack is essentially replaced by the function call stack
Recursive DFS
// Ψευδοκώδικας, επίσκεψη όλων των κόμβων του γράφου
void graph_dfs(G) {
for (each vertex x in V) {
x.visited = false;
}
for (each vertex x in V) {
if (!x.visited))
traverse(G, x);
}
}
void traverse(G, x) {
visit(x);
x.visited = true;
for (each vertex w adjacent to v) {
if (!w.visited))
traverse(G, w);
}
}
Example of Recursive DFS
What is the order vertices are visited?
Example
The vertices are visited in the order 1, 2, 5, 6, 3, 4, 7 and 8. This is
different than the order we got when using a stack!
Complexity of DFS
 DFS as implemented above (with adjacency lists) on a graph with $e$
edges and $n$ vertices has complexity $O(n + e)$.
 To see why observe that on no vertex is
traverse
called more than
once, because as soon as we call traverse
with parameter $x$ , we mark $x$
visited and we never call traverse
on a vertex that has previously
been marked as visited.
 Thus, the total time spent going down the adjacency lists is
proportional to the lengths of those lists, that is $O(e)$
 The initialization steps in
graph_dfs
have complexity $O(n)$
 Thus, the total complexity is $O(n+e)$
Complexity of DFS
 If DFS is implemented using an adjacency matrix, then its complexity
will be $O(n^2)$.
 If the graph is dense (πυκνός), that is, it has close to $O(n^2)$ edges
the difference of the two implementations is minor as they would
both run in $O(n^2)$ time.
 If the graph is sparse (αραιός), that is, it has close to $O(n)$ edges,
then the adjacency matrix approach would be much slower than the
adjacency list approach.
Complexity of BFS
 BFS with adjacency lists has the same
complexity as DFS i.e., $O(n+e)$.
Readings

T. A. Standish. Data Structures , Algorithms and Software Principles in C.
Chapter 10

R. Kruse and C.L. Tondo and B. Leung. Data Structures and Program Design in C. 2nd edition.
Chapter 11

A. V. Aho, J. E. Hopcroft and J. D. Ullman. Data Structures and Algorithms.
Chapters 6 and 7

M. T. Goodrich, R. Tamassia and D. Mount. Data Structures and Algorithms in C++. 2nd edition.
Chapter 13