当前位置: 代码迷 >> C语言 >> 图的广度优先遍历问题,望大家指点
  详细解决方案

图的广度优先遍历问题,望大家指点

热度:161   发布时间:2008-01-04 12:46:53.0
图的广度优先遍历问题,望大家指点
运行“5---广度优先遍历”时总是出现内存引用错误,该内存不能为“written”。是否我在初始化队列时代码有错误呢?请大家指教!
(注:红色部分是与“队列”和“广度优先遍历”有关的代码)
在tc下没有内存错误,但实现不了结果。在vc++就有内存错误

#include <stdio.h>
#define MAX 10                     /* 图的最多顶点数*/
#define INF 65535                  /*定义大于所有权值的一个数*/
#define MAXLEN 10                  /*定义MAXLEN等于10*/
typedef enum {DGN,UDGN} GraphKind; /*DGN包括有向图和有向网,UDGN包括无向图和无向网*/
typedef char VertexType;           /* 图的顶点类型 */
typedef int AdjType;               /* 图的边(或弧)的类型,如果是网,则权值非负 */

typedef struct                        /*队的结构*/
{
    VertexType* Q;
    int front,rear;
}CycQue;

struct  
{    VertexType  vex;
    AdjType  lowcost;
}closeedge[MAX];


typedef struct
{    VertexType vexs[MAX+1];      /* 表示的顶点的一维向量 */
    AdjType edges[MAX+1][MAX+1];
        int n,e;                     /* n表示当前顶点数  e表示当前的边数(弧数) */
}MGraph;
              
void CreateGN(MGraph* G,GraphKind gk)                                           /*构造图*/
{    int i,j,k;
    AdjType w;

    printf("\n\t\t请输入图的顶点数和边数(格式为:顶点数,边数)\n\t\t");
    scanf("%d,%d",&(G->n),&(G->e));getchar();                     /*输入图的顶点数和边数*/
    for(i=1;i<=G->n;i++)
        for(j=1;j<=G->n;j++)
            G->edges[i][j]=INF;                /*邻接矩阵的初始化,用INF表示边或弧的不存在*/
    printf("\t\t请输入各顶点的值:\n\t\t");
    for(i=1;i<=G->n;i++)
    {    scanf("%c",&(G->vexs[i]));   getchar();    printf("\t\t"); }              /*构造顶点向量*/
    printf("请输入边信息,如果不是网,则用0或1表示边(狐)的存在与否。\n");
    printf("\t\t如果是网,则输入权值!\n");
    printf("\t\t输入格式为:端点1的序号,端点2的序号,1或权值\n\t\t");
    for(k=1;k<=G->e;k++)
    {    scanf("%d,%d,%d",&i,&j,&w);
                               
        getchar();
        printf("\t\t");
        G->edges[i][j]=w;
        if (gk==2)
            G->edges[j][i]=w;
    }                                                                        /*构造邻接矩阵*/
    printf("\n\t\t输入的各个顶点为: ");
    for(i=1;i<=G->n;i++)
        printf("%c\t",G->vexs[i]);
    printf("\n\t\t输入的邻接矩阵为: \n");
    for(i=1;i<=G->n;i++)
    {    printf("\n\t\t");
        for(j=1;j<=G->n;j++)
            printf("%d\t",G->edges[i][j]);
    }
}

            /*队列操作函数*/
void InitCycQue(CycQue* sp)                                  /*初始化队列*/
{    
    sp->Q=(VertexType *)malloc(MAXLEN*sizeof(VertexType));    
    sp->front=sp->rear=0;
    printf("\t\t\t内存分配成功\n");
}

int InsertCycQue(CycQue* sp, VertexType x)                             //入队操作
{
    sp->rear=(sp->rear+1)%MAXLEN;
    sp->Q[sp->rear]=x;
    return 1;    
}

int ExitCycQue(CycQue* sp,VertexType x)                  //出队操作
{
    sp->front=(sp->front+1)%MAXLEN;
    x=sp->Q[sp->front];
    return 1;    
}

EmptyQue(CycQue* sp)                             /*判断队列是否空*/
{
     if(sp->front==sp->rear)
    {        
    return 1;
    }
     return 0;
}

void  BFSM(MGraph* G,int i,int visited[MAX] )            /*从第i 个顶点开始的广度优先搜索遍历*/
{
    int j,k;
    VertexType x;
    CycQue* sp;
    printf("\t\t\t输入i的值:");
    scanf("%d",&i);
    printf("\n");

    InitCycQue(sp);
    printf("\t\t\tthe node is:%c\n",G->vexs[i]);
    visited[i]=1;
    InsertCycQue(sp,G->vexs[i]);
    while(!EmptyQue(sp))
    {
        k=ExitCycQue(sp,x);
        for(j=1;j<=G->n;j++)
            if(G->edges[k][j]!= INF&& (!visited[j]))
            {
                printf("the node is:%c\n",G->vexs[j]);
                visited[j]=1;
                InsertCycQue(sp,G->vexs[j]);
            }
    }
}



main()
{    MGraph G;
    GraphKind gk;
    VertexType a;
    int choice;
    int i,j=1,ch2,k;
    int visited[MAX];                 /*定义数组存储访问标志*/
    int P[MAX];                       /*记录单源点的最短路径*/
    AdjType D[MAX];                   /*记录从源点到其余各顶点的最短路径的长度*/         
       
        printf("\t\t请输入图的类型(有向还是无向)\n");
        printf("\t\t如果是有向图或有向网输入1,否则输入2\n\t\t");
        scanf("%d",&gk);getchar();        
        CreateGN(&G,gk);                     

        BFSM(&G,i,visited);                 /*广度优先搜索遍历*/
}

[[italic] 本帖最后由 诸事丁 于 2008-1-4 18:24 编辑 [/italic]]
搜索更多相关的解决方案: 遍历  内存  define  定义  队列  

----------------解决方案--------------------------------------------------------
你自己先把队列调好啊,这么长的代码不高兴看啊
----------------解决方案--------------------------------------------------------
好的,让我先列好些
----------------解决方案--------------------------------------------------------
  相关解决方案