当前位置:   article > 正文

有向图数据结构_数据结构基础——图(Graph)

有向图结构
图:由顶点的有穷非空集合和顶点之间边的集合组成。通常表示为G(V,E),其中,G表示一个图, V是图G中的顶点的集合 , E是图G中边的集合。

8b674ed664b909e6ac1fd6144b181ceb.gif

注意:

1.在线性表中,数据元素之间是被串起来的,仅有线性关系,每一个数据元素只有一个直接前驱和一个直接后继。

2.在树形结构中,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素相关,但只能和上一层中一个元素相关。

3.图是一种较线性表和树更加复杂的数据结构,在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。

de37be49e1531f8be2f6306b8afc86d3.gif

图的五种种类 :无向图、有向图、简单图、完全无向图,完全有向图。 权(Weight) :有些图的边或弧具有与它相关的数字,这种与图的边或弧相关的数叫做权。

1.这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网(Network)。

2.图结构中,路径的长度是路径上的边或弧的数据。

3.第一个顶点到最后一个顶点相同的路径称为回环或环(Cycle)。

4.序列中顶点不重复出现的路径称为简单路径。

简单环 :除第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环。 特性:

1.连通:图中顶点间存在路径,两顶点存在路径则说明是连通的。

2.简单路径:如果路径最终回到起始点则称为 简单环,当中不重复叫 简单路径。

3.强连通图:若任意两顶点都是连通的,则图就是连通图,有向则称为 强连通图。

4.强连通分量:图中有子图,若子图极大连通则就是连通分量,有向的则称为 强连通分量。

5.生成树:无向图中连通且n个顶点n-1条边叫 生成树。

6.有向树:有向图中一顶点入度为0,其余顶点入度为1的叫有向树。

7.森林:一个有向图由若干有向树构成生成 森林。

578abaa72bdbad7c415363cd1f47c87a.gif

注意:

由于图的结构比较复杂,任意两个顶点之间都可能存在联系,因此无法以数据元素在内存中的物理位置来表示元素之间的关系。也就是说,图不可能用简单的顺序存储结构(即数组)来表示。

图的两种遍历 :深度优先遍历、 广度优先遍历。 AVO网 :在一个表示工程的有向图中, 用顶点表示活动 ,用弧表示活动之间的优先关系。AVO网中不能存在回路。

拓扑排序:对一个有向图构造拓扑序列的过程。

AOE网 :在一个表示工程的带权有向图中, 用顶点表示事件 ,用有向边表示活动,用边上的权值表示活动的持续时间。

正常情况下,AOE网只有一个源点一个汇点。

始点或源点 :我们把AOE网中没有入边的顶点称为始点或源点。 终点或汇点 :没有出边的顶点称为终点或汇点。 我们把路径上各个活动所 持续的时间之和 称为 路径长度 。 从源点到汇点具有 最大长度的路径 叫  关键路径 。 在 关键路径上的活动 叫  关键活动

ab5a1a41fb413894b0e3e5b4c3e74afb.gif

47a326dd41a17ec806b3793325da36c2.gif

数据结构基础——线性表&顺序表示

数据结构基础——线性表&链式表示

数据结构基础——栈&队列

数据结构——串

数据结构基础——树

f638f57bb005264aeb6932beb2d3d290.gif

‧  END  

﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌ 免责声明:本文部分内容来自网络,版权归原作者所有,如涉及作品版权问题,请及时联系我们,谢谢!

关注微信公众号 小平Linux工作室

55f60fed52e7978f30b77a38bad539c1.png学习更多互联网知识55f60fed52e7978f30b77a38bad539c1.png

c254a8fa946bd27a71285fee9771a3b4.png

长按前往图中包含的公众号关注

若文章对你有帮助,在页面右下角点个 在看

最 后 

若觉得文章不错,转发分享给更多的朋友dcf07737c01ca422b9e2ed6b6911d85d.png

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop】
推荐阅读
相关标签
  

闽ICP备14008679号