数据结构:图的定义和术语总结

一、图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。在图中的数据元素,我们称之为顶点(Vertex),顶点集合有穷非空。在图中,任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空的。

二、图按照有无方向分为无向图和有向图。无向图由顶点和边组成,有向图由顶点和弧构成。弧有弧尾和弧头之分,带箭头一端为弧头。

三、图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫做完全图,有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。

四、图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度。有向图顶点分为入度和出度。

五、图上的边或弧带有权则称为网。

六、图中顶点间存在路径,两顶点存在路径则说明是连通的,如果路径最终回到起始点则称为环,当中不重复的叫简单路径。若任意两顶点都是连通的,则图就是连通图,有向则称为强连通图。图中有子图,若子图极大连通则就是连通分量,有向的则称为强连通分量。

七、无向图中连通且n个顶点n-1条边称为生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CreateAMind

Building Agents with Imagination

1393
来自专栏机器之心

资源 | 谷歌与MIT联袂巨著:《计算机科学的数学》开放下载

选自CSAIL.Mit 机器之心编译 参与:蒋思源、吴攀 谷歌和麻省理工学院联袂出品的《计算机科学的数学》昨日已经开放下载了,读者可点击文末「阅读原文」下载。...

2777
来自专栏calmound

poj 3083 Children of the Candy Corn(搜索)

http://poj.org/problem?id=3083 题意:迷宫沿着左墙走,和沿着右强的距离以及最短路径的距离分别是多少,当向左走的时候1的位置就是面向...

2795
来自专栏专知

ACL 2018 计算语言学协会接受论文列表

3441
来自专栏小樱的经验随笔

“玲珑杯”ACM比赛 Round #12题解&源码

我能说我比较傻么!就只能做一道签到题,没办法,我就先写下A题的题解&源码吧,把官方给出的题解贴出来! A -- Niro plays Galaxy Note ...

3827
来自专栏计算机视觉与深度学习基础

计算机视觉著名数据集CV Datasets

Detection PASCAL VOC 2009 datasetClassification/Detection Competitions, Segm...

2378
来自专栏数据科学与人工智能

【陆勤践行】DataSchool 推荐的数据科学资源

Blogs Simply Statistics1: Written by the Biostatistics professors at Johns Hopki...

2549
来自专栏wym

欧拉路和欧拉回路理论基础

   欧拉路是指从图中任意一点开始到任意一点结束的路径,并且图中每条边通过且只通过一次。也即可以一笔画出。

852
来自专栏Pulsar-V

Python MFCC算法

MFCC(梅尔倒谱系数)的算法思路 读取波形文件 汉明窗 分帧 傅里叶变换 回归离散数据 取得特征数据 Python示例代...

3714
来自专栏CreateAMind

视觉机械臂 visual-pushing-grasping

1011

扫码关注云+社区