数据结构基础详解(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的有向图,称为有向树

相关文章
|
12天前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践,体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案,包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例,帮助读者掌握C语言的基本语法和常用算法,提升编程能力。
|
27天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
84 64
|
12天前
|
存储 算法 C语言
【趣学C语言和数据结构100例】
《趣学C语言和数据结构100例》精选5个编程问题,涵盖求最大公约数与最小公倍数、字符统计、特殊序列求和及阶乘计算等,通过实例讲解C语言基础与算法思维,适合初学者实践学习。
|
19天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
14 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
21天前
|
存储 C语言
探索C语言数据结构:利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录,包括初始化、添加、删除、查找和保存联系人信息的操作,以及自定义结构体用于存储联系人详细信息。
18 2
|
27天前
|
存储 编译器 C++
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
|
27天前
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(三)
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解
|
27天前
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(二)
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解
|
27天前
|
存储
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(一)
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解
|
16天前
|
Java C++
【数据结构】探索红黑树的奥秘:自平衡原理图解及与二叉查找树的比较
本文深入解析红黑树的自平衡原理,介绍其五大原则,并通过图解和代码示例展示其内部机制。同时,对比红黑树与二叉查找树的性能差异,帮助读者更好地理解这两种数据结构的特点和应用场景。
21 0