博客 wordpress,关键词优化排名软件怎么样,网页设计作业成品免费下载,网站建设订制版合同模板文章目录1 图1.1 定义1.2 4种图模型2 无向图2.1 定义2.2 术语后记1 图
1.1 定义
图是一种非线性的数据结构#xff0c;表示多对多的关系。 图#xff08;Graph#xff09;是由顶点的有穷非空集合和顶点之间边的集合组成#xff0c;通常表示为#xff1a;G(V, E)#xf…
文章目录1 图1.1 定义1.2 4种图模型2 无向图2.1 定义2.2 术语后记1 图
1.1 定义
图是一种非线性的数据结构表示多对多的关系。 图Graph是由顶点的有穷非空集合和顶点之间边的集合组成通常表示为G(V, E)其中G表示一个图V是图G中顶点的集合E是图G中边的集合。 在图中需要注意的是 线性表和树可以看做特殊的图。 线性表中我们把数据元素叫元素树中将数据元素叫结点在图中数据元素我们则称之为顶点Vertex。 线性表可以没有元素称为空表树中可以没有节点称为空树但是在图中不允许没有顶点有穷非空性 线性表中的各元素是线性关系树中的各元素是层次关系而图中各顶点的关系是用边来表示边集可以为空。
1.2 4种图模型
无向图有向图加权图加权有向图
2 无向图
2.1 定义 图是由一组顶点和一组能够将两个顶点相连的边组成。 图下图2.1-1所示 顶点一般使用0至V-1来表示一张含有V个顶点的图中的各个顶点使用数组索引作为结点很方便。我们使用v-w或者w-v表示连接v和w的边。
特殊的图
自环一条连接一个顶点和其自身的边连接同一对顶点的两条及以上的边称为平行边
含有平行边的图称为多重图没有平行边或自环的图称为简单图。
2.2 术语 相邻顶点由同一条边连接的两个顶点称为相邻顶点并称这条边依附于这2个顶点。 度数某个顶点的度数即为依附于这个顶点的边的总数。 子图有一幅图所以边的一个子集以及他们所依附的所有顶点组成的图。 路径由边顺序连接的一系列顶点。 简单路径一条没有重复顶点的路径。 环一条至少含有一条边且起点和终点相同的路径。 简单环一条除起点和终点必须相同外不含有重复顶点和边的环。u-v-w-x-u记法表示从u到v到w在回到u到一条环。 路径长度或者环的长度路径或者边所 包含的边数。 连通当两个顶点之间存在一条连接双方的路径时我们称一个顶点和另外一个顶点连通。 u-v-w-x记法表示u到x的一条路径 连通图如果从任意一顶点都存在一条路径到达另一个任意顶点我们称这幅图是连通图。 一幅非连通图由若干连通的部分组成它们都是其极大连通子图分量。 连通图的生成树连通图的生成树是它的一幅子图它含有图中的所有顶点且是一颗树。 树是一幅无环连通图。互不相连的树组成的集合称为森林。 图的生成树森林图的所有连通子图上生成树的集合。
一棵树如下图所示 生成树森林 当且仅当一幅含有V个结点的图G满足下列5个条件之一时它就是一棵树 G有V-1条边且不含有环 G有V-1条边且时连通的 G是连通的但删除任意一条边都会使它不在连通 G是无环图但添加任意一条边都会产生一条环 G中任意一堆顶点之间仅存在一条简单路径。 图密度图密度是指已连接的顶点对占所有可能连接顶点对的比例。 稀疏图如果一幅图中不同边的数量在顶点总数V的一个小的常数倍以内那么我们就称这幅图是稀疏的。稠密图否则就是稠密图。 二分图二分图是一种能够将所有结点分为两部分的图其中图的每条边所连接的两个顶点分别属于不同的部分。
后记
如果小伙伴什么问题或者指教欢迎交流。 ❓QQ:806797785 ⭐️源代码仓库地址https://gitee.com/gaogzhen/algorithm 参考链接:
[1][美]Robert Sedgewich,[美]Kevin Wayne著;谢路云译.算法第4版[M].北京人民邮电出版社2012.10
[2]数据结构图的基本概念
