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

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

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

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

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

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

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏腾讯高校合作

【犀牛鸟·视野】SIGGRAPH Asia 2017 (DAY 3):领略前沿poster papers,关注WebXR新技术

今天是SIGGRAPH Asia 2017的第三天,也是Poster papers讲解的最后一天(总共两天,每天中午13:00-14:00)。今年中了poste...

41460
来自专栏程序生活

第三周编程作业-Planar data classification with one hidden layerPlanar data classification with one hidden l

Planar data classification with one hidden layer Welcome to your week 3 programm...

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

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

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

35580
来自专栏HansBug's Lab

1342: [Baltic2007]Sound静音问题

1342: [Baltic2007]Sound静音问题 Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 710 ...

37370
来自专栏HansBug's Lab

1475: 方格取数

1475: 方格取数 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 578  Solved: 309 [Subm...

26660
来自专栏wym

HDU 3018 Ant Trip(欧拉回路)

#include <bits/stdc++.h> using namespace std; const int N=100005; int f[N]; ...

9920
来自专栏用户画像

5.1 图的基本概念

在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。含有n个顶点的无向图有n(n-1)/2条边。

9120
来自专栏专知

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

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

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

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

29190
来自专栏机器之心

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

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

33770

扫码关注云+社区

领取腾讯云代金券