bfs-

1、猴子选大王 2、约瑟夫环 3、迷宫求解 4、回文游戏 5、地图四染色问题 6、八皇后问题 7、原四则表达式求值 8、k阶斐波那契序列 9、遍历二叉树 10、编写DFS算法的非递归

/*BFS算法的非递归函数*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define infinity 30000
#define MAX 20

int visited[MAX];                //访问标记
int (*visitFunc)(int v);         //访问函数指针

typedef struct record{  //访问点，和它的双亲的纪录，pri为双亲，nxt为自己
 int pri,nxt;
}record,*rec;

typedef struct Sq{//栈
  record*base;
  record*top;
  int stacksize;
}Sq;  

typedef struct ArcCell{//邻接矩阵
  int adj;
}AecCell,AdjMatrix[MAX][MAX];

typedef struct Mgraph{ //顶点
  char vex[MAX];
  AdjMatrix arcs;
  int vexnum,arcnum;
}Mgraph;

int InitStack(Sq &s){   //初始化栈
    s.base=(rec)malloc(MAX*sizeof(record));
    s.top=s.base;
    s.stacksize=MAX;
    return 1;
}

int push(Sq&s,record e){
   if(s.top-s.base>=s.stacksize)
     return 0;
   else
     *s.top++=e;
    return 1;
}

int pop(Sq&s,record&e){
   if(s.top==s.base)
      return 0;
   e=*--s.top;
   return 1;
}

int Create(Mgraph&G)  //建图
{
   int i,j,n=0;
   int v1,v2; 
   int LocateVex(Mgraph G,char name);
   printf("input the number of the vertex:");
   scanf("%d",&G.vexnum);
   printf("input the number of the ArcCell:");
   scanf("%d",&G.arcnum);
   for(i=0;i<G.vexnum;i++)
    for(j=0;j<G.vexnum;j++)
       G.arcs[i][j].adj=infinity;
   printf("input the ArcCell:\n");
   for(j=0;j<G.arcnum;j++)
   {  
	  scanf("%d %d",&v1,&v2);
      G.arcs[v1-1][v2-1].adj=G.arcs[v2-1][v1-1].adj=1;
   }
   return 1;
}

void BFSTraverse(Mgraph G,int (*visit)(int v))   //DFS访问全过程
{
   int v;
   void BFS(Mgraph G,int v);
   visitFunc=visit;
   
   
   printf("The graph DFSTraverse:");
   
   for(v=0;v<G.vexnum;v++)      //所有访问纪录初始为0
       visited[v]=0;
   
   for(v=0;v<G.vexnum;v++)      //访问不同连通分支
    if(!visited[v])BFS(G,v);           
}

void BFS(Mgraph G,int v)  
{
   int u;
   record r;
   struct Sq s;
   InitStack(s);
   
   visited[v]=1;//初始点访问纪录为1
   
   visitFunc(v);//print第v个节点
   
   for(u=0;u<G.vexnum;u++)
     if(G.arcs[v][u].adj!=infinity&&!visited[u])break;  //查找v的第一个没被访问的邻接节点
   
	 
	 while(u<G.vexnum||s.top-s.base!=0)
	 {
   
	  if(u<G.vexnum)
	  {
      r.pri=v;
      r.nxt=u;
      push(s,r);//记录压栈
      visited[u]=1;//新节点访问记录设为1
      visitFunc(u);//访问该节点
      
	  for(u++;u<G.vexnum;u++)//继续查找，找到下一个邻接点，break
         if(G.arcs[v][u].adj!=infinity&&!visited[u])break;
	  }
    
	  else{//栈不空（没查找到） 
      r=*(s.base++); //从栈底提出记录，并栈底指针向上移动1个        
      v=r.nxt;     //从出栈记录的邻接点继续查找
      for(u=0;u<G.vexnum;u++)
         if(G.arcs[v][u].adj!=infinity&&!visited[u])break;   
    }//若将栈退光,还没找到新路,则说明完成BFS,退出while循环
   } 
}

int print(int i)          //一种visit方式，输出
{
   printf("v%d.",i+1);
   return 1;
}

int main(int argc, char *argv[])
{
  Mgraph G;
  Create(G);
  BFSTraverse(G,print);
  printf("\n");
  system("PAUSE");	
  return 0;
}




//测试数据
//vexnum=8，arcnum=9
/*
1 2
1 3
2 4
2 5
3 6
3 7
4 8
5 8
6 7
*/