Graphs and Graph Algorithms - PowerPoint Presentation, Algorithms, Engg. Notes | EduRev

: Graphs and Graph Algorithms - PowerPoint Presentation, Algorithms, Engg. Notes | EduRev

 Page 1


1 	

CSE 421: Intro Algorithms	

Autumn 2012	

Graphs and Graph Algorithms	

Pratik Prasad / Larry Ruzzo	


Page 2


1 	

CSE 421: Intro Algorithms	

Autumn 2012	

Graphs and Graph Algorithms	

Pratik Prasad / Larry Ruzzo	

Goals 	

Graphs: defns, examples, utility, terminology	

Representation: input, internal	

Traversal: Breadth- & Depth-?rst search	

Three Algorithms:	

	

Connected components	

	

Bipartiteness	

	

Topological sort	

2 	


Page 3


1 	

CSE 421: Intro Algorithms	

Autumn 2012	

Graphs and Graph Algorithms	

Pratik Prasad / Larry Ruzzo	

Goals 	

Graphs: defns, examples, utility, terminology	

Representation: input, internal	

Traversal: Breadth- & Depth-?rst search	

Three Algorithms:	

	

Connected components	

	

Bipartiteness	

	

Topological sort	

2 	

 4 	

Objects & Relationships	

The Kevin Bacon Game:	

Obj: Actors	

Rel: Two are related if they've been in a movie together	

Exam Scheduling:	

Obj: Classes	

Rel: Two are related if they have students in common	

Traveling Salesperson Problem:	

Obj: Cities	

Rel: Two are related if can travel directly between them	


Page 4


1 	

CSE 421: Intro Algorithms	

Autumn 2012	

Graphs and Graph Algorithms	

Pratik Prasad / Larry Ruzzo	

Goals 	

Graphs: defns, examples, utility, terminology	

Representation: input, internal	

Traversal: Breadth- & Depth-?rst search	

Three Algorithms:	

	

Connected components	

	

Bipartiteness	

	

Topological sort	

2 	

 4 	

Objects & Relationships	

The Kevin Bacon Game:	

Obj: Actors	

Rel: Two are related if they've been in a movie together	

Exam Scheduling:	

Obj: Classes	

Rel: Two are related if they have students in common	

Traveling Salesperson Problem:	

Obj: Cities	

Rel: Two are related if can travel directly between them	

5 	

Graphs	

	

An extremely important formalism for 
representing (binary) relationships	

Objects: "vertices," aka "nodes"	

Relationships between pairs: "edges," aka 
"arcs"	

Formally, a graph G = (V, E) is a pair of sets, 
V the vertices and E the edges	


Page 5


1 	

CSE 421: Intro Algorithms	

Autumn 2012	

Graphs and Graph Algorithms	

Pratik Prasad / Larry Ruzzo	

Goals 	

Graphs: defns, examples, utility, terminology	

Representation: input, internal	

Traversal: Breadth- & Depth-?rst search	

Three Algorithms:	

	

Connected components	

	

Bipartiteness	

	

Topological sort	

2 	

 4 	

Objects & Relationships	

The Kevin Bacon Game:	

Obj: Actors	

Rel: Two are related if they've been in a movie together	

Exam Scheduling:	

Obj: Classes	

Rel: Two are related if they have students in common	

Traveling Salesperson Problem:	

Obj: Cities	

Rel: Two are related if can travel directly between them	

5 	

Graphs	

	

An extremely important formalism for 
representing (binary) relationships	

Objects: "vertices," aka "nodes"	

Relationships between pairs: "edges," aka 
"arcs"	

Formally, a graph G = (V, E) is a pair of sets, 
V the vertices and E the edges	

6 	

Undirected Graph   G = (V,E)	

1 
2 
10 
9 
8 
3 
4 
5 
6 
7 
11 
12 
13 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!