最新公告
  • 欢迎您光临欧资源网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 有向图:有向图无向图的定义和术语连通(组图)

    1、图片

    1)图的定义:有向图 无向图

    2)图存储结构

    3)图遍历

    4)图应用(最小生成树拓扑排序关键路径

    2、图形定义和术语

    1)顶点连通性:如果有一条从顶点v到顶点v’的路径c语言无向图连通分量,那么就说顶点v和v’是连通的

    2)无向连通图:如果无向图中任意两个顶点vi和vj连通,则该图称为连通图(vivj)

    3)有向连通图:如果有向图中任意两个顶点vi和vj都有从vi到vj和从vj到vi的路径,则该图称为强连通图(vivj)

    4)无向图连通分量:无向图中的最大连通子图,称为连通分量

    5)有向图强连通分量:有向图的强连通子图称为强连通分量。

    6)生成树:假设一个无向图G是一个有n个顶点的连通图,那么图G的生成树是一个有n个顶点且只有n-1条边的连通子图。

    3、邻接矩阵

    4、有向图邻接表:与无向图的邻接表结构相同,只是第一个链表上的节点是以Vi为弧尾的每个弧头的顶点。

    5、有向图逆邻接表:与有向图的邻接表结构相同,只是第i个链表上的节点是以Vi为弧头的每条弧尾的顶点。

    6、图遍历:从图的某个顶点开始,使图中的每个顶点沿路径被访问且只访问一次的过程称为遍历图。

    1)遍历图的两种常用方法:深度优先搜索和广度优先搜索

    c语言无权限删除文件_c语言 无重复随机数_c语言无向图连通分量

    7、深度优先搜索:访问指定顶点V,以V为当前顶点访问当前顶点的下一个未访问的相邻点,并以该相邻点为当前顶点重复上一个步骤直到所有与当前顶点有路径的顶点都被访问,沿着搜索路径返回,并返回到仍然有尚未访问的相邻点的节点。到目前为止访问过。

    8、广度优先搜索:首先访问指定顶点V0,以V0为当前顶点访问当前顶点所有未访问的相邻点c语言无向图连通分量,依次将这些访问过的相邻点作为当前顶点,并重复上一步,直到所有顶点都被访问过。

    9、最小生成树生成树—-是无向连通图G的连通子图

    1)生成树的三个元素n个顶点n-1条边相连(无循环)

    10、生成树的代价:给图中的每条边分配一个权重(代价)组成一个网络,生成树的代价G’=(V.{T})为网络是T中每条边的权重之和,最小生成树是互联网上所有可能的生成树中代价最小的生成树。最小生成树也不一定是唯一的。

    11、拓扑排序:从集合上的偏序得到集合上的全序。这种操作称为拓扑排序。 (拓扑排序是对具有非线性结构的有向图进行线性化的重要手段)

    12、AOV网络可以解决以下两个问题:1)确定项目的可行性。显然,如果存在循环,整个项目是无法结束的2)确定整个项目中每个活动的执行顺序。这个序列称为拓扑有序序列。

    13、关键路径:

    1)AOE网络:在有向图中,顶点代表事件,弧代表活动,弧上的权重代表完成活动所需的时间。这种类型的有向图称为网络,其边代表活动。

    2)AOE网络中只有一个入度为0的事件,称为源点,代表项目的开始;网络中也只有一个出度为0的事件,称为汇点,表示项目结束。

    3)每一个事件V都表示以它为弧头的所有活动都已完成,同时也表示以它为弧头的所有活动都可以开始了.

    4)AOE网络可以解决以下问题:估计项目的最短工期(从源点到汇点需要多少时间)找出哪些活动是进度的关键整个项目。

    14、路径长度:路径上每个活动的持续时间之和,即:路径上所有弧的权重之和

    1)关键路径:从源到汇的路径长度最长的路径。 (不一定只有 一)

    2)关键活动:l(i)=e(i) 的活动

    15、 关键路径上的活动是关键活动。 1) 缩短非关键活动不会缩短整体持续时间。

    2)分析关键路径的目的是找出影响整个工期的关键活动,缩短关键活动的工期,往往会缩短整个工期。

    站内大部分资源收集于网络,若侵犯了您的合法权益,请联系我们删除!
    欧资源网 » 有向图:有向图无向图的定义和术语连通(组图)

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    欧资源网
    一个高级程序员模板开发平台

    发表评论