n8.1图的基本概念n8.2图的存储表示n8.3图的遍历与连通性 n8.4最小生成树n8.5最短路径 n8.6活动网络第八章 图18.1图的基本概念n图定义 图是由顶点集合(vertex)及顶点间的 关系集合组成的一种数据结构：Graph( V, E ) 其中 V = x | x 某个数据对象 是顶点的有穷非空集合；E = (x, y) | x, y V 或 E = | x, y V 顶点 v 的出度是以 v 为始点的有向 边的条数, 记作 OD(v)。n路径 在图 G(V, E) 中, 若从顶点 vi 出发, 沿 一些边经过一些顶点 vp1, vp2, , vpm，到达顶 点vj。则称顶点序列 (vi vp1 vp2 . vpm vj) 为从顶 点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、 (vp1, vp2)、.、(vpm, vj) 应是属于E的边。5n路径长度 非带权图的路径长度是指此路径上 边的条数。带权图的路径长度是指路径上各边 的权之和。n简单路径 若路径上各顶点 v1, v2, ., vm 均不 互相重复, 则称这样的路径为简单路径。n回路 若路径上第一个顶点 v1 与最后一个顶 点vm 重合, 则称这样的路径为回路或环。0123012301236n连通图与连通分量 在无向图中, 若从顶 点v1到顶点v2有路径, 则称顶点v1与v2是 连通的。如果图中任意一对顶点都是连 通的, 则称此图是连通图。n非连通图的极大连通子图叫做连通分量 。7连通图若无向图为非连通图 ，则图中各个极大连 通子图称作此图的连 通分量。BACDFEBACDFE8ABECFABECFn强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi 到vj和从vj到vi的路径, 则称此图是强连通 图。非强连通图的极大强连通子图叫做 强连通分量。9n生成树 一个连通图的生成树是其极小 连通子图，在 n 个顶点的情形下，有 n- 1 条边。10对非连通图，则 称由各个连通分 量的生成树的集 合为此非连通图 的生成森林。BACDFEn生成树 一个连通图的生成树是其极小 连通子图，在 n 个顶点的情形下，有 n- 1 条边。11图的抽象数据类型class Graph /对象: 由一个顶点的非空集合和一个边集合构成 /每条边由一个顶点对来表示。 public:Graph();/建立一个空的图void insertVertex (const T/插入一个顶点vertex, 该顶点暂时没有入边void insertEdge (int v1, int v2, int weight);/在图中插入一条边(v1, v2, w)void removeVertex (int v);/在图中删除顶点v和所有关联到它的边 12void removeEdge (int v1, int v2);/在图中删去边(v1,v2)bool IsEmpty();/若图中没有顶点, 则返回true, 否则返回falseT getWeight (int v1, int v2);/函数返回边 (v1,v2) 的权值int getFirstNeighbor (int v);/给出顶点 v 第一个邻接顶点的位置int getNextNeighbor (int v, int w);/给出顶点 v 的某邻接顶点 w 的下一个邻接顶点 ;138.2图的存储表示n图的模板基类 在模板类定义中的数据类型 参数表 中，T是顶点数据的 类型，E是边上所附数据的类型。n这个模板基类是按照最复杂的情况（即带权 无向图）来定义的，如果需要使用非带权图 ，可将数据类型参数表 改 为 。n如果使用的是有向图，也可以对程序做相应 的改动。 14图的模板基类 const int maxWeight = ; /无穷大的值(=) const int DefaultVertices = 30; /最大顶点数(=n) template class Graph /图的类定义 protected:int maxVertices; /图中最大顶点数int numEdges; /当前边数int numVertices; /当前顶点数int getVertexPos (T vertex);/给出顶点vertex在图中位置 public: 15Graph (int sz = DefaultVertices); /构造函数Graph();/析构函数bool GraphEmpty () const /判图空否 return numEdges = 0; int NumberOfVertices () return numVertices; /返回当前顶点数int NumberOfEdges () return numEdges; /返回当前边数 virtual T getValue (int i);/取顶点 i 的值virtual E getWeight (int v1, int v2); /取边上权值virtual int getFirstNeighbor (int v);/取顶点 v 的第一个邻接顶点16virtual int getNextNeighbor (int v, int w);/取邻接顶点 w 的下一邻接顶点virtual bool insertVertex (const T vertex);/插入一个顶点vertexvirtual bool insertEdge (int v1, int v2, E cost);/插入边(v1,v2), 权为costvirtual bool removeVertex (int v);/删去顶点 v 和所有与相关联边virtual bool removeEdge (int v1, int v2);/在图中删去边(v1,v2) ;178.2 图的存储表示8.2.1图的数组(邻接矩阵)存储表示8.2.2图的邻接表存储表示8.2.3 邻接多重表 188.2.1邻接矩阵 (Adjacency Matrix)n在图的邻接矩阵表示中，有一个记录各个顶 点信息的顶点表，还有一个表示各个顶点之 间关系的邻接矩阵。n设图 A = (V, E) 是一个有 n 个顶点的图, 图的 邻接矩阵是一个二维数组 A.edgenn，定义 ：19A.Edgeij=0 (i,j)E1 (i,j)EBACDFE定义:图A矩阵的元素为1234561 2 3 4 5 688 8101010999n无向图的邻接矩阵是对称的;20ABECDn有向图的邻接矩阵可能是不对称的。21n在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 列 1 的个数可得顶点 j 的入 度。n在无向图中, 统计第 i 行 (列) 1 的个数可得顶 点i 的度。22网络的邻接矩阵86312954203123用邻接矩阵表示的图的类定义template class Graphmtx : public Graph friend istream/输入friend ostream/输出24private:T *VerticesList; /顶点表E *Edge;/邻接矩阵 int getVertexPos (T vertex) /给出顶点vertex在图中的位置for (int i = 0; i = 0 numVertices = 0; numEdges = 0; int i, j; VerticesList = new TmaxVertices; /创建顶点表Edge = (int *) new int *maxVertices; for (i = 0; i int Graphmtx:getFirstNeighbor (int v) /给出顶点位置为v的第一个邻接顶点的位置, /如果找不到, 则函数返回-1if (v != -1) for (int col = 0; col int Graphmtx:getNextNeighbor (int v, int w) /给出顶点 v 的某邻接顶点 w 的下一个邻接顶点 if (v != -1 col struct Edge /边结点的定义int dest; /边的另一顶点位置E cost; /边上的权值Edge *link; /下一条边链指针Edge () /构造函数Edge (int num, E cost) /构造函数: dest (num), weight (cost), link (NULL) bool operator != (Edge /判边等否 ;36template struct Vertex /顶点的定义T data; /顶点的名字 Edge *adj; /边链表的头指针 ;template class Graphlnk : public Graph /图的类定义 friend istream /输入 friend ostream /输出37private:Vertex *NodeTable;/顶点表 (各边链表的头结点)int getVertexPos (const T vertx) /给出顶点vertex在图中的位置for (int i = 0; i = 0 numVertices = 0; numEdges = 0;NodeTable = new VertexmaxVertices; /创建顶点表数组if (NodeTable = NULL) cerr Graphlnk:Graphlnk() /析构函数：删除邻接表for (int i = 0; i *p = NodeTablei.adj;while (p != NULL) NodeTablei.adj = p-link;delete p; p = NodeTablei.adj; delete NodeTable; /删除顶点表数组 ;41template int Graphlnk:getFirstNeighbor (int v) /给出顶点位置为 v 的第一个邻接顶点的位置, /如果找不到, 则函数返回-1if (v != -1) /顶点v存在Edge *p = NodeTablev.adj; /对应边链表第一个边结点 if (p != NULL) return p-dest; /存在, 返回第一个邻接顶点return -1;/第一个邻接顶点不存在 ;42template int Graphlnk:getNextNeighbor (int v, int w) /给出顶点v的邻接顶点w的下一个邻接顶点的位置, /若没有下一个邻接顶点, 则函数返回-1if (v != -1) /顶点v存在Edge *p = NodeTablev.adj;while (p != NULL if (p != NULL /返回下一个邻接顶点return -1; /下一邻接顶点不存在 ;438.2.3邻接多重表 (Adjacency Multilist)n在邻接多重表中, 每一条边只有一个边结点。n无向图的情形u边结点的结构n其中, mark 是记录是否处理过的标记; vertex1 和vertex2是该边两顶点位置。path1域