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 13Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!