【笔记】图学习笔记
前言
图学习笔记
图的定义
- 由一组顶点和一组能够将两个顶点相连的边组成
特殊的图
自环
- 即一条连接一个顶点和其自身的边
平行边
- 连接同一对顶点的两条边
图的分类
无向图
- 边仅仅连接两个顶点，没有其他含义
有向图
- 边不仅连接两个顶点，并且具有方向
图的相关术语
相邻顶点
- 当两个顶点通过一条边相连时，我们称这两个顶点是相邻的，并且称这条边依附于这两个顶点
度
- 某个顶点的度就是依附于该顶点的边的个数
子图
- 是一幅图的所有边的子集（包含这些边依附的顶点）组成的图
路径
- 是由边顺序连接的一系列的顶点组成
环
- 是一条至少含有一条边且终点和起点相同的路径
连通图
- 如果图中任意一个顶点都存在一条路径达到另外一个顶点，那么这幅图就称之为连通图
连通子图
- 一个非连通图由若干连通的部分组成，每一个连通的部分都可以成为该图的连通子图
无向图
邻接矩阵
- 用二维数组的横纵坐标分别表示两个点，存储在坐标位置的值表示是(1)否(0)相连
邻接表
- 用一个数组存放其中一个点，在这个点内存放一个队列，这个队列内存放的是与这个点相邻的另外其他点
有向图
有向图的定义
- 有向图是一副具有方向性的图，是由一组顶点和一组有方向的边组成，每条方向的边都连着一对有序的点
有向图的术语
出度：由某个顶点指出的边的个数称为该顶点的出度
入度：指向某个顶点的边的个数称为该顶点的入度
有向路径：由一系列顶点组成，对于其中的每个顶点都存在一条有向边，从它指向序列中的下一个顶点
有向环：一条至少含有一条边，且起点和终点相同的有向路径
两个顶点可能出现的关系
- 没有相连
- 存在一个顶点到另一个顶点的边
- 存在另一个顶点到一个顶点的边
- 既存在一个顶点到另一个顶点的边，又存在另一个顶点到一个顶点的边