Graph

Topics
• Graph
• Implementation of graph
• Graph Traversals
– Breadth-first search (BFS)
– Depth-first search (DFS)

2
 Graphs
A graph consists of a set of nodes or vertices together
with a set of edges or arcs where each edge joins two
vertices.
A graph G = (V,E) is composed of:
• V: set of vertices
• E: set of edges connecting the vertices in V
• An edge e = (u,v) is a pair of vertices
• Example:
V= {a,b,c,d,e}
E= { (a,b), (a,c), (a,d), (b,e),
(c,d),(c,e), (d,e) }
3
 Terminologies
Path: a sequence of vertices that connect two nodes in a graph
cycle is a simple path with the same start and end vertex.
Path length: the number of edges in the path
simple path : repeats no vertices (except that the first can also be the last)
- Cycle is a cycle that is also a simple path (in undirected graphs, no edge can
be repeated)
Path cost:
the sum of the costs of each edge

• The indegree of a node v is the number of distinct edges (w,v)E.

• The outdegree of a node v is the number of distinct edges (v,w)E.

• node with indegree 0 is a root.

4
 Connections of graph
• Undirected Connected graph:
▪ For any vertices x, y there exists a path: x→y (= y→x)
• Directed connected graph:
▪ In directed graphs, edges have a direction
• Strongly connected directed graph:
– If for any two vertices x, y ,
– Exisist a path x→y and path y→x X
• weakly connected Directed graphs :
if there is a path between any
Y
two vertices, ignoring direction
Simple Graphs: have no loops and no repeated edges
Complete graph:
a graph in which every vertex is directly
connected to every other vertex.
And has an edge between every pair of vertices
5
 Terminologies
Adjacent nodes: two nodes are adjacent if they are connected
by an edge. Vertices adjacent to a given vertex are called its
neighbors.
X Y
X is adjacent to Y

Loops: edges that connect a vertex to itself.

Multiple Edges: two nodes may be connected by >1 edge
6
 Terminologies
• Weighted graph: a graph in which each edge carries a value
• subgraph: subset of vertices and edges forming a graph
• connected component: maximal connected subgraph.
• E.g., the graph has 3 connected components
• Graph with no cycles: acyclic
• Directed Acyclic Graph: DAG 20
X Y

• NOTES :
Every tree is a graph with some restrictions:
–the tree is directed there are no cycles (directed or undirected)
–there is a directed path from the root to every node

7
 Cycle

Simple path ceb

Connected graph Non-Connected graph

Simple path
Cycle path abc

Connected path

8
Non Connected path
 Degree of Graphs
Degree of a node X:
The degree of a vertex is the number of edges incident to that vertex
• The degree of vertex i is the no. of edges incident on vertex i.
• e.g., degree(2) = 2, degree(5) = 3, degree(3) = 1
Out-degree: number of edges < X, v2 >
In-degree: number of edges < v1, X >
Degree: In-degree + Out-degree
• A dag is a directed acyclic graph.
• tree : connected graph without cycles.
▪ A tree is a connected acyclic undirected graph.
• Forest : collection of trees
• Undirected forest: Acyclic undirected graph
• A forest is an acyclic undirected graph (not necessarily
connected), i.e., each connected component is a tree.
9
 Degree of Graphs
• The no. of possible pairs in an n vertex graph is n*(n-1)
• Since edge (u,v) is the same as edge (v,u), the
• number of edges in an undirected graph is
n*(n-1)/2
• The no. of possible pairs in an n vertex graph is
• n*(n-1)
• Since edge (u,v) is not the same as edge (v,u), the
• number of edges in a directed graph is n*(n-1)
• Thus, the number of edges in a directed graph is ≤ n*(n-1)

10
 Graph Traversals (Search)
• Graphs can be represented using
• adjacency matrix or adjacency list
1. Adjacency matrix : two dimensional array in
which elements indicate whether an edge is
present between two vertices.
– Edge is represented by 1.
– Or Edge is represented by weight

2. Adjacency List : array of lists.

– Each individual list shows what vertices a given
vertex is adjacent to.

12
 Adjacency matrix examples
EX: 3
EX:1 EX:2 Adjacency Matrix
-Directed multigraphs
 Examples

1 2 1

3 2 3
4
1 2 3 1 2 3 4
1 0 0 1 1 0 1 1 0
2 0 1 0 2 1 0 0 0
3 1 1 0 3 1 0 0 0
4 0 0 0 0 15
 Examples of Graphs
The web
–Vertices are webpages
–Each edge is a link from one page to another
Call graph of a program
–Vertices are subroutines
–Edges are calls and returns
Social networks
–Vertices are people
–Edges connect friends
networks (roads, flights, communications)

16
 Why do we need graphs?
1) Graphs find their importance in many types of applications,
Some examples are:
2) In a telephone system, finding the least congested route
between two phones, given connections between
switching stations.
3) On the web, determine if there is a way to get to one
page from another, just by following normal links.
4) While driving, find the shortest path from one city to
another.
5) As a traveling salesperson who needs to visit a number
of cities, find the shortest path that includes all the
cities.
6) Determine an ordering of courses so that you always
take prerequisite courses first.
17
 Graph Traversals (Search)
• we first have to build a graph by starting with a set of nodes
and adding in any edges we need. The information that we
need to know :
• “Is this graph connected?”
• “What is the shortest path in this graph from s to t?”,
• “How many edges can I remove from this graph before some nodes
become unreachable from other nodes?”
• the information these algorithms need is typically
• (a) given a vertex u, what successors does it have; and sometimes
• (b) given vertices u and v, does the edge (u, v) exist in the graph?
• graph of n nodes is represented by a one dimensional array L of linked
lists, where
• L[i] is the linked list containing all the nodes adjacent
• from node i.
• The nodes in the list L[i] are in no particular order
18
 ADT for Graph
• functions: for all graph Î Graph, v, v1 and v2 Î Vertices
• Graph Create()::=return an empty graph
• Graph InsertVertex(graph, v):: = return a graph with v inserted. v has
no
• incident edge.
• Graph InsertEdge(graph, v1,v2)::= return a graph with new edge
• between v1 and v2
• Graph DeleteVertex(graph, v)::= return a graph in which v and all
edges
• incident to it are removed
• Graph DeleteEdge(graph, v1, v2)::= return a graph in which the edge
(v1, v2)
• is removed
• Boolean IsEmpty(graph):: = if (graph==empty graph) return TRUE
• else return FALSE
• List Adjacent(graph,v):: = return a list of all vertices that are adjacent
to v
19
Consider the directed graphs of Figure,
shows the adjacency list of the
directed graph

Operations on graph
[Link] the graph. That is, store the
graph in computer memory using a
particular graph representation.

2. Clear the graph. This operation

makes the graph empty.

3. Determine whether the graph is

empty.

4. Traverse the graph.

5. Print the graph

 implementation of Graph using List
4
1

2 5

6
7 implementation of Graph using List 8

9
 Graph Traversals (Search)
• Problem: Search for a certain node or traverse all
nodes in the graph.
• solve : using any of several standard graph search
algorithms
– Breadth-first search (BFS)
– Depth-first search (DFS)
• A traversal (search):
– An algorithm for systematically exploring a graph
– Visiting (all) vertices Until finding a goal vertex or until no
more vertices Only for connected graphs
• BFS finds shortest path from s to each vertex
– Shortest in terms of number of edges
24
 Breadth-first search
• One of the simplest algorithms
• Also one of the most important
– It forms the basis for MANY graph algorithms
• BFS: Level-by-level traversal
• Given a starting vertex s
• Visit all vertices at increasing distance from s
– Visit all vertices at distance k from s
– Then visit all vertices at distance k+1 from s , Then ….
• BFS for general graphs assumes vertices have two children :
– left, right ,This is trivial to fix
• But still no good for general graphs
• It does not handle cycles. (disadvantage)
• Complexity: O(|V| + |E|)
• DFS is a real workhorse: has many variants that solve a
number of computational graph theory problems.
25
 BFS
BFS: visit all siblings before their descendents

Reminder
L1 BFS: Level-by-level traversal

5
L2
2 8
L3
1 3 6 10

L4
7 9
5 2 8 1 3 6 10 7 9
26
 Cycle graph

B E

D
G C

F
ABEGCDF
Suppose we now want to expand C. We put F in again!
27
 BFS
• Implemented with a queue.
• Stays as close as possible to the starting point.
• Visits all the vertices adjacent to the starting vertex
• every node in the graph is processed and no node is processed
more than once.
• DSF application -> display visited edges
• Example Application: Reduce paths and pins in VLSI (Chip)
design and fabrication
Steps:
- start with visiting a starting vertex
-visit the next unvisited adjacent
vertex, mark it and insert it into the
queue.
- if there are no unvisited vertices,
remove a vertex from the queue and
make it the current vertex.
- continue until you reach the end.
28
 Breadth First Search Algorithm
BFS(G,s):
1) Let L0 be empty
2) Insert s into L0.
3) Let i = 0
4) While Li is not empty do the following:
A) Create an empty container Li+1.
B) For each vertex v in Li do
i) For all edges e incident to v
a) if e is unexplored, mark endpoint w.
b) if w is unexplored
Mark it.
Insert w into Li+1.
Label e as a discovery edge.
else
Label e as a cross edge.
C) i = i+1
29
 Depth-first search
• Again, a simple and powerful algorithm
• Given a starting vertex s
• Pick an adjacent vertex, visit it.
– Then visit one of its adjacent vertices, Until impossible, then
backtrack, visit another
– DFS does not necessarily find shortest path
– Complexity: O(|V| + |E|)

There are 3 rules

- start with a vertex
R1 go to any vertex adjacent to it that hasn’t yet been
visited , push it on a stack and mark it
R2 if can’t follow R1, then possible pop up a vertex off
the stack
R3 if can’t follow R1 and R2, you’re done
30
 Example : Depth-first search
1 A
2
5
B E
3 6
G 7 C D

Start with A. Mark it.

Expand A’s adjacent vertices. Pick one (B).
4
F
Mark it and re-visit.
Now expand B, and visit its neighbor, C.
Visit F. Pick one of its neighbors, E.
E’s adjacent vertices are A, D and F. Done. We have explored the graph in orde
A and F are marked, so pick D.
Visit D. No new vertices available. Backtrack to ABCFEDG
E. Backtrack to F. Backtrack to C. Backtrack to B.
Visit G. No new vertices from here. Backtrack to
B. Backtrack to A. E already marked so no new.
31
 Depth First Search Algorithm
DFS(Graph G,vertex v):
For all edges e incident to
the start vertex v do:
1) If e is unexplored
a) Let e connect v to w.
b) If w is unexplored
i) Label e as a discovery edge
ii) Recursively call DFS(G,w)
else
iii) Label e as a back edge

32