图的遍历
深度优先遍历(DFS,Depth-First Search)
访问给定顶点v
访问v的第一个未访问临顶点w
访问w的第一个未访问临顶点...
广度优先遍历(BFS,Breadth-First Search)
访问给定顶点v
访问v所有的临顶点w
访问w所有的临顶点...
最小生成树：
Prim：选取一个点，找到权最小的边，把新点、边、旧的顶点看成一个整体，重复，直至连通了所有点
Kruskal：每次选取权最小且不与已选边构成回路的边，直至连通了所有点
对于存在权相等边的图
最短路径
Dijkstra算法求单源最短路径
Floyd算法求所有源最短路径
拓扑排序
网友评论