- 邻接矩阵:每行代表一个顶点与其它各个顶点邻接的情况。
- 邻接表:^ 表示空指针 NULL,链表结点之间没有边。邻接表用链表有毛用!就应该用动态数组。。。看得烦得很
- 图的广度优先的时间复杂度搞不清楚
- 图的 BFS:出队一个元素,访问其邻接点并入队,再将队头元素出队,循环往复。
- 存在连通图的情况:外侧循环用于遍历所有非连通图。
- MST 性质搞不清楚
- 普里姆算法:划分阵营,小心发展。时间复杂度和边数无关,适合处理稀疏图
- 拓扑排可以用来判断有向图是否存在环,并给出任务的可行执行先后顺序。 拓扑排序判断图中有无环的原理:拓扑排序只处理入度为0的点,环内所有顶点入度永远不为0,无法被选出,统计到的顶点数量就会变少。
- 拓扑排序的算法实现搞不清楚
- 确定关键路径的过程搞不清楚