BFS,DFS,DIJKSTRA算法基础练习

发布时间:2016-12-8 15:48:10 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"BFS,DFS,DIJKSTRA算法基础练习",主要涉及到BFS,DFS,DIJKSTRA算法基础练习方面的内容,对于BFS,DFS,DIJKSTRA算法基础练习感兴趣的同学可以参考一下。

今天,好好看了下算法导论,根据给出的伪代码,实现了BFS,DFS,SSSP的基本模型~今天好好联系下三种算法的实际应用。 我的思路是:首先理解伪代码,了解证明过程,再通过应用加深了解。 #include<iostream> #include<string.h> using namespace std; #define INF 100000000 #define maxN 40 int a[maxN][maxN],n; int d[maxN],fa[maxN],v[maxN],q[maxN*maxN],visited[maxN*maxN]; void bfs(int s){//初始化所有节点为白色 int front=0,rear=0; int x=s/n,y=s%n; if(a[x][y]>=0){ q[rear++]=s;//使用编号(代替坐标)存储,出队时分解为坐标 visited[s]=1;//入队->标记灰色 } while(front<rear){ int u=q[front++]; x=u/n; y=u%n; cout<<a[x][y]<<" "; int dx[4]={-1,1,0,0}; int dy[4]={0,0,1,-1}; int nx,ny; int i,cur; for(i=0;i<4;i++){ nx=x+dx[i];ny=y+dy[i];//循环取下一个节点 cur=nx*n+ny; if(nx>=0&&nx<n&&ny>=0&&ny<n&&a[nx][ny]>=0&&!visited[cur]){//判断下一个节点是否可访问 q[rear++]=cur;//入队->标记灰色 visited[cur]=1; } } visited[u]=2;//访问完->标记黑色 } } void dfs(int x,int y){ int u=x*n+y; if(x<0||x>=n||y<0||y>=n||a[x][y]==-1||visited[u])//不可访问时返回 return; visited[u]=1;//标记已访问 cout<<a[x][y]<<" "; dfs(x+1,y); dfs(x-1,y); dfs(x,y+1); dfs(x,y-1); } void DIJKSTRA(int s){ //初始化:集合S为空,估计值为最大,前驱子图为空 //循环n次,将所有点加入S,每一次将d值最小的加入 int i,j; for(i=0;i<n;i++){ d[i]=INF; fa[i]=-1; } d[s]=0; int min; int x; for(i=0;i<n;i++){//第i次迭代 min=INF; for(j=0;j<n;j++){ if(d[j]<min&&!v[j]) min=d[x=i]; } v[x]=1;//加入S for(j=0;j<n;j++) { if(a[x][j]!=-1&&d[j]>d[x]+a[x][j]) { fa[j]=x; d[j]=d[x]+a[x][j]; } } } } void print(int x){//递归打印路径 if(fa[x]==-1){ cout<<x; return; } print(fa[x]); cout<<"->"<<x; } int main(){ int i,j; freopen("result.txt","r",stdin);//使用文件输入 memset(visited,0,sizeof(visited));//初始化为白色 cin>>n; for(i=0;i<n;i++){ for(j=0;j<n;j++) cin>>a[i][j]; } bfs(0);//从(0,0)开始广度优先搜索连通子图 memset(visited,0,sizeof(visited)); cout<<endl; dfs(0,0);//从(0,0)开始深度优先搜索连通子图 memset(v,0,sizeof(v)); DIJKSTRA(0);//从点0开始的单源最短路径 cout<<endl; for(i=0;i<n;i++){ print(i); cout<<" cost:"<<d[i]; cout<<endl; } }

上一篇:使用String.split拆分多个空格的问题
下一篇:一种排序 sort cmp STL

相关文章

相关评论