内蒙古大学《算法与数据结构》课件第6章图

1 2： / /弧弧 3v无向图无向图无向图无向图G是由两个集合是由两个集合V(G)和和E(G)组成的组成的其中：其中：V(G)是顶点的非空有限集是顶点的非空有限集;E(G)是边的有限集是边的有限集 合，边是顶点的无序对合，边是顶点的无序对, 记为记为(v,w)或或(w,v)， 并且（并且（v,w)=(w,v)v有向图有向图有向图有向图G是由两个集合是由两个集合V(G)和和E(G)组成的组成的 其中：其中：V(G)是顶点的非空有限集是顶点的非空有限集;E(G)是有向边是有向边(也称也称 弧弧）的有限集合，弧是顶点的有序对，记为）的有限集合，弧是顶点的有序对，记为 ，v,w是顶点，是顶点，v为弧尾为弧尾(或始点或始点)， w为弧头为弧头(终点终点). 4例例1245136G2图图G2：V(G2)=1,2,3,4,5,6 E(G2)=, , , , , , 例例2157324G16图图G1：V(G1)=1,2,3,4,5,6,7E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)5本章只讨论本章只讨论简单图简单图, ,即有两类图形不在本章讨论之列：即有两类图形不在本章讨论之列：6v(无向无向)完全图完全图(Completed graph) : n个顶点的有个顶点的有n(n-1)/2条边的简单条边的简单无向图无向图.v有向完全图有向完全图: n个顶点的有个顶点的有n(n-1)条弧的简单条弧的简单有向图有向图. v稀疏图稀疏图(sparse graph)： 边或弧很少的图，通常边数边或弧很少的图，通常边数enlog2nv稠密图稠密图(Dense graph): 无向图中，边数接近无向图中，边数接近有向图中，弧数接近有向图中，弧数接近7有向网有向网v权权与图的边或弧相关的数与图的边或弧相关的数.v网网带权的无向图称为无向网带权的无向图称为无向网; 带权的带权的有向有向图称为有向网图称为有向网;无向网无向网8v子图子图已知图已知图G(V,E)和图和图G(V,E), 若若满足：满足：V V且且 E E 则称则称G为为G的子图的子图9关联关联: :10v顶点的度（与树中结点的度不同）顶点的度（与树中结点的度不同）:无向图中，顶点无向图中，顶点v的度是与该顶点的度是与该顶点v关联的边数关联的边数, 记作记作TD(v)有向图中，顶点有向图中，顶点v的度分成入度与出度的度分成入度与出度入度：以该顶点入度：以该顶点v为终头的弧的数目为终头的弧的数目,记为记为ID(v)出度：以该顶点出度：以该顶点v为始点的弧的数目为始点的弧的数目,记为记为OD(v)一个顶点一个顶点v的度等于该顶点的入度与出度之和的度等于该顶点的入度与出度之和,即即TD(v)=OD(v)+ID(v)nii)v(TDe12111v(有向有向)路径路径顶点的序列顶点的序列(Vi0,Vi1 , , Vik)， 满足满足(Vij-1,Vij) E 或或 E，(1 j k)v路径长度路径长度沿路径边的数目或沿路径各边权值之和。沿路径边的数目或沿路径各边权值之和。v简单路径简单路径序列中顶点不重复出现的路径。序列中顶点不重复出现的路径。v回路回路第一个顶点和最后一个顶点相同的路径。第一个顶点和最后一个顶点相同的路径。v简单回路简单回路除了第一个顶点和最后一个顶点外，其除了第一个顶点和最后一个顶点外，其 余顶点不重复出现的回路。余顶点不重复出现的回路。12V0V1V3V2V0V1V3V0V1V2V0V1V3V013ABCDEHMFGIJLK无向图无向图G的三个连通分量的三个连通分量ABCDEFGIJLHMK无向图无向图G14强连通图强连通图非强连通图非强连通图G非强连通图非强连通图G两两个个 强强连通分量连通分量15v生成树生成树：回路回路. .ABCDEHM无向图无向图G ABCDEHM无向图无向图G的生成树的生成树 16v生成森林生成森林：FGIJLK生成森林生成森林ABCDEFGIJLHMK无向图无向图GABCDEHM17class Graph /图是由一个顶点的非空有限集合和一个边或弧的集合组成。图是由一个顶点的非空有限集合和一个边或弧的集合组成。 public: Graph ( ); /建立一个空图建立一个空图 void InsertVertex ( Type & vertex ); / 在图中插入一个顶点在图中插入一个顶点vertex void InsertEdge(int v1，int v2 ); / 在图中插入一条边在图中插入一条边(v1，v2)或一条弧或一条弧 void RemoveVertex ( int v ); / 删除一个顶点删除一个顶点v void RemoveEdge ( int v1，int v2 ); /删除一条边删除一条边(v1，v2)或一条弧或一条弧 int IsEmpty ( ); / 判断图中是否有顶点，若无则返回判断图中是否有顶点，若无则返回1，否则返回，否则返回0 DataType GetWeight ( int v1，int v2 ); / 函数返回边函数返回边(v1，v2)或弧或弧的权值的权值 int GetFirstNeighbor ( int v ); / 函数返回顶点位置函数返回顶点位置v的第一个邻接顶点的位置，若找不到，则函的第一个邻接顶点的位置，若找不到，则函 / 数返回数返回-1 int GetNextNeighbor ( int v1，int v2 ); / 函数返回顶点位置函数返回顶点位置v1相对于相对于v2的下一个邻接顶点的位置的下一个邻接顶点的位置,若找不到，若找不到， /则函数返回则函数返回-1181 若若(vi，vj)E或或 E0 反之反之192021Aij= 0 i=j 其它其它 wij 若若(vi，vj)E 或或 E 22class AdjMatrix / 非带权图非带权图 int n； / 顶点的个数顶点的个数 int matrixMaxSize MaxSize； / 邻接矩阵邻接矩阵 public: AdjMatrix(int m) n=m； ; / AdjMatrix class AdjMatrix / 带权图带权图 const int INFINITE=； int n； /顶点的个数顶点的个数 float matrixMaxSizeMaxSize； / 邻接矩阵邻接矩阵 public: AdjMatrix(int m) n=m； 23 void CreateGraph() ; / 建立一个图建立一个图G的邻接矩阵的邻接矩阵matrix void LocateVex(v) ; / 确定图确定图G中顶点中顶点v在顶点中的位置在顶点中的位置 void GetVex(v); / 得到图得到图G中顶点中顶点v的值的值 int FirstAdjVex(v); / 确定图确定图G中顶点出中顶点出v的第一个邻接点的第一个邻接点 int NextAdjVex(v,w); / 确定图确定图G中顶点出中顶点出v相对于相对于w的下一个邻接点的下一个邻接点 void DFSTraverse(int v)； / 从顶点从顶点v开始对图进行深度优先遍历开始对图进行深度优先遍历 void BFSTraverse(int v)； / 从顶点从顶点v开始对图进行广度优先遍历开始对图进行广度优先遍历; / AdjGraph24假定图以邻接矩阵假定图以邻接矩阵G存储存储:int AdjMatrix :FirstAdjVex(int v) int w=0; while(wn & matrixvw=0)w+; if(wn) return w; else -1; 算法的时间复杂度为：算法的时间复杂度为：(n)25假定图以邻接矩阵假定图以邻接矩阵G存储存储 int NextAdjVex(int v,int w) u=w+1; while(un & matrixvu=0)u+; if(ufirstout) /书上没有书上没有 return gheadv-firstout.adjvex； else return -1; /书上没有书上没有/ FirstAdjVex转转int NextAdjVex(int v，int w) p=gheadv-firstout；while (p & p-adjvex!=w) p=p-link；if (!p | !p-link) return -1； /书上为书上为0else return p-link-adjvex；/ NextAdjVex336.2.3 邻接多重表表示法邻接多重表表示法 邻接多重表是只用来存储无向图的另一种存储结构邻接多重表是只用来存储无向图的另一种存储结构 . 在邻接多重表表示法中每一条边只对应一个边结点在邻接多重表表示法中每一条边只对应一个边结点（EdgeNode），每一个顶点也对应一个顶点结点），每一个顶点也对应一个顶点结点（VNode）。）。在边结点中，每一条边对应的边结点有五个域：在边结点中，每一条边对应的边结点有五个域：EdgeNode mark vex1 vex2 link1 link2 34其中：其中：mark是标志域，标记该边是否被遍历是标志域，标记该边是否被遍历 过；过；vex1与与vex2是该边所关联的两个顶点在图中的序号是该边所关联的两个顶点在图中的序号；link1是指向下一条与顶点是指向下一条与顶点vex1相关联的边；相关联的边；link2是是指向下一条与顶点指向下一条与顶点vex2相关联的边。相关联的边。 其中：其中：data是存放该顶点相关信息；是存放该顶点相关信息；firstEdge是指是指向第一条与顶点相关联的边。向第一条与顶点相关联的边。VNode data firstEdge 35邻接多重表类型说明如下：邻接多重表类型说明如下：class EdgeNode / 边结点边结点 Tag mark； /访问标记访问标记 int vex1,vex2； / 该边所指向的顶点的序号该边所指向的顶点的序号 EdgeNode *link1，*link2； / 指向下一条边的指针指向下一条边的指针 public: EdgeNode(int adj) ;/ EdgeNodeclass VNode / 顶头结点顶头结点DataType data； / 顶点的信息顶点的信息EdgeNode *firstEdge / 指向与该顶点所关联的一条的指针指向与该顶点所关联的一条的指针36public: VNode (DataType e) data=e; firstEdge=NULL;/ VNodeclass MulistGragh /邻接多重表邻接多重表 int n； / 顶点的个数顶点的个数Node VheadMaxSize； public: MulistGragh (int m) n=m； void CreateGraph(g ) ； / 建立图建立图gvoid LocateVex(u) ； / 得到顶点得到顶点v在图中的序号在图中的序号 void GetVex(v) ； / 得到顶点得到顶点v的值的值void PutVex(v，value) ； / 把把v的值赋为的值赋为value void FirstAdjVex(v) ； / 得到顶点得到顶点v的第一个邻接顶点的第一个邻接顶点 void NextAdjVex(v, w); / 确定图确定图G中顶点出中顶点出v相对于相对于w的下一个邻接点的下一个邻接点37void DFSTraverse(int v)； / 从顶点从顶点v开始对图进行深度优先遍历开始对图进行深度优先遍历void BFSTraverse(int v); / 从顶点从顶点v开始对图进行广度优先遍历开始对图进行广度优先遍历; /MulistGragh386.2.4 十字链表十字链表 十字链表是只用来存储有向图的另一种存储结构。可十字链表是只用来存储有向图的另一种存储结构。可以把十字链表看成是将有向图的邻接表和逆邻接表结以把十