今天小编为各位2023考研的考生整理了数据结构考试的一些知识点——图的基础知识，并以表格的形式为大家进行展示，方便大家理解和记忆，希望能够帮助大家更好地备考数据结构，取得好成绩。
| 基本概念 | 定义 |
| 边、弧 | 边是顶点的无序对，记为(v，w)或(w，v)。弧是顶点的有序对，记为<v，w>，v称为弧尾，w称为弧头 |
| 无向图 | 若E是无向边(简称边)的有限集合时，则图G为无向图 |
| 有向图 | 若E是有向边(也称弧)的有限集合时，则图G为有向图 |
| 顶点的度、 入度、出度 |
图中每个顶点的度定义为以该顶点为一个端点的边的数目 对于无向图，顶点v的度是指依附于该顶点的边的数量，记为TD(v) 对于有向图，顶点v的度分为入度和出度，入度是以v为终点的有向边的数目，记为ID(v)：出度是以v为起点的有向边的数目，记为OD(v)。顶点v的度等于入度和出度之和，即TD(v)=ID(v)+OD(v) |
| 连通、连通图、连通分 | 在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。若图G中任意两个顶点都是连通的，则称图G为连通图，否则为非连通图 无向图中的极大连通子图称为连通分量 |
| 强连通、强连通图、强 连通分量 |
在有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的。若图中任意一对顶点都是强连通的，则称此图为强连通图 有向图中的极大强连通子图称为有向图的强连通分量 |
| 完全图 | 在无向完全图中，任意两个顶点之间都存在边，共有n(n-1)／2条边在有向完全图中，任意两个顶点之间都存在方向相反的两条弧，共有n(n-1)条有向边 |
| 子图 | 设有两个图G=(V，E)和Gl=(v′，E′)，若V′是V的子集，且是E的子集，则称G，是G的子图注意：不是任意V′，E′都能构成子图，前提是V′，E′必须能够构成图 |
| 生成树、 生成森林 |
连通图的生成树是包含图中全部顶点的一个极小连通子图 在非连通图中，连通分量的生成树构成了非连通图的生成森林 |
以上就是数据结构之图的基础知识的相关介绍，大家可以继续关注启航教育考研备考栏目，获取更多实用备考信息。
【26考研辅导课程推荐】：26考研集训课程,VIP领学计划,26考研VIP全科定制套餐（公共课VIP＋专业课1对1） , 这些课程中都会配有内部讲义以及辅导书和资料，同时会有教研教辅双师模式对大家进行教学以及督学，并配有24小时答疑和模拟测试等，可直接咨询在线客服老师领取大额优惠券。
热门下载
资料下载
院校解析
真题解析
考研数学
考研英语
考研政治
考研备考
资讯
备考
747
25考研
26考研
精选课程
