GraphGraph AlgorithmsWhat can graphs model?What is a Graph?Directed GraphSlide 6Undirected GraphSlide 8DegreeSlide 10Slide 11Weighted GraphSlide 13Implementation of a GraphSlide 15Slide 16Adjacency listsAdjacency-matrix-representationSlide 19Slide 20Slide 21GraphDr. Bernard Chen Ph.D.University of Central ArkansasFall 2008Graph AlgorithmsGraphs and Theorems about GraphsGraph ADT and implementationGraph AlgorithmsShortest pathsminimum 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.What is a Graph?Informally a graph is a set of nodes joined by a set of lines or arrows.1123445 56 62 3Directed GraphA directed graph is a pair ( V, E ), where the set V is a finite set and E is a binary relation on V . The set V is called the vertex set of G and the elements are called vertices. The set E is called the edge set of G and the elements are edgesDirected Graph12345 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 GraphAn undirected graph G = ( V , E ) , but unlike a digraph the edge set E consist of unordered pairs. We use the notation (a, b ) to refer to a directed edge, and { a, b } for an undirected edge.Undirected GraphADEFBCV = { A, B, C, D, E, F } |V | = 6E = { {A, B}, {A,E}, {B,E}, {C,F} } |E | = 4Some texts use (a, b) also for undirected edges. So ( a, b ) and ( b, a ) refers to the same edge.DegreeDegree of 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 degree is the number of edges entering it.DegreeADEFBCThe degree of B is 2.Degree1245The in degree of 2 is 2 andthe out degree of 2 is 3.Weighted GraphA weighted graph is 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.3Weighted GraphImplementation of a GraphAdjacency-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.Implementation of a Graph15122544332 51 5 3 42 4245132Implementation of a Graph15122544332 55 3 4455Adjacency listsAdvantage: Saves space for sparse graphs. Most graphs are sparse.“Visit” edges that start at vMust traverse linked list of vSize of linked list of v is degree(v)(degree(v))Adjacency-matrix-representationAdjacency-matrix-representation of a graph G = ( V, E) is a |V | x |V | matrix A = ( aij ) such that aij = 1 (or some Object) if (i, j ) E 0 (or null) otherwise.Adjacency-matrix-representation04132 0 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-representation0 1 0 0 10 0 1 1 10 0 0 1 00 0 0 0 10 0 0 0 0 0 1 2 3 4 0123404132Advantage:Saves space on pointers for dense graphs, and onsmall unweighted graphs using 1 bit per edge.Check for existence of an edge (v, u) (adjacency [i] [j]) == true?)So
View Full Document