Scribd
Upload
182 views19 pages

Graph and Graph Traaversals

The document discusses graphs and graph traversal algorithms. It defines directed and undirected graphs, weighted graphs, and different graph representations. It then describes depth-first search (DFS) and breadth-first search (BFS) algorithms for traversing graphs, including pseudocode for BFS. DFS traces paths in a graph by going deep down one branch before backtracking, while BFS searches level-by-level from neighboring to distant nodes.

Uploaded by

gopitheprince
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
182 views19 pages

Graph and Graph Traaversals

The document discusses graphs and graph traversal algorithms. It defines directed and undirected graphs, weighted graphs, and different graph representations. It then describes depth-first search (DFS) and breadth-first search (BFS) algorithms for traversing graphs, including pseudocode for BFS. DFS traces paths in a graph by going deep down one branch before backtracking, while BFS searches level-by-level from neighboring to distant nodes.

Uploaded by

gopitheprince
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 19

Graph and Graph Traaversals

• Definitions and Representations


• Traversing Graphs
• Depth-First Search on Directed Graphs
• Strongly Connected Components of a Directed Graph
• Depth-First Search on Undirected Graphs
• Biconnected Components of an
Undirected Graph
Problems: e.g. Airline Routes
Problems: e.g. Computer Networks
Definition: Directed graph
• Directed Graph
A directed graph, or digraph, is a pair
G = (V, E)
where V is a set whose elements are called vertices, and
E is a set of ordered pairs of elements of V.

 Vertices are often also called nodes.


 Elements of E are called edges, or directed edges, or arcs.
 For directed edge (v, w) in E, v is its tail and w its head;
 (v, w) is represented in the diagrams as the arrow, v -> w.
 In text we simple write vw.
Definition: Undirected graph
• Undirected Graph
A undirected graph is a pair
G = (V, E)
where V is a set whose elements are called vertices, and
E is a set of unordered pairs of distinct elements of V.

 Vertices are often also called nodes.


 Elements of E are called edges, or undirected edges.
 Each edge may be considered as a subset of V containing two
elements,
 {v, w} denotes an undirected edge
 In diagrams this edge is the line v---w.
 In text we simple write vw, or wv
 vw is said to be incident upon the vertices v and w
Definitions: Weighted Graph
• A weighted graph is a triple (V, E, W)
where (V, E) is a graph (directed or undirected) and
W is a function from E into R, the reals (integer or
rationals).
For an edge e, W(e) is called the weight of e.
Graph Representations using Data Structures
• Adjacency Matrix Representation
Let G = (V,E), n = |V|, m = |E|, V = {v1, v2, …, vn)
G can be represented by an n  n matrix
Adjacency Matrix for weight digraph
Array of Adjacency Lists Representation
• From
to
Array of Adjacency Lists Representation

from -> to, weight


More Definitions
• Subgraph
• Symmetric digraph
• complete graph
• Adjacency relation
• Path, simple path, reachable
• Connected, Strongly Connected
• Cycle, simple cycle
• acyclic
• undirected forest
• free tree, undirected tree
• rooted tree
• Connected component
Traversing Graphs
• Most algorithms for solving problems on a graph
examine or process each vertex and each edge.
• Breadth-first search and depth-first search
are two traversal strategies that provide an efficient way
to “visit” each vertex and edge edge exactly once.
• Breadth-first search: Strategy (for digraph)
choose a starting vertex, distance d = 0
vertices are visited in order of increasing distance from
the starting vertex,
examine all edges leading from vertices (at distance d)
to adjacent vertices (at distance d+1)
then, examine all edges leading from vertices at distance
d+1 to distance d+2, and so on,
until no new vertex is discovered
Breath-first search, e.g.
• e.g. Start from vertex A, at d = 0
visit B, C, F; at d = 1
visit D; at d = 2
• e.g. Start from vertex E, at d = 0
visit G; at d = 1
Algorithm for BFS

Algorithm BFS & DFS


Depth-first search for digraph, e.g.
from a tree, remember where we have been

and so on…
Depth-first Search, e.g. trace it, in order
• Vertex status: undiscovered, discovered, finished
• Edge status: exploring, backtrack, checked
Depth-first search tree
• edges classified:
tree edge, back edge, descendant edge, and cross edge
• Algorithm BFS & DFS

You might also like