这代码哪错了采用邻接矩阵法构造有向图，深度优先搜索输出

#2

azzbcc2015-11-26 10:20

你的代码太乱了，还有c++的引用

这是我整理后的，把参数改为指针可以节省很多内存

程序代码：

#include <stdio.h>

#define MAX_VERTEX_NUM 20
#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;

int visited[MAX_VERTEX_NUM] = { FALSE };

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, *pMGraph;

int LocateVex(pMGraph pG, VertexType v)
{
    for (int i = 0;i < pG->vexnum;i++)
        if (pG->vexs[i] == v)
        {
            return i;
        }
    printf("ERROR on find %c\n", v);
    return -1;
}

Status CreateUDN(pMGraph pG)
{
    VertexType v1, v2;

    scanf("%d%d", &pG->vexnum, &pG->arcnum);
    getchar();
    for (int i = 0;i < pG->vexnum;i++)
    {
        scanf("%c", &pG->vexs[i]);
    }
    getchar();
    for (int i = 0;i < pG->arcnum;i++)
    {
        scanf("%c%c", &v1, &v2);
        getchar();
        pG->arcs[LocateVex(pG, v1)][LocateVex(pG, v2)].adj = 1;
    }
    return OK;
}

int FirstAdjVex(pMGraph pG, VertexType v)
{
    int i = LocateVex(pG, v);
    for (int j = 0;j < pG->vexnum;j++)
    {
        if (pG->arcs[i][j].adj == 1) return j;
    }
    return ERROR;
}

int NextAdjVex(pMGraph pG, VertexType v, VRType w)
{
    int i = LocateVex(pG, v);

    for (int j = w + 1;j < pG->vexnum;j++)
    {
        if (pG->arcs[i][j].adj == 1) return j;
    }
    return ERROR;
}

void DFS(pMGraph pG, int v)
{
    visited[v] = TRUE;
    printf("%c", pG->vexs[v]);
//  for (int w = FirstAdjVex(pG, v);w;w = NextAdjVex(pG, v, w))  // 调用这两个函数时应该传节点具体值而不是下标
    for (int w = FirstAdjVex(pG, pG->vexs[v]);w;w = NextAdjVex(pG, pG->vexs[v], w))
    {
        if (!visited[w]) DFS(pG, w);
    }
}

void DFSTraverse(pMGraph pG)
{
    for (int v = 0;v < pG->vexnum;v++)
    {
        if (!visited[v]) DFS(pG, v);
    }
    printf("\n");
}

int main()
{
    MGraph G = { { 0 } };
    CreateUDN(&G);
    DFSTraverse(&G);
    return 0;
}

问题出现在DFS函数

#3

不同认为2015-11-26 12:46

明白了

#4

不同认为2015-11-26 16:01

回复 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;
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;
}

这代码哪错了 采用邻接矩阵法构造有向图，深度优先搜索输出