图
图的定义:图是由顶点的有穷非空集合和顶点之间边的集合组成,表示为G(V,E) 翻译一下Graph(Vertex,Edge)
注意点:(1)线性表中数据元素称为元素,树中数据元素称为结点,图中的数据元素称为顶点
(2)图中不允许没有顶点,即顶点集合V有穷非空,但边集V可以是空的。
无向边:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边,用无序偶对(Vi,Vj)来表示
无向图:如果图中所有的边都是无向边,则称该图为无向图
无向完全图:无向图中任意两个顶点之间都存在边,称为完全无向图。含n个顶点的完全无向图有n*(n-1)/2条边
有向边:若有顶点Vi指向Vj的边,则称这条边为有向边,,用有序偶对<Vi,Vj>来表示
有向图:如果图中所有的边都是有向边,则称该图为有向图(显而易见hh)
有向完全图:在有向图中,如果任意两个顶点之间都存在方向相反的两条有向边,则称为有向完全图,共有n*(n-1)条边
简单图:若不存在从一个节点出发,可以回到该点自身的边的集合(回环),且两个点之间不存在两个以上的边(重边)
稀疏图:边不多
稠密图:边很多
顶点的度:无向图中和该顶点想关联的边的数目
出度:在有向图中该顶点被指向的箭头个数,就是它的入度
入度:在有向图中从这个顶点指出去的箭头个数,就是它的出度
性质:出度和等于入度和
路径:从一个顶点到另一个顶点所经历的顶点序列,路径的长度是路径上边的数目
回路(环):第一个顶点和最后一个顶点相同的路径称为回路
子图:
连通图:在无向图G中。如果从顶点v1到顶点v2有路径,则称v1和v2是连通的,如果对于图中任意两个顶点都是联通的,则该图称为连通图。
连通分量:无向图中的最大连通子图称为连通分量
强连通图:在有向图中,如果从任意两个顶点v1和v2,都分别有v1到v2的路径和v2到v1到路径,则称为强连通图
强连通分量:
连通图的生成树:一个连通图的生成树是一个极小连通子图,它含有图中的n个顶点,但只有足以构成一棵树的n-1条边。
图的遍历
概念:从图中某一顶点出发访遍图中其余结点,且使每一个顶点仅被访问一次,这一过程称为图的遍历
深度优先遍历(DFS):选定一个出发点后进行遍历,能前进则前进,若不能前进,回退一步再前进,或再回退一步后继续前进。依此重复,直到所有与选定点相通的所有顶点都被遍历。
广度优先遍历(BFS):首先把起点相邻的几个点探索完成,然后去探索距离起点稍远一些(隔一层)的点,然后再去玩探索距离起点更远一些(隔两层)的点,是一层一层的向外探索。
最小生成树
概念:构造连通图的最小代价生成树称为最小生成树
Prim算法:以某顶点为起点,逐步寻找各个顶点上最小权值的边来构建最小生成树
Kruskal算法:将所有边按从小到大排序,逐步选中最小权值的边,构建时需要考虑是否会形成环路
最短路径
概念:对于网图来说,最短路径指的是两顶点之间经过的边上权值之和最小的路径。
Dijkstra算法:基于已经求出的最短路径的基础上,求得更远顶点的最短路径
Flyod算法:每一个顶点都是出发访问点,所以需要将每一个顶点看做被访问顶点,求出从每一个顶点到其他顶点的最短路径
最近看y总图论那里理论方面有点忘记,就记录下,先把算法详细写完再把这篇更完,有错的话大家指教下