[其它技巧]数据结构PPT 7.ppt

Graphs Graph Definition Graph Implementations Graph Traversals Shortest-paths Problems Minimum-Cost Spanning Trees 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 weighted graph Graph Applications Modeling connectivity in computer networks Representing maps Modeling flow capacities in transportation networks Modeling transitions in algorithms Ordering tasks Modeling relationships (families, organizations) 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 v1 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(连通分量）. Graphs Graph Definition Graph Implementations Graph Traversals Shortest-paths Problems Minimum-Cost Spanning Trees 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(