什么是图
图论（Graph theory）是数学的一个分支，它以图为研究对象，研究顶点和边组成的图形的数学理论和方法。图论中的图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用顶点代表事物，用连接两顶点的边表示相应两个事物间具有这种关系。
图论的研究对象相当于一维的拓扑学。
基本概念
- 顶点 图中结点称为结点
- 边 顶点与顶点之间有一条边
- 图的分类
- 有向图 在有向图中，顶点对
- 无向图 (x,y)(y,x)是一条边
- 有向图 在有向图中，顶点对
- 完全图
- 在有n个顶点的无向图中，若有n*(n-1)/2条边，即任意两 个两个顶点之间有且只有一条边
- 在n个顶点的有向图中，若有n*(n-1)条边，即任意两个顶 点之间有且仅有方向相反的边
- 邻接结点
- 在无向图中G中，若（u,v）是E（G）中的一条边，则称u 和v互为邻接顶点，并称（u，v）依附于顶点u和v
- 在有向图G中，若
- 顶点的度 与它相关联的边的条数
- 在有向图中，顶点的度等于该顶点的入度与出度之和，其 中顶点v的入度是以v为终点的有向边的条数，记做indev( v)顶点v的出度是以v为起始点的有向边的条数记做 outdev（v）
- 无向图的度等于入度和出度dev(v)=indev(v)=outdev( v)
- 路径
在图G=(V,E)中，若从顶点vi出发有一组边使其可到达顶
点vj，则称顶点vi到vj的顶点序列为从顶点vi到顶点vj的路 径 - 权 边附带的数据信息
- 路径长度
- 对于不带权的图，一条边的路径长度是指该路径上的边的 条数
- 对于带权的图，一条路径的长度是指一条路径的路径长度 是指该路径上各个边权值的总和
- 简单路径与回路
如路径上各个顶点均不重复，则称这样的路径是简单路 径，若路径上第一个顶点v1和最后一个顶点vm重合，则 称这样的路径为回路或环 - 子图
设图G={V,E}和图G1={V1.E1},若V1属于V且E1属于E，则称 G1是G的子图 - 连通图
无向图中，两个顶点之间有路径就是连通的，任一对顶点 之间都是连通的则称这个图是连通图 - 强连通图
在有向图中，任意一对顶点vi和vj之间都存在一条从vi到 vj的路径，也存在一条从vj到vi的一条路径 - 生成树
一个连通图的最小连通子图称作该图的生成树，有n个顶 点的连通图的生成树有n个顶点和n-1条边
图的存储结构
- 邻接矩阵
一般用两个数组来表示图。一个一维数组存储顶点信息，一个二维数组(邻接矩阵)存储图中的边或弧的信息
- 邻接表
- 无向图
- 有向图
- 无向图
图的遍历
- 深度优先
- 广度优先
最小生成树 准则
- 只能使用图中的边来构造最小生成树
- 只能使用恰好n-1条边来连接图中的n个顶点
- 选用的n-1条边不能构成回路
Kruskal算法(克鲁斯卡尔算法)
- 所有的顶点放那，每次从所有的边中找一条代价最小的，同时保证加入的边不产生圈
prim算法 (普利姆算法)
- 图的顶点分为两部分，一部分是最小生成树中的结点（A集合），另一部分是未处理的结点（B集合），每次找一条代价最小的
- 算法是用于构建最小生成树——即树中所有边的权值之和最小
单元最短路径
- 从在带权图的某一顶点出发，找出一条通往另一个顶点的 最短路径，最短也即是沿路径各边的权值和最小
- Dijkstra算法：用于计算一个节点到其他所有节点的最短路径。
- 弗洛伊德算法（Floyd算法）
- SPFA算法
若有收获，就点个赞吧
0 人点赞
