数据结构笔记——图的基本概念
目录
一、图的定义
二、图逻辑结构的应用
三、无向图、有向图
四、简单图、多重图
五、顶点的度、入度、出度
六、顶点-顶点的关系描述
七、连通图、强连通图
八、研究图的局部——子图
九、连通分量、强连通分量
十、生成树
十一、生成森林
十二、边的权、带权图/网
十三、带权图的应用举例
十四、几种特殊形态的图
十五、总结
一、图的定义
图G由顶点集V和边集E组成，记G=（V,E），其中V（G）表示图G中顶点的有限非空集；E（G）表示图G中顶点之间的关系（边）集合。若V={V1,V2….Vn}，则用|V|表示图G中顶点的个数，也称图G的阶，E={（u，v）| u∈V，v∈V}，用|E|表示图G中边的条数。
注：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集
二、图逻辑结构的应用
三、无向图、有向图
若E是无向边（简称边）的有限集合时，则图G为无向图。边是顶点的无序对，记为（v,w）或（w,v），其中v、w是顶点。可以说顶点w和顶点v互为邻接点。边（v,w）依附于顶点w和v，或者说边（v,w）和顶点v、w相关联。
G1 = （V1,E1）
V1 = {A,B,C,D,E}
E2 = {（A,B），（B,D），（B,E），（C,D），（C,E），（D,E）}
若E是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为
G2 = （V2，E2）
V2 = （A,B,C,D,E）
E2 = {
四、简单图、多重图
简单图——①不存在重复边；②不存在顶点到自身的边
多重图——图G中某两个节点之间的边数多以一条，又允许顶点通过同一条边和自己关联，则G为多重图。
五、顶点的度、入度、出度
无向图
顶点v的度是指依附于该顶点的边的条数，记为TD（v）。在具有n个顶点、e条边的无向图中，
，即无向图的全部顶点的度的和等于边数的2倍。
有向图
入度是以顶点v为终点的有向边的数目，记为ID（v）；
出度是以顶点v为起点的有向边的数据，记为OD（v）。
顶点v的度等于其入度和出度之和，即TD（v） = ID（v） + OD（v）。
在具有n个顶点、e条边的有向图中，
六、顶点-顶点的关系描述
路径——顶点vp到顶点vq之间的一条路径是指顶点序列vp,vk…..vq
回路——第一个顶点和最后一个顶点相同的路径称为回路或环
简单路径——在路径序列中，顶点不重复出现的路径称为简单路径
简单回路——除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
路径长度——路径上边的数目
点到点的距离——从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记为无穷。
无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的
有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的
七、连通图、强连通图
若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。
常见考点：
对于n个顶点的无向图G
①若G是连通图，则最少有n-1条边
②若G是非连通图，则最多可能有
条边。
若图中任何一对顶点都是强连通的，则称此图为强连通图。
常见考点：
对于n个顶点的有向图G
若G是强连通图，则最少有n条边（形成回路）
八、研究图的局部——子图
设有两个图G=（V，E） =和G’ =（V’，E’），若V’是V的子集，且E’是E的子集，则称G’是G的子图。
若有满足V（G’） = V（G）的子图G’，则称其为G的生成子图。
注：并非任意挑几个点、几条边都能构成子图
九、连通分量、强连通分量
极大连通子图——子图必须连通，且包含尽可能多的顶点和边
无向图中的极大连通子图称为连通分量
极大强连通子图——子图必须强连通，同时保留尽可能多的边
有向图中的极大强连通子图称为有向图的强连通分量
十、生成树
极小连通子图——边尽可能的少，但要保持连通
连通图的生成树是包含图中全部顶点的一个极小连通子图
若图中顶点树为n，则它的生成树含有n - 1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。
十一、生成森林
在非连通图中，连通分量的生成树构成了非连通图的生成森林。
十二、边的权、带权图/网
边的权——在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
带权图/网——边上带有权值的图称为带权图，也称网。
带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度
十三、带权图的应用举例
十四、几种特殊形态的图
无向完全图——无向图中任意两个顶点之间都存在边
若无向图的顶点树|V| = n,则
有向完全图——有向图中任意两个顶点之间都存在方向相反的两条弧
若有向图的顶点树|V| = n，则
稀疏图——边数很少的图
稠密图——边数很多的图
树——不存在回路，且连通的无向图
有向图——一个顶点的入度为0，其余顶点的入度均为1的有向图
常见考点
n个顶点的树，必有n-1条边
n个顶点的图，若|E| > n - 1 ，则一定有回路
十五、总结
柔光的暖阳◎
系统管理员
深藏阁楼爱情的钟
还没有评论，来说两句吧...