1
Graphs
(Chapter 9)
,2
Outline
• Introduction
• Definitions and Basic Terminologies
• Representations of Graphs
• Graph Traversals
Breadth First Traversal
Depth First Traversal
• Applications
Single Source Shortest Path Problem
Minimum Cost Spanning Trees
• ADT for graphs
,3
• The history of graphs dates back to 1736 in what is now
referred to as the classical Koenigsberg bridge problem.
• Euler solved the problem with a theory that laid the
foundation for graph theory
Graphs
(Chapter 9)
,2
Outline
• Introduction
• Definitions and Basic Terminologies
• Representations of Graphs
• Graph Traversals
Breadth First Traversal
Depth First Traversal
• Applications
Single Source Shortest Path Problem
Minimum Cost Spanning Trees
• ADT for graphs
,3
• The history of graphs dates back to 1736 in what is now
referred to as the classical Koenigsberg bridge problem.
• Euler solved the problem with a theory that laid the
foundation for graph theory
