Graph AlgorithmsCourse SyllabusGraph PreliminariesGraph TerminologiesGraph Terminologies (Contd)Graph TerminologiesPaths and CyclesPaths and CyclesSlide Number 9Spanning TreeConnectivityConnectivityGraph RepresentationsGraph RepresentationsDepth-first searchDFSDFSDFS BFSBFSSlide Number 22DFS and BFSConnected Components of a GraphSlide Number 25DFS ForestDFS Forest QuestionsMinimum-Cost Spanning TreesMinimum-Cost Spanning TreesMCSTMCSTKruskal's AlgorithmMCSTMCSTComplexitySlide Number 37Single-Source Shortest Paths Single Source Shortest PathThe single-source shortest paths problem Slide Number 41Slide Number 42Dijkstra's Single-source shortest pathAnalysisAll-Pairs Shortest Path Problem Floyd' s Algorithm for Shortest PathsSlide Number 47Slide Number 48Slide Number 49Slide Number 50Slide Number 51Transitive ClosureWarshall's Algorithm for Transitive Closure Slide Number 54Hamiltonian CycleEuler PathEuler cycleSlide Number 58Slide Number 59Biconnected ComponentsDefinitionsSlide Number 62AlgorithmsBipartite MatchingBipartite MatchingBipartite matchingSlide Number 679/12/2008 M KUMAR CSE5311 1Graph AlgorithmsThis weekGraph terminologyStacks and QueuesBreadth-first-searchDepth-first-searchConnected ComponentsAnalysis of BFS and DFS AlgorithmsChapter 3Algorithm Design Kleinberg and Tardos9/12/2008 M KUMAR CSE5311 2Course Syllabus• Review of Asymptotic Analysis and Growth of Functions, Recurrences• Sorting Algorithms• Graphs and Graph Algorithms.• Greedy Algorithms: – Minimum spanning tree,Union-Find algorithms, Kruskal's Algorithm, – Clustering, – Huffman Codes, and – Multiphase greedy algorithms. • Dynamic Programming: – Shortest paths, negative cycles, matrix chain multiplications, sequence alignment, RNA secondary structure, application examples.• Network Flow: – Maximum flow problem, Ford-Fulkerson algorithm, augmenting paths, Bipartite matching problem, disjoint paths and application problems.• NP and Computational tractability: – Polynomial time reductions; The Satisfiability problem; NP-Complete problems; and Extending limits of tractability.• Approximation Algorithms, Local Search and Randomized Algorithms9/12/2008 M KUMAR CSE5311 3Graph PreliminariesExamples of modeling by GraphsDarwinAdelaideBrisbaneSydneyMelbournePerthModule 1Module3Module 2Module 4Module 5Module 6Module 79/12/2008 M KUMAR CSE5311 4Graph Terminologies• A Graph consists of a set 'V' of vertices (or nodes) and a set 'E' of edges (or links). • A graph can be directed or undirected. • Edges in a directed graph are ordered pairs. • The order between the two vertices is important.– Example: (S,P) is an ordered pair because the edge starts at S and terminates at P.– The edge is unidirectional– Edges of an undirected graph form unordered pairs.• A multigraph is a graph with possibly several edges between the same pair of vertices.• Graphs that are not multigraphs are called simple graphs.9/12/2008 M KUMAR CSE5311 5Graph Terminologies (Contd)G1: Undirected Graph QRTPSG2: Directed Graph DBAEC9/12/2008 M KUMAR CSE5311 6Graph TerminologiesThe degree d(v) of a vertex v is the number of edges incident to v.d (A) = three, d (D) = twoIn directed graphs, indegree is the number of incoming edges at the vertex and outdegree is the number of outgoing edges from the vertex.The indegree of P is 2, its outdegree is 1.The indegree of Q is 1, its outdegree is 1.DBAECQRTPS9/12/2008 M KUMAR CSE5311 7Paths and CyclesA path from vertex v1 to vk is a sequence of vertices v1 ,v2 , …, vk that are connected by edges (v1 ,v2 ), (v2 ,v3 ), …, (vk-1 ,vk ).Path from D to E: (D,A,B,E)Edges in the path: (D,A), (A,B), (B,E)A path is simple if each vertex in it appears only once.DABE is a simple path.ABCDAE is not a simple path.Vertex u is said to be reachable from v if there is a path from v to u.A circuit is a path whose first and last vertices are the same.DAEBCEAD, ABEA, DABECD, SPQRS, STRS are circuitsQRTPSDBAEC9/12/2008 M KUMAR CSE5311 8Paths and CyclesA simple circuit is a cycle if except for the first (and last) vertex, no other vertex appears more than once. ABEA, DABECD, SPQRS, and STRS are cycles.A Hamiltonian cycle of a graph G is a cycle that contains all the vertices of GDABECD is a Hamiltonian cycle of G1PQRSTP is a Hamiltonian of G2. DBAECQRTPS9/12/2008 M KUMAR CSE5311 9A subgraph of a graph G = (V,E) is a graph H(U,F) such that U  V and FE. H1 {[U1:A,E,C,D], F1:[ (A,E),(E,C),(C,D),(D,A)]} is a subgraph of G1H2 {[U2:S,P,T],F2:[(S,P),(S,T),(T,P)]} is a subgraph of G2.Spanning tree of G1DBAECDAECQRTPSTPS9/12/2008 M KUMAR CSE5311 10Spanning TreeA spanning tree of a graph G is a subgraph of G that is a tree and contains all the vertices of G.DBAECDBAECQRTPSSpanning tree of G2QRTPS9/12/2008 M KUMAR CSE5311 11ConnectivityA graph is said to be connected if there is a path from any vertex to any other vertex in the graph.G1 and G2 are both connected graphsA forest is a graph that does not contain a cycle.A tree is a connected forest.QRTCDBAEPSG(A,B,C,D,E,P,Q,R,S,T) is a forest G(A,B,C,D,E) is a tree9/12/2008 M KUMAR CSE5311 12ConnectivityA spanning forest of an undirected graph G is a subgraph of G that is a forest and contains all the vertices of G.If a graph G(V,E) is not connected, then it can be partitioned in a unique way into a set of connected subgraphs called connected components.A connected component of G is a connected subgraph of G such that no other connected subgraph of G contains it.QRTCDBAEPSG(A,B,C,D,E,P,Q,R,S,T) is a forest G(A,B,C,D,E) is a tree (A,B,C,D,E) and (P,Q,R,S,T) are connected components9/12/2008 M KUMAR CSE5311 13Graph RepresentationsDBAECG1: undirected graphAdjacency MatrixA B C D EA 0 1 0 1 1B 1 0 1 0 1C 0 1 0 1 1D 1 0 1 0 0E 1 1 1 0 0Adjacency listA B D EB A C EC B D ED A C \E A B C9/12/2008 M KUMAR CSE5311 14Graph RepresentationsQRTPSG2: DirectedGraphAdjacency matrixP Q R S TP 0 1 0 0 0Q 0 0 1 0 0R 0 0 0 1 0S 1 0 0 0 1T 1 0 1 0 0Adjacency listP Q /Q R /R S /S P TT P R9/12/2008 M KUMAR CSE5311 15Depth-first searchProcedure DFS_Tree G(V,E)Input: G = (V,E); S is a stack - initially empty;’x’ refers to the top of stack;initially mark all vertices ’new’;L[x] refers to the adjacency list of x.T 