Representation of Graphs Suppose,for now,that we can number the vertices, starting at 1;that is,V1,2,...,n One simple way to represent a graph is to use a two- dimensional array this is known as a adjacency matrix representation. For each edge (u,we set A[u][]=1;otherwise the entry in the array is 0. a If the edge has a weight associated with it,then we can set Au][]equal to the weight and use either a very large or a very small weight as a sentinel to indicate nonexistent edges
Representation of Graphs ◼ Suppose, for now, that we can number the vertices, starting at 1; that is, V={1, 2, …, n} ◼ One simple way to represent a graph is to use a twodimensional array this is known as a adjacency matrix representation. ◼ For each edge (u, v), we set A[u][v]=1; otherwise the entry in the array is 0. ◼ If the edge has a weight associated with it, then we can set A[u][v] equal to the weight and use either a very large or a very small weight as a sentinel to indicate nonexistent edges
Representation of Graphs If the number of edges in a graph is very small,a better solution is an adjacency list representation. For each vertex,we keep a list of all adjacent vertices: The leftmost structure is merely an array of header cells.If the edges have weights,then this additional information is also stored in the cells
Representation of Graphs ◼ If the number of edges in a graph is very small, a better solution is an adjacency list representation. ◼ For each vertex, we keep a list of all adjacent vertices: The leftmost structure is merely an array of header cells. If the edges have weights, then this additional information is also stored in the cells
Topological Sort A topological sort is an ordering of vertices in a directed acyclic graph,such that if there is a path from vto v then vappears after v in the ordering. a See Figure 9.3:A directed edge (v,w)indicates that course vmust be completed before course wmay be attempted.A topological ordering of these courses is any course sequence that does not violate the prerequisite requirement
Topological Sort ◼ A topological sort is an ordering of vertices in a directed acyclic graph, such that if there is a path from vi to vj , then vj appears after vi in the ordering. ◼ See Figure 9.3: A directed edge (v, w) indicates that course v must be completed before course w may be attempted. A topological ordering of these courses is any course sequence that does not violate the prerequisite requirement
Topological Sort It is clear that a topological ordering is not possible if the graph has a cycle,since for two vertices vand w on the cycle,vprecedes wand wprecedes v. The ordering is not necessarily unique;any legal ordering will do. A simple algorithm to find a topological ordering is first to find any vertex with no incoming edges.We can then print this vertex,and remove it,along with this edge,from the graph.Then we apply this same strategy to the rest of the graph. Thus,we compute the indegrees of all vertices in the graph,and look for a vertex with indegree 0 that has not already been assigned a topological number
Topological Sort ◼ It is clear that a topological ordering is not possible if the graph has a cycle, since for two vertices v and w on the cycle, v precedes w and w precedes v. ◼ The ordering is not necessarily unique; any legal ordering will do. ◼ A simple algorithm to find a topological ordering is first to find any vertex with no incoming edges. We can then print this vertex, and remove it, along with this edge, from the graph. Then we apply this same strategy to the rest of the graph. ◼ Thus, we compute the indegrees of all vertices in the graph, and look for a vertex with indegree 0 that has not already been assigned a topological number
Topological Sort ■Example: 1 2 3 4 5 6 7
Topological Sort 3 1 6 2 7 5 ◼ Example: 4