dfs

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

//DFS非递归算法

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define infinity 30000//若边的权值为infinity，此边为空边
#define MAX 20

int visited[MAX];

int (*visitFunc)(int v);//函数变量

typedef struct record{//栈节点类型
 int pri,nxt;//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,value,n=0;
   int v1,v2; 
   
   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:<like this:0 2 36>\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;// 无向-对称。。。输入值为1到vexnum---->数组的标号减一
   }
   return 1;//建图成功返回1
}



void DFSTraverse(Mgraph G,int (*visit)(int v))
{
   int v,u;
   void DFS(Mgraph G,int v);//声明
   
   visitFunc=visit;
   
   printf("The graph DFSTraverse:");
   for(v=0;v<G.vexnum;v++)//清空visited访问记录
       visited[v]=0;
   for(v=0;v<G.vexnum;v++)
      if(!visited[v])DFS(G,v);           
}



void DFS(Mgraph G,int v)
{
   int u;
   
   record r;
   
   struct Sq s;
   
   InitStack(s);
   
   visited[v]=1;//访问第v个节点
   
   visitFunc(v);//print(v)
   
   for(u=0;u<G.vexnum;u++)
     if(G.arcs[v][u].adj!=infinity&&!visited[u])break;//找第一个邻接点
	                                                  //若访问边的权值不为infinity即此边不是空边，且u点未曾访问,break
   
   while(u<G.vexnum||s.top-s.base!=0)
   {
    if(u<G.vexnum)//通过循环遍历节点
	{
      r.pri=v;
      r.nxt=u;
      push(s,r);
      v=u;
      visited[v]=1;
      visitFunc(v);
      for(u=0;u<G.vexnum;u++)                             //找第一个邻接点
         if(G.arcs[v][u].adj!=infinity&&!visited[u])break;//若访问边的权值不为infinity即此边不是空边，且u点未曾访问,break
    }//若找不到可访问的邻接点，u=vexnum
    else{//若u=vexnum，说明此条路线到尽头
      pop(s,r);//退栈,寻找新路
      v=r.pri;
      for(u=r.nxt;u<G.vexnum;u++)
         if(G.arcs[v][u].adj!=infinity&&!visited[u])break;//若将栈退光,还没找到新路,则说明完成DFS,退出while循环  
    }
   } 
}

int print(int i)
{
   printf("v%d.",i+1);
   return 1;
}




int main()
{
  Mgraph G;
  
  
  Create(G);
  
  DFSTraverse(G,print);
  
  printf("\n");
  
  return 0;
}
//测试数据
//vexnum=8，arcnum=9
/*
1 2
1 3
2 4
2 5
3 6
3 7
4 8
5 8
6 7
*/