这个有向图广度优先遍历哪里错了帮忙看看 - 数据结构与算法

已结贴√ 问题点数：10 回复次数：8

这个有向图广度优先遍历哪里错了帮忙看看

#include <stdio.h>
#include <malloc.h>
#define MAX_VERTEX_NUM 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int VRType;
typedef char VertexType;
typedef char InfoType;
typedef enum {DG,DN,UDG,UDN}GraphKind;
typedef char QElemType;
int visited[MAX_VERTEX_NUM];
typedef struct ArcCell
{
    VRType adj;
    InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
    VertexType vexs[MAX_VERTEX_NUM];
    AdjMatrix arcs;
    int vexnum,arcnum;
    GraphKind kind;
}MGraph;
typedef struct QNode
{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
Status InitQueue(LinkQueue &Q)
{
   Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
   if(!Q.front) return ERROR;
   Q.front->next=NULL;
   return OK;
}
Status EnQueue(LinkQueue &Q,QElemType e)
{
    QueuePtr p;
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p) return ERROR;
    p->data=e;
      p->next=NULL;
       Q.rear->next=p;
       Q.rear=p;
    return OK;
}
Status DeQueue(LinkQueue &Q,QElemType &e)
{
     QueuePtr p;
  if(Q.front==Q.rear)
        return ERROR;
  p=Q.front->next;
  Q.front->next=p->next;
  if(Q.rear==p)
      Q.rear=Q.front;
  free(p);
  return OK;
}
int LocateVex(MGraph G,VertexType v)
{
     int j=-1,k;
     for(k=0;k<G.vexnum;k++)
         if(G.vexs[k]==v)
        {
            j=k;
            break;
        }
     return j;
}
Status CreateUDN(MGraph &G)
{
    int i,j,k;
    VertexType v1,v2;
    scanf("%d%d",&G.vexnum,&G.arcnum);
    getchar();
    for(i=0;i<G.vexnum;i++)
        scanf("%c",&G.vexs[i]);
    for(i=0;i<G.vexnum;i++)
    for(j=0;j<G.vexnum;j++)
        G.arcs[i][j].adj=0;
      for (k=0;k<G.arcnum;k++)
      {
          getchar();
        scanf("%c%c",&v1,&v2);
        i=LocateVex(G,v1);j=LocateVex(G,v2);
        G.arcs[i][j].adj=1;
      }
      return OK;
}
Status first(MGraph G,int v)
{
    int j;
    for(j=0;j<G.vexnum;j++)
        if(G.arcs[v][j].adj==1)
            return j;
        return -1;
}
Status next(MGraph G,int v,int w)
{
    int j;
    for(j=w+1;j<G.vexnum;j++)
        if(G.arcs[v][j].adj==1)
            return j;
        return -1;
}
void guangdu(MGraph G)
{
    int j,w,v;
    LinkQueue Q;
    for(v=0;v<G.vexnum;v++)
        visited[v]=0;
    InitQueue(Q);
    for(v=0;v<G.vexnum;v++)
        if(!visited[v])
        {
          visited[v]=TRUE;
          printf("%c",G.vexs[v]);
          EnQueue(Q,G.vexs[v]);
        while(Q.front!=Q.rear)
        {
           DeQueue(Q,G.vexs[v]);
           for(w=first(G,v);w!=-1;w=next(G,v,w))
               if(!visited[w])
              { visited[w]=true;
                printf("%c",G.vexs[w]);
                 EnQueue(Q,G.vexs[w]);
               }
        }
        }
}
int main()
{
  MGraph G;
  CreateUDN(G);
  guangdu(G);
  printf("n");
  return 0;
}

搜索更多相关主题的帖子: include　

第 2 楼

得分:0

DeQueue(Q, G.vexs[v]); // 这一行错了，出队列的值覆盖G.vexs[v]倒是也能接受，可是后面完全没有用到这个值，出队列的意义就没有了

程序代码：

入队
while (队非空)
beg:
    出队 --> tmp
    打印 tmp
    遍历tmp的子节点，依次入队
end

还是重写吧

[fly]存在即是合理[/fly]

第 3 楼

得分:0

回复 2楼 azzbcc

这样改还是错了
#include <stdio.h>
#include <malloc.h>
#define MAX_VERTEX_NUM 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int VRType;
typedef char VertexType;
typedef char InfoType;
typedef enum {DG,DN,UDG,UDN}GraphKind;
typedef char QElemType;
int visited[MAX_VERTEX_NUM];
typedef struct ArcCell
{
    VRType adj;
    InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
    VertexType vexs[MAX_VERTEX_NUM];
    AdjMatrix arcs;
    int vexnum,arcnum;
    GraphKind kind;
}MGraph;
typedef struct QNode
{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
int LocateVex(MGraph G,VertexType v)
{
     int j=-1,k;
     for(k=0;k<G.vexnum;k++)
         if(G.vexs[k]==v)
        {
            j=k;
            break;
        }
     return j;
}
Status CreateUDN(MGraph &G)
{
    int i,j,k;
    VertexType v1,v2;
    scanf("%d%d",&G.vexnum,&G.arcnum);
    getchar();
    for(i=0;i<G.vexnum;i++)
        scanf("%c",&G.vexs[i]);
    for(i=0;i<G.vexnum;i++)
    for(j=0;j<G.vexnum;j++)
        G.arcs[i][j].adj=0;
      for (k=0;k<G.arcnum;k++)
      {
          getchar();
        scanf("%c%c",&v1,&v2);
        i=LocateVex(G,v1);j=LocateVex(G,v2);
        G.arcs[i][j].adj=1;
      }
      return OK;
}
Status first(MGraph G,int v)
{
    int j;
    for(j=0;j<G.vexnum;j++)
        if(G.arcs[v][j].adj==1)
            return j;
        return -1;
}
Status next(MGraph G,int v,int w)
{
    int j;
    for(j=w+1;j<G.vexnum;j++)
        if(G.arcs[v][j].adj==1)
            return j;
        return -1;
}
Status InitQueue(LinkQueue &Q)
{
   Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
   if(!Q.front) return ERROR;
   Q.front->next=NULL;
   return OK;
}
Status EnQueue(LinkQueue &Q,QElemType e)
{
    QueuePtr p;
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p) return ERROR;
     p->data=e;
      p->next=NULL;
       Q.rear->next=p;
       Q.rear=p;
    return OK;
}
Status DeQueue(LinkQueue &Q,QElemType &e)
{
     QueuePtr p;
  if(Q.front==Q.rear)
        return ERROR;
  p=Q.front->next;
  e=p->data;
  Q.front->next=p->next;
  if(Q.rear==p)
      Q.rear=Q.front;
  free(p);
  return OK;
}
void guangdu(MGraph G)
{
    int v,w;
    char u;
    LinkQueue Q;
    for(v=0;v<G.vexnum;v++)
        visited[v]=0;
    InitQueue(Q);
    for(v=0;v<G.vexnum;v++)
        if(!visited[v])
        {
          visited[v]=TRUE;
          printf("%c",G.vexs[v]);
          EnQueue(Q,G.vexs[v]);
        while(Q.front!=Q.rear)
        {
           DeQueue(Q,u);
           for(w=first(G,u);w!=-1;w=next(G,u,w))
               if(!visited[w])
              { visited[w]=true;
                printf("%c",G.vexs[w]);
                 EnQueue(Q,w);
               }
        }
        }
}
int main()
{
  MGraph G;
  CreateUDN(G);
  guangdu(G);
  printf("\n");
  return 0;
}

第 4 楼

得分:10

学会debug

和你上一贴的问题正好反过来了

first 和 next 按下标查找，但你队列中存储的是节点具体值

[fly]存在即是合理[/fly]

第 5 楼

得分:0

回复 4楼 azzbcc

调试好像没那么容易上次百度说什么按f5 ，还有按f10是什么单不调试

第 6 楼

得分:0

回复 4楼 azzbcc

感觉这样错了但还是不对
void guangdu(MGraph G)
{
    int v,w;
    char u;
    LinkQueue Q;
    for(v=0;v<G.vexnum;v++)
        visited[v]=0;
    InitQueue(Q);
    for(v=0;v<G.vexnum;v++)
        if(!visited[v])
        {
          visited[v]=TRUE;
          printf("%c",G.vexs[v]);
          EnQueue(Q,G.vexs[v]);
        while(Q.front!=Q.rear)
        {
           DeQueue(Q,u);
           for(w=first(G,u);w!=-1;w=next(G,u,w))
               if(!visited[w])
              { visited[w]=true;
                printf("%c",G.vexs[w]);
                 EnQueue(Q,G.vexs[w]);
               }
        }
        }
}

第 7 楼

得分:0

回复 4楼 azzbcc

#include <stdio.h>
#include <malloc.h>
#define MAX_VERTEX_NUM 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int VRType;
typedef char VertexType;
typedef char InfoType;
typedef enum {DG,DN,UDG,UDN}GraphKind;
typedef char QElemType;
int visited[MAX_VERTEX_NUM];
typedef struct ArcCell
{
    VRType adj;
    InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
    VertexType vexs[MAX_VERTEX_NUM];
    AdjMatrix arcs;
    int vexnum,arcnum;
    GraphKind kind;
}MGraph;
typedef struct QNode
{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
int LocateVex(MGraph G,VertexType v)
{
     int j=-1,k;
     for(k=0;k<G.vexnum;k++)
         if(G.vexs[k]==v)
        {
            j=k;
            break;
        }
     return j;
}
Status CreateUDN(MGraph &G)
{
    int i,j,k;
    VertexType v1,v2;
    scanf("%d%d",&G.vexnum,&G.arcnum);
    getchar();
    for(i=0;i<G.vexnum;i++)
        scanf("%c",&G.vexs[i]);
    for(i=0;i<G.vexnum;i++)
    for(j=0;j<G.vexnum;j++)
        G.arcs[i][j].adj=0;
      for (k=0;k<G.arcnum;k++)
      {
          getchar();
        scanf("%c%c",&v1,&v2);
        i=LocateVex(G,v1);j=LocateVex(G,v2);
        G.arcs[i][j].adj=1;
      }
      return OK;
}
Status first(MGraph G,int v)
{
    int j;
    for(j=0;j<G.vexnum;j++)
        if(G.arcs[v][j].adj==1)
            return j;
        return -1;
}
Status next(MGraph G,int v,int w)
{
    int j;
    for(j=w+1;j<G.vexnum;j++)
        if(G.arcs[v][j].adj==1)
            return j;
        return -1;
}
Status InitQueue(LinkQueue &Q)
{
   Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
   if(!Q.front) return ERROR;
   Q.front->next=NULL;
   return OK;
}
Status EnQueue(LinkQueue &Q,QElemType e)
{
    QueuePtr p;
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p) return ERROR;
     p->data=e;
      p->next=NULL;
       Q.rear->next=p;
       Q.rear=p;
    return OK;
}
Status DeQueue(LinkQueue &Q,QElemType &e)
{
     QueuePtr p;
  if(Q.front==Q.rear)
        return ERROR;
  p=Q.front->next;
  e=p->data;
  Q.front->next=p->next;
  if(Q.rear==p)
      Q.rear=Q.front;
  free(p);
  return OK;
}
void guangdu(MGraph G)
{
    int v,w;
    char u;
    LinkQueue Q;
    for(v=0;v<G.vexnum;v++)
        visited[v]=0;
    InitQueue(Q);
    for(v=0;v<G.vexnum;v++)
        if(!visited[v])
        {
          visited[v]=TRUE;
          printf("%c",G.vexs[v]);
          EnQueue(Q,v);
        while(Q.front!=Q.rear)
        {
           DeQueue(Q,u);
           for(w=first(G,u);w!=-1;w=next(G,u,w))
               if(!visited[w])
              { visited[w]=true;
                printf("%c",G.vexs[w]);
                 EnQueue(Q,w);
               }
        }
        }
}
int main()
{
  MGraph G;
  CreateUDN(G);
  guangdu(G);
  printf("\n");
  return 0;
}我这样改对了但是我不知道为什么我这里EnQueue(Q,v) 传的是下标过去那入队入的是下标而不是字符感觉应该要入字符才对

第 8 楼

得分:0

既然队列中控制传入字符，可以将节点值传入，出队列时再用LocateVex得到下标，然后调用first或next

[fly]存在即是合理[/fly]

第 9 楼

得分:0

回复 8楼 azzbcc

还有一个 DeQueue(Q,u) 我这里的U定义为char 要是定义为 int 就错了但是入队列的V我定义为int就没错这是为什么