数据结构与算法分析第二版英文版课件chapter11.ppt

Graph Applications Modeling connectivity in computer networks Representing maps Modeling flow capacities in networks Finding paths from start to goal Modeling transitions in algorithms Ordering tasks Modeling relationships (families, organizations) Graphs (1) A graph G = (V, E) consists of a set of vertices V, and a set of edges E, such that each edge in E is a connection between a pair of vertices in V. The number of vertices is written |V|, and the number edges is written |E|. Graphs (2) undirected graph directed graph labeled graph Paths and Cycles Path: A sequence of vertices v1, v2, …, vn of length n-1 with an edge from vi to vi+1 for 1 = i n. A path is simple if all vertices on the path are distinct. A cycle is a path of length 3 or more that connects vi to itself. A cycle is simple if the path is simple, except the first and last vertices are the same. Connected Components An undirected graph is connected if there is at least one path from any vertex to any other. The maximum connected subgraphs of an undirected graph are called connected components. Directed Representation Undirected Representation Representation Costs Adjacency Matrix: ?(|V|2) space Adjacency List: ?(|V| + |E|) space Graph ADT class Graph { // Graph abstract class public: virtual int n() =0; // # of vertices virtual int e() =0; // # of edges // Return index of first, next neighbor virtual int first(int) =0; virtual int next(int, int) =0; // Store new edge virtual void setEdge(int, int, int) =0; // Delete edge defined by two vertices virtual void delEdge(int, int) =0; // Weight of edge connecting two vertices virtual int weight(int, int) =0; virtual int getMark(int) =0; virtual void setMark(int, int) =0; }; Graph Traversals (1) Some applications require visiting every vertex in the graph exactly once. The application may require that vertices be visited in some special order based on graph topology. Examples: Artificial