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的逆拓扑序列。
阅读(938) | 评论(0) | 转发(0) |
