dfs.cpp

本人还是初学者

#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{
 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,value,n=0;
   int v1,v2; 
   int LocateVex(Mgraph G,char name);//G.vexnum=3;G.arcnum=3;
   printf("请输入顶点数:");
   scanf("%d",&G.vexnum);
   printf("请输入弧数:");
   scanf("%d",&G.arcnum);
   //printf("input the vertex:");
   /*for(i=0;i<G.vexnum;i++)
      scanf("%c",&G.vex[i]);*/
    //G.vex[0]='a';
    //G.vex[1]='b';
    //G.vex[2]='c';
   for(i=0;i<G.vexnum;i++)
    for(j=0;j<G.vexnum;j++)
       G.arcs[i][j].adj=infinity;
   printf("请对弧结点赋值:<like this:0 1 n>\n");
   for(j=0;j<G.arcnum;j++)
   {  
	  scanf("%d %d %d",&v1,&v2,&value);
      //i=LocateVex(G,v1);
      //j=LocateVex(G,v2);printf("%d,%d\n",i,j);
      G.arcs[v1][v2].adj=G.arcs[v2][v1].adj=value;
   }
   return 1;
}

void DFSTraverse(Mgraph G,int (*visit)(int v))
{
   int v,u;
   void DFS(Mgraph G,int v);
   visitFunc=visit;
   printf("DFS遍历图为:");
   for(v=0;v<G.vexnum;v++)
       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;
   visitFunc(v);
   for(u=0;u<G.vexnum;u++)
     if(G.arcs[v][u].adj!=infinity&&!visited[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;
    }
    else{
      pop(s,r);
      v=r.pri;
      for(u=r.nxt;u<G.vexnum;u++)
         if(G.arcs[v][u].adj!=infinity&&!visited[u])break;   
    }
   } 
}

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

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