搜索与图论

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

一、深度优先搜索

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

1
2
3
4
5
6
7
8
9
10
void dfs(){
    /*结束条件*/
    for(){/*遍历下一个*/
        if(/*筛选条件*/){
            /*改变现场*/
        	dfs();
            /*恢复现场*/
        }
    }
}

二、广度优先搜索

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

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

三、Dijkstra算法

n个点，m条边，先找到距离顶点最短且没有被标记的点，用该点更新所有的点，把改点当成中间点，标记该点。时间复杂度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];

四、ford有边数限制的最短路

（指一号点到n号点的最短距离）

外面循环边数限制k,里面循环所有的边，方法和dijkstra一样，遍历边，用该点原来到1号的距离和该点边上的一点加边长比较，取最小的那个存下，注意要备份原来的距离。边权不为负值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct edge{
	int a,b,c;
} e[N];

int ford(){
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	for(int i=0;i<k;i++){
		memcpy(backup,dist,sizeof dist);
		for(int j=0;j<m;j++){
			int a=e[j].a,b=e[j].b,c=e[j].c;
			dist[b]=min(dist[b],backup[a]+c);
		}
	}
	if(dist[n]>0x3f3f3f3f / 2) return -1;
	else return dist[n];
	
}

五、spfa求最短路

n个点和m条边，存在负权回路，求1号点到n号点的最短距离，0<n,m<1e5;

n和m过大，邻接矩阵不合适，n*n太大了，

​