请求高手帮忙看下深度优先遍历的代码 ??????急急急.........

nagu 发布于 2011/08/16 10:46
阅读 459
收藏 0
#include <stdio.h> 
#include <stdlib.h>
 #include <string.h>
 #include<conio.h>
 #include<math.h>
 #define TRUE 1
 #define FALSE 0
 #define OK 1
 #define ERROR 0
 #define NULL 0
 #define MAX_VErR_NUM 10  
#define QueueSize 30 

/*邻接矩阵存储表示定义*/  
typedef enum{False,True}Boolean;   
Boolean visited[MAX_VErR_NUM];  
typedef char VertexType;   
typedef int EdgeType;   
typedef struct     
{   
    VertexType vexs[MAX_VErR_NUM];  //顶点表   
    EdgeType arcs[MAX_VErR_NUM][MAX_VErR_NUM ];//邻接矩阵,可看做边表   
    int n,e;    //图中当前的顶点数和边数   
}MGraph;   
  
/*邻接表定义*/
 typedef struct Node
 {
  int elem;
     struct Node *next;
 }Node,*QNode;

typedef struct
 {
  QNode front;
     QNode rear;
 }Queue;

typedef struct ArcNode       /*头节点*/
 {
  int adjvex;              /*该边所指向的顶点的位置*/
     struct ArcNode *nextarc; /*指向下一条边*/
 }ArcNode;

typedef struct VNode           /*表节点*/
 {int data;                /*顶点信息*/
 ArcNode *firstarc;       /*指向第一条依附该节点的边的指针*/
 }VNode,AdjList[MAX_VErR_NUM ];

typedef struct
 {AdjList vertices;     /*表节点*/
 int vexnum;           /*节点的个数*/
 int arcnum;           /*边的条数*/
 }Graph;

int Visited[MAX_VErR_NUM];

 

/* 邻接矩阵的存储*/
  
 void CreateMGraph(MGraph *G)   
{    
    int i,j,k;   
    VertexType ch1,ch2;   
    printf("输入顶点数和边数(中间以空格隔开):\n"); 
 fflush(stdin);
     scanf("%d%d",&(G->n),&(G->e));   
    printf("输入顶点号每个顶点以空格作为结束:\n");   
    for(i=0;i<G->n;i++)   
    {   
        getchar();
   scanf("%c",&(G->vexs[i]));   
    }   
    for(i=0;i<G->n;i++)   
        for(j=0;j<G->n;j++)   
            G->arcs[i][j]=0;   
        printf("请输入每条边对应的两个顶点的序号(输入格式为:i,j):\n");   
        for(k=0;k<G->e;k++)   
        {   
            printf("请输入第%d条边的顶点序号:",k+1);
    fflush(stdin);
             scanf("%c,%c",&ch1,&ch2);   
            for(i=0;ch1!=G->vexs[i];i++);   
            for(j=0;ch2!=G->vexs[j];j++);   
            G->arcs[i][j]=1;   
        }   
}   


/*邻接矩阵的深度优先遍历搜索*/
   
void DFSM(MGraph *G,int i)   
{   
    int j;   
    printf("v%c ",G->vexs[i]); 
    visited[i]=True;           
    for(j=0;j<G->n;j++)           //依次搜索vi邻接点   
        if(G->arcs[i][j]==1 && !visited[j])   
            DFSM(G,j);   
}   

void DFSTraverseM(MGraph *G)   
{   
    int i;   
    for(i=0;i<G->n;i++)   
        visited[i]=False;      
    for(i=0;i<G->n;i++)   
        if(!visited[i])    
            DFSM(G,i);   
}   

/* 邻接矩阵的广度优先遍历搜索*/                                       
 typedef struct  
{   
    int front;   
    int rear;   
    int count;   
    int data[QueueSize];   
}CirQueue;   
  
void InitQueue(CirQueue *Q)   
{   
    Q->front=Q->rear=0;   
    Q->count=0;   
}   
  
int QueueEmpty(CirQueue *Q)   
{   
    return Q->count=QueueSize;   
}   
  
int QueueFull(CirQueue *Q)   
{   
    return Q->count==QueueSize;   
}   
  
void EnQueue(CirQueue *Q,int x)   
{    
    if (QueueFull(Q))   
        printf("Queue overflow");   
    else  
    {    
        Q->count++;   
        Q->data[Q->rear]=x;   
        Q->rear=(Q->rear+1)%QueueSize;   
    }   
}   
int DeQueue(CirQueue *Q)   
{   
    int temp;   
    if(QueueEmpty(Q))   
    {    
        printf("Queue underflow");   
        return NULL;   
    }   
    else  
    {   
        temp=Q->data[Q->front];   
        Q->count--;   
        Q->front=(Q->front+1)%QueueSize;   
        return temp;   
    }   
}   
void BFSM(MGraph *G,int k)   
{    
    int i,j;   
    CirQueue Q;   
    InitQueue(&Q);   
    printf("v%c ",G->vexs[k]);
     visited[k]=True;   
    EnQueue(&Q,k);   
    while (!QueueEmpty(&Q))   
    {   
        i=DeQueue(&Q);   
        for (j=0;j<G->n;j++)   
            if(G->arcs[i][j]==1&&!visited[j])   
            {   
                printf("广度优先遍历结点:%c\n",G->vexs[j]);   
                visited[j]=True;   
                EnQueue(&Q,j);   
            }   
    }   
}   
void BFSTraverseM(MGraph *G)   
{   
    int i;   
    for (i=0;i<G->n;i++)   
        visited[i]=False;   
    for (i=0;i<G->n;i++)   
        if (!visited[i])    
            BFSM(G,i);   
}   
  

/*邻接表*/
 void InitQueue(Queue *Q)  /*初始化操作*/
 {
 Q->front=Q->rear=(QNode)malloc(sizeof(Node));
 if(!Q->front) exit(OVERFLOW);
 Q->front->next=NULL;
 }

void EnQueue(Queue *Q,int e)  /*进队操作*/
 {
 QNode p=(QNode)malloc(sizeof(Node));
 if(!p) exit(OVERFLOW);
 p->elem=e;
 p->next=NULL;
 Q->rear->next=p;
 Q->rear=p;
 }

 

void DeQueue(Queue *Q,int *e)   /*出队操作*/
 {
 QNode p;
 p=Q->front->next;
 Q->front->next=p->next;
 if(Q->rear==p)
        Q->rear=Q->front;
 *e=p->elem;
 free(p);
 }

int QueueEmpty(Queue Q)
 {
 if(Q.rear==Q.front) return TRUE;
 else return -1;
 }

 

int LocateVex(Graph *G,int v)    /*返回节点v在图中的位置*/
 {int i;
 for(i=0;i<G->vexnum;++i)
    if(G->vertices[i].data==v) break;
       else continue;
 if(i<G->vexnum) return i;
     else return 0;
 }

 

/*邻接表创建*/
 void CreateGraph(Graph *G)
 {
  int m,n,i,j,k,v1,v2,flag=0;
 ArcNode *p1,*q1,*p,*q;
 printf("请输入有向图的顶点数目: ");
 scanf("%d",&m);
 printf("请输入有向图的边的数目: ");
 scanf("%d",&n);
 G->vexnum=m;            /*顶点数目*/
 G->arcnum=n;            /*边的数目*/
 for(i=0;i<G->vexnum;++i)
     {G->vertices[i].data=i+1;      /*顶点信息*/
      G->vertices[i].firstarc=NULL;
     }
    
  for(k=0;k<G->arcnum;++k)
     {printf("请输入第 %d 条边的起点和终点(中间以空格隔开): ",k+1);
      scanf("%d%d",&v1,&v2);
      i=LocateVex(G,v1);
      j=LocateVex(G,v2);
      if(i>=0&&j>=0)
        {++flag;
         p=(ArcNode *)malloc(sizeof(ArcNode));
         p->adjvex=j;
         p->nextarc=NULL;
 if(!G->vertices[i].firstarc) G->vertices[i].firstarc=p;
           else{for(p1=G->vertices[i].firstarc;p1->nextarc;p1=p1->nextarc);
                p1->nextarc=p;
               }
      q=(ArcNode *)malloc(sizeof(ArcNode));
      q->adjvex=i;
      q->nextarc=NULL;
      if(!G->vertices[j].firstarc) G->vertices[j].firstarc=q;
        else{for(q1=G->vertices[j].firstarc;q1->nextarc;q1=q1->nextarc);
      q1->nextarc=q;
     }
     }
      else{printf("Not hava this edge!\n");
    k=flag;
 }
     }
 }
 int FirstAdjVex(Graph G,int v)/*返回v的第一个邻接顶点*/
 {
 if(G.vertices[v].firstarc)
       return G.vertices[v].firstarc->adjvex;
 else
       return -1;
 }

int NextAdjVex(Graph G,int v,int w)/*返回v中相对于w的下一个邻接顶点*/
 {int flag=0;
 ArcNode *p;
 p=G.vertices[v].firstarc;
 while(p)
 {
    if(p->adjvex==w)
    {
     flag=1;
     break;
    }
    p=p->nextarc;
 }
 if(flag && p->nextarc)
    return p->nextarc->adjvex;
 else
    return -1;
 }

/*邻接表深度优先遍历*/
 void DFS(Graph G,int v)
 {int w;
 Visited[v]=TRUE;
 printf("v%d ",G.vertices[v].data);
 for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
    if(!Visited[w]) DFS(G,w);
 }

void DFSTraverse(Graph G)
 {int v;
 for(v=0;v<G.vexnum;++v)
      Visited[v]=FALSE;
 for(v=0;v<G.vexnum;++v)
      if(!Visited[v]) DFS(G,v);       
}

/*邻接表广度优先遍历*/
 void BFSTraverse(Graph G)/*广度优先遍历*/
 {int v,v1,w;
 Queue q;        
for(v=0;v<G.vexnum;++v)
     Visited[v]=FALSE;
 InitQueue(&q);   
for(v=0;v<G.vexnum;++v)
    if(!Visited[v])
    {Visited[v]=TRUE;
     printf("v%d ",G.vertices[v].data);
     EnQueue(&q,v);   /*第一个顶点入队*/
     while(!QueueEmpty(q))
          {DeQueue(&q,&v1); /*第一个顶点出对*/
           for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,w))
              if(!Visited[w]){Visited[w]=TRUE;
                              printf("v%d ",G.vertices[w].data);
                       EnQueue(&q,w);
                             }
          }
    }
 }


 void main()   
{ 
 int a,flag=1;
     MGraph G;
     Graph g;
  printf("1 对邻接矩阵进行深度优先遍历与广度优先遍历 \n2 对邻接表进行深度优先遍历与广度优先遍历 \n3 退出 \n");
     while(flag)
  {
   printf("请选择:");
         scanf("%d",&a);
      switch(a)
   {
   case 1:
    CreateMGraph(&G); 
         printf("深度优先遍历结点: ");
             DFSTraverseM(&G);
          printf("\n");
          printf("广度优先遍历结点:"); 
            BFSTraverseM(&G); 
         printf("\n");
    break;
   case 2:
    CreateGraph(&g);
             printf("深度优先搜索为:\n");
             DFSTraverse(g);
             printf("\n");
             printf("广度优先搜索为:\n");
             BFSTraverse(g);
             printf("\n");
       break;
   case 3:
    flag=0;
    break;
   }
  }
     
} 

程序运行后,按以下步骤执行,为什麽是这样?

选择1->输入"8 9"->再输入"1 2 3 4 5 6 7 8"->依次输入边数的顶点是:2,4、5,8、4,8、2,5、1,2、3,6、1,3、6,7、3,7  深度优先遍历的结果是:v1 v2 v4 v8 v5 v3 v6 v7   但是我根据程序的执行步骤,算出的结果是:v1 v2 v4 v8 v3 v6 v7 v5.  v5在最后面,为什麽会这样呢?请求高手解释...

 

加载中
返回顶部
顶部