内蒙古大学《算法与数据结构》课件第6章图
170页1、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本章只讨论本章只讨论简单图简单图, ,即有两类图形不在本章
2、讨论之列:即有两类图形不在本章讨论之列: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)有向图中,顶点有
3、向图中,顶点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的三个连通分量
4、的三个连通分量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 ); /删除一条边
5、删除一条边(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 M
《内蒙古大学《算法与数据结构》课件第6章图》由会员东***分享,可在线阅读,更多相关《内蒙古大学《算法与数据结构》课件第6章图》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页