广度优先搜索与深度优先搜索

落日映苍穹つ 2022-07-16 06:43 188阅读 0赞

**广度优先搜索使用的是步步为营的策略，每执行一步循环就会把所有可能的情况加入队列，直到调出循环。适用于求最短的问题。**

**深度优先搜索则是依次遍历每一种情况，直至找到问题的解。**

**深度优先搜索和广度优先搜索都属于穷竭法。在运行内存空间上面，广度优先搜索与情况数成正比，而深度优先搜索与递归深度成正比。**

#include <iostream>
    #include <queue>
    using namespace std;
    int G[100][100];
    int D[100];
    int P[100];
    bool M[100];
    void BFS(int G[][],int D[],int P[],int M[],int s)
    {
    	int n;//n个点
    	for(int i=1;i<n;i++)
    	{
    		M[i]=true;
    	}
    
    	D[s]=0;
    	M[s]=false;
    	queue<int> Q;
    	Q.push(s);
    
    	while(!Q.empty())
    	{
    		int u=Q.front();
    		Q.pop();
    
    		for(int v=1;v<=n;v++)
    			if(G[u][v]>0&&M[v])
    			{
    				Q.push(v);
    				M[v]=false;
    				P[v]=u;
    				D[v]=D[u]+1;
    			}
    	}
    }
    
    void print_path(int P[],int s,int v)
    {
    	if(s==v)
    	{
    		cout<<s;
    		return;
    	}
    	else
    	{
    		print_path(P,s,P[v]);
    		cout<<v;
    	}
    }

#include <iostream>
    using namespace std;
    int G[100][100];
    bool M[100];
    int D[100];
    int F[100];
    int P[100];
    int time=0;
    void DFS(int G[][],int M[])
    {
    	for(int i=1;i<=100;i++)
    		M[i]=true;
    
    
    	for(int u=1;u<=100;u++)
    		if(M[u]) dfs_visit(G,u);
    }
    void dfs_visit(int G[][],int u)
    {
    	time+=1;
    	D[u]=time;
    	M[u]=false;
    
    	for(int v=1;v<=100;v++)
    	{
    		if(M[v]&&G[u][v]>0)
    		{
    			P[v]=u;
    			dfs_visit(G,v);
    		}
    	}
    
    	time+=1;
    	F[u]=time;
    }

队列：\#include<queue>

申请队列：queue<type>q;

判队空：q.empty();

获取队头元素：q.front()；

入队：q.push();

出出队：q.pop();

栈：\#include<stack>

申请栈：stack<type>s;

入栈：s.push();

出栈：s.pop();

获取栈顶元素：s.top();

判栈空：s.empty();