西安电子科技大学：《数据结构与算法分析 Data Structure and Algorithm Analysis》课程教学资源（PPT课件讲稿）07 Graph Algorithms

Definitions ■A graph G=(V，E)consists of a set of vertices,V and a set of edges,E. Each edge is a pair (v,w),where v,we V.Edges are sometimes referred to as arcs.If the pair is ordered,then the graph is directed. Vertex wis adjacent to v if and only if (v,w)eE. In an undirected graph with edge iv w,wis adjacent to vand vis adjacent to w.Some times an edge has a third component,known as either a weight or a cost

Definitions ◼ A graph G=(V, E) consists of a set of vertices, V, and a set of edges, E. ◼ Each edge is a pair (v, w), where v, wV. Edges are sometimes referred to as arcs. If the pair is ordered, then the graph is directed. ◼ Vertex w is adjacent to v if and only if (v, w)E. In an undirected graph with edge {v, w}, w is adjacent to v and v is adjacent to w. Some times an edge has a third component, known as either a weight or a cost

Definitions A path in a graph is a sequence of vertices wi,w2, w3,...,Ww such that (wi W1)EEfor 1s/N.The length of such a path is the number of edges on the path,which is equal to /1. ■ We allow a path from a vertex to itself;if this path contains no edges,then the path length is 0. If the graph contains an edge (v,v)from a vertex to itself,then the path v,vis sometime referred to as a loop.The graphs we will consider will generally be loopless. A simple path is a path such that all vertices are distinct,except that the first and the last could be the same

Definitions ◼ A path in a graph is a sequence of vertices w1 , w2 , w3 , …, wN such that (wi , wi+1)E for 1i<N. The length of such a path is the number of edges on the path, which is equal to N-1. ◼ We allow a path from a vertex to itself; if this path contains no edges, then the path length is 0. ◼ If the graph contains an edge (v, v) from a vertex to itself, then the path v, v is sometime referred to as a loop. The graphs we will consider will generally be loopless. ◼ A simple path is a path such that all vertices are distinct, except that the first and the last could be the same

Definitions A cycle in a directed graph is a path of length at least 1 such that wi=w;this cycle is simple if the path is simple. For undirected graphs,we require that the edges be distinct;that is,the path u,v,win an undirected graph should not be considered a cycle,because (u, v and (v,u)are the same edge.In a directed graph, these are different edges,so it makes sense to call this a cycle. A directed graph is acyclic if it has no cycles

Definitions ◼ A cycle in a directed graph is a path of length at least 1 such that w1=wn ; this cycle is simple if the path is simple. ◼ For undirected graphs, we require that the edges be distinct; that is, the path u, v, u in an undirected graph should not be considered a cycle, because (u, v) and (v, u) are the same edge. In a directed graph, these are different edges, so it makes sense to call this a cycle. ◼ A directed graph is acyclic if it has no cycles

Definitions An undirected graph is connected if there is a path from every vertex to every other vertex.A directed graph with this property is called strongly connected.If a directed graph is not strongly connected,but the underlying graph(without direction to the arcs)is connected,then the graph is said to be weakly connected. A complete graph is a graph in which there is an edge between every pair of vertices

Definitions ◼ An undirected graph is connected if there is a path from every vertex to every other vertex. A directed graph with this property is called strongly connected. If a directed graph is not strongly connected, but the underlying graph (without direction to the arcs) is connected, then the graph is said to be weakly connected. ◼ A complete graph is a graph in which there is an edge between every pair of vertices

Definitions In an undirected graph,the degree of a vertex is the number of edges connected to this vertex. In an directed graph,the outdegree of a vertex is the number of edges that start from this vertex,and the indegree is the number of edges that end at this vertex. ■ Examples of graphs:airport system,traffic flow, friendship

Definitions ◼ In an undirected graph, the degree of a vertex is the number of edges connected to this vertex. ◼ In an directed graph, the outdegree of a vertex is the number of edges that start from this vertex, and the indegree is the number of edges that end at this vertex. ◼ Examples of graphs: airport system, traffic flow, friendship

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 two￾dimensional 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