Algorithm:C++语言实现之图论算法相关(图搜索广度优先BFS、深度优先DFS,最短路径SPF、带负权的最短路径Bellman-ford、拓扑排序)
目录
一、图的搜索
1、BFS (Breadth-First-Search) 广(宽)度优先
2、DFS (Depth-First-Search) 深度优先
二、三大算法
1.1、最短路径SPF:Shortest Path First(Dijkstra)
1.2、带负权的最短路径:Bellman-ford算法
3、拓扑排序
一、图的搜索
1、BFS (Breadth-First-Search) 广(宽)度优先
1.1、单词变换问题Word ladder
1.2、周围区域问题
2、DFS (Depth-First-Search) 深度优先
2.1、回文划分问题
2.1.1、Palindrome Partitioning思考:动态规划
2.2、八皇后问题
有个//要取消掉
2.3、数独Sudoku问题
2.4、非递归数独Sudoku
3、Tarjan算法
二、三大算法
1.1、最短路径SPF:Shortest Path First(Dijkstra)
生成最短路径的贪心算法procedure SHORTEST-PATHS(v,COST,DIST,n)//G是一个n结点有向图,它由其成本邻接矩阵COST(n,n)表示。DIST(j)被置从结点v到结点j的最短路径长度,这里1≤j≤n。特殊的,DIST(v)被置成零//boolean S(1:n);real COST(1:n,1:n),DIST(1:n)integer u,v,n,num,i,wfor i←1 to n do //将集合S初始化为空//S(i) ←0;DIST(i) ←COST(v,i) //若v到i没有边,DIST(i)=∞//repeatS(v) ←1;DIST(v) ←0 //结点v计入S//for num←2 to n-1 do //确定由结点v出发的n-1条路//选取结点u,它使得DIST(u)=S(u) ←1 //结点u计入S//for 所有S(w)=0的结点w do //修改DIST(w)//DIST(w) = min(DIST(w), DIST(u) + COST(u,w))repeatrepeatend SHORTEST-PATHS
1.2、带负权的最短路径:Bellman-ford算法
2、Floyd算法
3、拓扑排序
Algorithm:C++语言实现之图论算法相关(图搜索广度优先BFS 深度优先DFS 最短路径SPF 带负权的最短路径Bellman-ford 拓扑排序)