图的应用

图的应用

• 关键路径的计算中注意区分事件和活动，活动是弧尾顶点开始，事件是弧头顶点开始，就是在活动的权值（时间）结束后才能进行（下一个）事件的开始。弧的权值代表活动的时间。顶点代表事件的开始。

• 仅有一条关键路径时，减少关键活动的时间会缩短工程的工期

  • 存在多条关键路径时，缩短一条关键活动的时间不一定会缩短工程的工期

  • 缩短了路径长度的那条关键路径不一定还是关键路径

• 采用邻接表作为 AOV网的存储结构进行拓扑排序，需要对n个顶点做进栈、出栈、输出各 一次，在处理e条边时，需要检测这n个顶点的边链表的e个边结点，共需要的时间代价为O（n+ e）。

• 若采用邻接矩阵作为 AOV网的存储结构进行拓扑排序，在处理e条边时需对每个顶点检测相应矩阵中的某一行，寻找与它相关联的边，以便对这些边的入度减1，需要的时间代价为 O（n^2）。

• 设N个结点构成环，N-1条边权值相等，另一条边权值较小，则从不同的顶点开始Prim算法会得到 N-1种不同的最小生成树

• 若无向图本身就是一颗树，则最小生成树就是它本身，它是唯一的

• 当最小生成树唯一时（各边的权值不同），Prim 算法和 Kruskal 算法得到的最小生成树相同，

• 一个有向图的顶点不能排成一个拓扑序列，表明其中存在一个顶点数目大于一的回路，该回路构成一个强连通分量

• 对有向图中的顶点适当地编号，使其邻接矩阵为三角矩阵且主对角元全为零的充分必要条件是，该有向图可以进行拓扑排序

  • 若一个有向图的邻接矩阵为三角矩阵（对角线上元素为0），则图中必不存在环。因此其拓扑序列必然存在。

• 最小生成树中的n-1条边并不能保证是图中权值最小的n-1 条边，因为权值最小的n-1条边并不一定能使图连通。

• 有向无环图的拓扑序列唯一并不能唯一确定该图。