Review: Graph Theory and RepresentationGraph Algorithms• Graphs and Theorems about Graphs• Graph implementation• Graph Algorithms– Shortest paths– Minimum spanning treeWhat can graphs model?•Cost of wiring electronic components together.•Shortest route between two cities.•Finding the shortest distance between all pairs of cities in a road atlas.•Flow of material: liquid flowing through pipes, current through electrical networks, information through communication networks, parts through an assembly line, etc.•State of a machine.•Used in Operating systems to model resource handling (deadlock problems).•Used in compilers for parsing and optimizing the code.What is a Graph?• Informally a graphis a set of nodes joined by a set of lines or arrows.1123445 56 623A directed graph,also called a digraphG, is a pair (V, E ) where Vis a finite set of vertices and Eis a set of directed edges. An edge from node ato node bis denoted by the ordered pair (a, b).12345 6V = { 1, 2, 3, 4, 5, 6, 7 }| V | = 7E = { (1,2), (2,2), (2,4), (4,5), (4,1), (5,4),(6,3) }| E | = 7Self loop7Isolated nodeUndirected graph G= (V , E): Unlike a digraph, Econsists of undirected edges. So, edge (A,B) = edge (B, A).ADE FBCV = { A, B, C, D, E, F }|V | = 6E = { {A, B}, {A,E}, {B,E}, {C,F} }|E | = 4-Thedegreeof a vertex in an undirected graph is the number of edges incident on it. - In a directed graph, the out degree of a vertex is the number of edges leaving it and the in degreeis the number of edges entering it.ADE FBCThe degree of B is 2.1245The in degree of 2 is 2 andthe out degree of 2 is 3.Self-loopCyclic and Acyclic A path from a vertex to itself is called a cycle(e.g., v1  v2  v4  v1)If a graph contains a cycle, it is cyclicOtherwise, it is acyclicA path is simple if it never passes through the same vertex twice.1245A pathis a sequence of vertices such that there is an edge from each vertex to its successor. A path from a vertex to itself is called a cycle. A graph is called cyclicif it contains a cycle; otherwise it is called acyclic. A path is simpleif each vertex is distinct.12345 6ADE FBCCycleSimple path from 1 to 5 = ( 1, 2, 4, 5 )or as in our text ((1, 2), (2, 4), (4,5))UnreachableCycleIf there is path pfrom uto vthen we say vis reachable from uvia p.Simple Graphs Simple graphsare graphs without multiple edges or self-loops. We will consider only simple graphs.Proposition: If G is an undirected graph thenΣ deg(v) = 2 |E|Proposition: If G is a digraph thenΣ indeg(v) = Σ outdeg(v) = |E| v ∈ Gv ∈ Gv ∈ GA weighted graphis a graph for which each edge has an associated weight, usually given by a weight function w: E→ R.12345 6.51.2.2.51.5.3145 6232135If (u, v) is an edge in a graph G, we say that vertex vis adjacentto vertex u.A Complete graphis an undirected/directed graph in which every pair of vertices is adjacent. ADEB4 nodes and (4*3)/2 edgesV nodes and V*(V-1)/2 edges DAB3 nodes and 3*2 edgesV nodes and V*(V-1) edgesAn undirected graph is connectedif you can get from any node to any other by following a sequence of edges, i.e., a path.A directed graph is strongly connectedif there is a directed path from any node to any other node.• A graph is sparseif | E| ≈ | V|• A graph is denseif | E| ≈ | V|2.ADE FBC1245A bipartite graphis an undirected graph G= (V,E) in which Vcan be partitioned into 2 sets V1and V2such that (u,v) ∈Eimplies either u∈V1and v∈V2 OR v∈V1and u∈V2.Set 1Set 2A free treeis an acyclic, connected, undirected graph. A forestis an acyclic undirected graph. A rooted treeis a tree with one distinguished node, root.Let G = (V, E) be an undirected, acyclic, connected graph. The following statements are equivalent.1. Gis a tree2. Any two vertices in Gare connected by unique simple path.3. Gis connected, but if any edge is removed from E, the resulting graph is disconnected.4. G is connected, and | E| = | V| -15. G is acyclic, and | E| = | V| -16. G is acyclic, but if any edge is added to E, the resulting graph contains a cycle.Implementation of a Graph.•Adjacency-list representation of a graph G =(V, E) consists of an array ADJ of |V| lists, one for each vertex in V. For each u∈V, ADJ[ u] points to all its adjacent vertices.15122544332 51 5 3 42 4245132Adjacency-list representation for a directed graph.15122544332 55 3 4455Variation: Can keep a second list of edges coming into a vertex.Adjacency lists• Property–Saves space for sparse graphs. Most graphs are sparse.– “Visit”edges that start at v• Must traverse linked list of v• Size of linked list of v is degree(v)• Order: Θ(degree(v))Adjacency List• Storage–We need V pointers to linked lists–For a directed graph the number of nodes (or edges) contained (referenced) in all the linked lists is Σ(out-degree (v)) = | E|. So we need Θ( V + E) –For an undirected graph the number of nodes isΣ(degree (v)) = 2 | E|Also Θ( V + E)v ∈ Vv ∈ VAdjacency-matrix representation of a graph G= (V, E) is a |V| x |V | matrix A = ( aij) such that aij= 1 if (i, j) ∈Eand 0 otherwise.041320 1 2 3 4 012340 1 0 0 11 0 1 1 10 1 0 1 00 1 1 0 11 1 0 1 0Adjacency Matrix Representation for a Directed Graph0 1 0 0 10 0 1 1 10 0 0 1 00 0 0 0 10 0 0 0 00 1 2 3 4 0123404132Adjacency Matrix Representation• Advantage:–Saves space on pointers for dense, un-weightedgraphs –Just one bit per matrix element–Faster lookup• Is there an edge (v, u)?  adjacency [i] [j] == true?• So θ(1)• Disadvantage:–Waste space for sparse, weighted graphs• Size of the adjacency matrix is |V|2 – “Visit”all the edges that start at v• Row v of the matrix must be traversed. • So θ(|V|).Adjacency Matrix Representation• Storage – Θ(V2)– For undirected graphs you can only use 1/2(V2) storage, since the adjacency matrix of an undirected graph is symmetricGraph traversals•Breadth first search•Depth first searchBreadth first search• Given a graph G=(V,E) and a source vertex s, BFS explores the edges of G to visit each node of G reachable from s.• Idea - Expand a frontierone step at a time.•Frontieris a FIFO queue –O(1) time to updateBreadth first search• Computes the shortest distance(dist) from sto any reachable node • Computes a breadth first tree(of parents) with root sthat contains all the