搜索与图论

学习内容：DFS, BFS, Dijstra ford,spfa,Floyd,prim,kuuskal算法，图论。点击这里开始学习。

一、深度优先搜索

​ 递归实现深度优先搜索，适用于全排列。著名问题有n-皇后问题。

void dfs(){
    /*结束条件*/
    for(){/*遍历下一个*/
        if(/*筛选条件*/){
            /*改变现场*/
        	dfs();
            /*恢复现场*/
        }
    }
}

二、广度优先搜索

​ 通过队列实现每一级的搜索，可以解决最短路的问题。比如走迷宫，华容道问题。遍历每一个结点，然后由结点产生下一个结点。判断该点是否符合题意

void bfs(){
    queue<int> q;
    while(/*遍历结点一般是q.size()*/){
    	int t=q.fornt();
        q.pop();
        if(/*判断t能否符合题意*/)
        for(/*遍历t能产生的结点*/) 
            /*加入队列*/
    }
    
}

三、Dijkstra算法

先找到距离顶点最短且没有被标记的点，用该点更新所有的点，把改点当成中间点，标记该点。时间复杂度O(mlog(n))
d[v]表示v到根的的距离
if (d[v] > d[u] + g[u][v] && g[u][v] != INF) 
            d[v] = d[u] + g[u][v];

​

Donate