数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图

简介: 本文介绍了图的基本概念,包括图的定义、无向图与有向图、简单图与多重图等,并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图,如完全图和树等。通过这些概念,读者可以更好地理解图论的基础知识。

@[TOC]

图的基本概念

1. 图的定义

图由顶点集V和边集E组成,记为G=(V,E).
图中顶点的个数,也称为图G的阶,用|V| 表示图G中顶点的个数, |E|表示图G中边的条数.

注意:
图不可以为空.即图的点集不能为空,图可以没有边,但是有边,边肯定要连接图.

1.1 无向图和有向图

无向图:
E是无向边,边是顶点的无序对,记为(v,w)=(w,v),其中v,w是顶点.

有向图:
E是有向边(也称弧)的有限集合时,则图G为有向图.弧是顶点的有序对,记为,其中v,w是顶点,v称为弧尾,w称为弧头

1.2 简单图和多重图

简单图:
:one: 不存在重复边
:two:不存在顶点到自身的边(无环的意思)
image.png

多重图:
可以存在重复边,可以有环.

2.图的一些术语

2.1 顶点的度,入度,出度

对于无向图,顶点的度是指依附于该顶点边的条数,记为TD(v).

简言之,与顶点接触的边的条数,对一个边来说,他必然会和两条边接触。所以一个无向图中,所有顶点的度之和=2倍的边数。

对于有向图,
入度数以顶点v为终点的有向边的数目,记为ID(v).
出度是以顶点v为起点的有向边的数目,记为OD(v)
顶点的度=其入度和出度之和,即TD(v)=ID(v)+OD(v)

简言之,入度数箭头接触该结点的边数,出度是线尾接触结点的边数

2.2 路径 回路,简单路径,路径长度,点到点的距离

路径:顶点v~p~到顶点~q~之间的一条路径是指顶点序列,v~p~,v~1~,v~2~....v~q~

回路:第一个顶点和最后一个顶点相同的路径叫回路

简单路径:在路径序列中,没有顶点重复的路径。

简单回路:除一个顶点和最后一个顶点外,其余顶点不重复的回路

点到点的距离:从顶点v出发到顶点v的最短路径存在,则称路径的长度为u到v到距离,如果两个顶点之间不存在路径,则记为无穷

2.3 连通图,强联通图

引入基本概念:连通,强连通
连通:无向图中,若从顶点v到顶点w有路径存在,则称v和我是连通的
强连通:有向图中,v到w,w到v之间都有路径,则称这两个顶点是强连通的。

连通图:若图中任意两个顶点都是连通的,则称图G为连通图,否则则称非连通图。

对于n个顶点的无向图G,若G是连通图,则最少有n-1条边。
若G是非连通图,则最少有c^2^~n-1~

强连通图,任何一对顶点都是强连通的图。
强连通图,至少有n条边,形成n条边

3. 图的局部--子图

子图是顶点是图的一部分,顶点之间原先在图中的线可以存在,也可以不存在。但是不是两头都有接触的边,肯定不能存在。

3.1 连通分量,强连通分量

无向图中的极大连通子图称为连通分量。

子图必须连通,且包含尽可能多的顶点和边。

有向图中的极大强连通子图称为有向图的强连通分量。

3.2 生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图。
若图中顶点数为n,则它的生成树含有n-1条边。对生成树而言,若砍去它的一条边,则会变成非连通图,若加上一条边则会形成一个回路。
image.png

3.3 生成森林

在非连通图中,连通分量的生成树构成了非连通图的生成森林。
image.png

3.4 边的权,带权图

边的权--在一个图中国,每条边都可以标上具有某种含义的数值,该数值称为该边的权值
带权图/网 边上带有权值的图为带权图,也称网。
带权路径长度:当图树带权图时,一条路径上所有边的权值之和,称为该路径的带权路径长度。

4. 几种特殊形态的图

4.1 无向完全图和有向完全图

image.png

4.2 树和有向树

树:不存在回路,且连通的无向图。

n个顶点的树,必有n-1条边,若边>n-1,则一定有回路

有向树:一个顶点的入度为0,其余顶点的入度均为1的有向图,称为有向树

相关文章
|
7天前
|
JSON 前端开发 JavaScript
一文了解树在前端中的应用,掌握数据结构中树的生命线
该文章详细介绍了树这一数据结构在前端开发中的应用,包括树的基本概念、遍历方法(如深度优先遍历、广度优先遍历)以及二叉树的先序、中序、后序遍历,并通过实例代码展示了如何在JavaScript中实现这些遍历算法。此外,文章还探讨了树结构在处理JSON数据时的应用场景。
一文了解树在前端中的应用,掌握数据结构中树的生命线
|
23天前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配,利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题,要求判断输入字符串中的括号是否正确匹配,并给出了完整的代码示例。此外,还探讨了栈在表达式求值中的应用,包括中缀、后缀和前缀表达式的转换与计算方法。最后,文章介绍了矩阵的压缩存储技术,涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略,提高存储效率。
|
25天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用,涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用;接着介绍了并查集的基本概念、存储结构及优化方法;随后探讨了二叉排序树的定义、查找、插入和删除操作;最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文,读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
|
25天前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现,涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例,展示了如何高效地处理顺序表数据结构的各种问题。
|
4天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
01_设计一个有getMin功能的栈
01_设计一个有getMin功能的栈
|
4天前
|
前端开发
07_用队列实现栈
07_用队列实现栈
06_用栈来求解汉诺塔问题
06_用栈来求解汉诺塔问题
05_用一个栈实现另一个栈的排序
05_用一个栈实现另一个栈的排序
03_如何仅用递归函数和栈操作逆序一个栈
03_如何仅用递归函数和栈操作逆序一个栈