Algorithm：C++语言实现之图论算法相关(图搜索广度优先BFS、深度优先DFS，最短路径SPF、带负权的最短路径Bellman-ford、拓扑排序)

Algorithm：C++语言实现之图论算法相关(图搜索广度优先BFS、深度优先DFS，最短路径SPF、带负权的最短路径Bellman-ford、拓扑排序)

一、图的搜索

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,w
    for i←1 to n do //将集合S初始化为空//
        S(i) ←0;DIST(i) ←COST(v,i) //若v到i没有边，DIST(i)=∞//
    repeat
    S(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))
        repeat
    repeat
end SHORTEST-PATHS

1.2、带负权的最短路径：Bellman-ford算法

2、Floyd算法

3、拓扑排序

赞 (0)

相关推荐