[go: up one dir, main page]
Scribd
Upload
29 views25 pages

Graph Traversals

The document discusses graph traversal, which involves visiting every vertex and edge in a defined order, and highlights two primary methods: Breadth First Search (BFS) and Depth First Search (DFS). It outlines the algorithms for both methods, their applications, and provides examples of how to implement BFS and DFS on a given graph. The document emphasizes the importance of the order of vertex visits based on the chosen algorithm.

Uploaded by

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

Graph Traversals

The document discusses graph traversal, which involves visiting every vertex and edge in a defined order, and highlights two primary methods: Breadth First Search (BFS) and Depth First Search (DFS). It outlines the algorithms for both methods, their applications, and provides examples of how to implement BFS and DFS on a given graph. The document emphasizes the importance of the order of vertex visits based on the chosen algorithm.

Uploaded by

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

Graph Traversals

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 1


Graph traversal means visiting every vertex and edge
exactly once in a well-defined order.

While using certain graph algorithms, you must ensure


that each vertex of the graph is visited exactly once.

The order in which the vertices are visited are important


and may depend upon the algorithm or question that you
are solving.

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 2


Two methods of traversing a graph:
1) Breadth First Search (BFS)
2) Depth First Search (DFS)

Both these methods consider the graph nodes to be in


one of the following states at any given point of time:

1) Ready state (initial state of node N)


2) Waiting state (Node N is in the queue or stack waiting
to be processed)
3) Processed state (Node N has been processed)

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 3


Breadth First Search (BFS) - ALGORITHM
1) Create the adjacency list
2) Start by pushing starting vertex of the graph into
the queue
3) Remove the front element of the queue and add it
to the visited list
4) Add the non-visited nodes to the queue
5) Keep repeating steps 2 and 3 until the queue is
empty

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 4


Breadth First Search (BFS) – Applications
• Un-weighted Graphs: BFS algorithm can easily create the
shortest path and a minimum spanning tree to visit all the
vertices of the graph in the shortest time possible with high
accuracy.
• P2P Networks: BFS can be implemented to locate all the
nearest or neighboring nodes in a peer to peer network.
This will find the required data faster.
• Web Crawlers: Search engines or web crawlers can easily
build multiple levels of indexes by employing BFS. BFS
implementation starts from the source, which is the web
page, and then it visits all the links from that source.

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 5


• Navigation Systems: BFS can help find all the
neighboring locations from the main or source
location.
• Network Broadcasting: A broadcasted packet is
guided by the BFS algorithm to find and reach all
the nodes it has the address for.

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 6


Example: Implement BFS traversal on the following graph

A C B

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 7


We first prepare the adjacency list

S : A, B, C
A: S, D
B: S, D
C: S, D
D: A, B, C

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 8


Step 1: We select vertex S as starting vertex
insert S in QUEUE

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 9


Step 2: Remove front node S; process it; change its status to
processed state;
Insert in QUEUE all adjacent vertices of S

B
A Processed: S

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 10


Step 2: Remove front node A; process it; change its status to
processed state;
Insert in QUEUE all adjacent vertices of A

D
C

B
Processed: S, A

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 11


Step 2: Remove front node B; process it; change its status to
processed state;
Insert in QUEUE all adjacent vertices of B

D
C

Processed: S, A, B

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 12


Step 2: Remove front node C; process it; change its status to
processed state;
Insert in QUEUE all adjacent vertices of C

Processed: S, A, B, C

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 13


Step 2: Remove front node D; process it; change its status to
processed state;
Insert in QUEUE all adjacent vertices of D

Processed: S, A, B, C, D

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 14


Since QUEUE is empty and no more vertices to
be visited – the BFS Traversal is

SA B C D

Meaning these are nodes reachable from


starting vertex S

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 15


Depth First Search (DFS) - ALGORITHM
1) Create the adjacency list
2) Start by pushing starting vertex of the graph into
the stack
3) Pop the top item of the stack and add it to the
visited list
4) Add the non-visited nodes in the list to the top of
the stack
5) Keep repeating steps 2 and 3 until the stack is
empty

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 16


Example: Implement DFS traversal on the following graph

A C B

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 17


We first prepare the adjacency list

S : A, B, C
A: S, D
B: S, D
C: S, D
D: A, B, C

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 18


Step 1: We select vertex S as starting vertex
push S onto STACK

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 19


Step 2: Pop S; push all neighbors of S onto STACK

C
Popped Elements: S
B
A

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 20


Step 2: Pop C; push all neighbors of C onto STACK

D
Popped Elements: S, C
B
A

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 21


Step 2: Pop D; push all neighbors of D onto STACK

Popped Elements: S, C, D
B
A

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 22


Step 2: Pop B; push all neighbors of B onto STACK

Popped Elements: S, C, D, B

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 23


Step 2: Pop A; push all neighbors of A onto STACK

Popped Elements: S, C, D, B, A

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 24


Stack is EMPTY and no more vertex to visit

Nodes are processed in the following order

Actual Output: S C D B A

Prof. N. Guruprasad INT to DS & Algorithms – GRAPHS 25

You might also like