1. 什么是有向图
2. 什么是无向图
3. 图的顶点数N与图的片数E之间的关系
若G是无向图,则0≤e≤n(n-1)/2
若G是有向图,则0≤e≤n(n-1)
4. 顶点的度,什么是出度,什么是入度?
5. 什么是路径?(包括有向图的路径和无向图的路径)
6. 什么是简单路么
7. 什么是简单回路或简单环?
8. 有根图和图的根
9. 连通图和连通分号。强连通图和强连通分量。
10. 什么是网络?
11. 图的存储结构有两种:邻接矩阵和邻接表
12. 邻接表分为有向邻接表和无向邻接表,其中有向邻接表又分为正向邻接和反向邻接
13. 图的遍历:深度优先和广度优先。其中深度优先使用堆栈的方式进行遍历,而广度优先使用队列进行遍历。
14. 图能够解决的问题有几下几种:
一、生成树和最小生成树(普里姆(Prim)算法 和 克鲁斯卡尔(Kruskal)算法)
普里姆(Prim)算法
T=(U,TE)是存放MST的集合。
①T的初值是({r},¢)
即最小生成树初始时只有一个红点r,没有红边。
②T经过n-1次如下步骤操作,最后得到一棵含n个顶点,n-1条边的
最小生成树(若蓝点与多个红点有连接,则取权值小的边作紫边)
1.选择紫边集中一条轻边并扩充进T
2.将轻边连接的蓝点改红点
3.将轻边改红边
4.修改紫边集
克鲁斯卡尔(Kruskal)算法
算法思想
①T的初始状态
只有n个顶点而无边的森林T=(V,¢ )
②按边长递增的顺序选择E中的n-1安全边(u,v)并加入T,生成MST
注意:
安全边指两个端点分别是森林T里两棵树中的顶点的边。加入安全边,可将森林 中的两棵树连接成一棵更大的树
因为每一次添加到T中的边均是当前权值最小的安全边,MST性质也能保证最终 的T是一棵最小生成树。
二、最短路径
迪杰斯特拉(Dijkstra)算法求单源最短路径
设S为最短距离已确定的顶点集(看作红点集),V-S是最短距离尚未确定的顶点 集(看作蓝点集)。
①初始化
初始化时,只有源点s的最短距离是已知的(SD(s)=0),故红点集S={s},蓝 点集为空。
②重复以下工作,按路径长度递增次序产生各顶点最短路径
在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集,以保证算法按路径长度递增的次序产生各顶点的最短路径。
当蓝点集中仅剩下最短距离为∞的蓝点,或者所有蓝点已扩充到红点集时,s到所有顶点的最短路径就求出来了。
注意:
①若从源点到蓝点的路径不存在,则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。
②从源点s到终点v的最短路径简称为v的最短路径;s到v的最短路径长度简称为v的最短距离,并记为SD(v)。
三、拓扑排序
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若
∈E(G),则u在线性序列中出现在v之前。
通常,这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列,简称拓扑序列。
无前趋的顶点优先的拓扑排序方法
该方法的每一步总是输出当前无前趋(即人度为零)的顶点,其抽象算法可描述为:
NonPreFirstTopSort(G){//优先输出无前趋的顶点
while(G中有人度为0的顶点)do{
从G中选择一个人度为0的顶点v且输出之;
从G中删去v及其所有出边;
}
if(输出的顶点数目<|V(G)|)
//若此条件不成立,则表示所有顶点均已输出,排序成功。
Error("G中存在有向环,排序失败!");
}
无后继的顶点优先拓扑排序方法
该方法得到的是一个逆序的拓扑,可以通过堆栈来实现拓扑排序
利用深度优先遍历对DAG拓扑排序
当从某顶点v出发的DFS搜索完成时,v的所有后继必定均已被访问过(想像它们均已被删除),此时的v相当于是无后继的顶点,因此在DFS算法返回之前输出顶点v即可得到 DAG的逆拓扑序列。
阅读(1094) | 评论(0) | 转发(0) |