亲，您未登录哦！ 登录 | 注册
首页  |  社区  |  工具箱  |  代码库  |  博客  |  招聘  |  文章  |  新闻  |  下载  |  读书
回 帖 发 新 帖 刷新版面

主题：[讨论]求教 关于图的遍历

lixuantea [专家分：0] 发布于 2006-04-20 22:12:00

程序是用VC＋＋编的，只能执行n-1个节点，到第n个节点时就出错，其中构造邻接多重表的部分如下
void CreateGraph(int n,amlgraph &G)//构造邻接多重表
{
    pebox p1,p2;
    int i,j,k,m;
    int mark;
    initgraph(G,n);
    printf("请输入边的数量:");
    scanf("%d",&m);
    for(k=0;k<m;k++)
    {
        printf("请输入第%d条边的两个顶点:",k+1);
        scanf("%d%d",&i,&j);
        p1=(pebox)malloc(sizeof(ebox));
        p1->ivex=i;
        p1->jvex=j;
        p1->ilink=NULL;
        p1->jlink=NULL;
        p2=G.adjmulist[i].firstedge;
        if(p2==NULL)
            G.adjmulist[i].firstedge=p1;
        else
        {
            mark=0;
            while(mark==0)
            {
                if(p2->ivex==i && p2->ilink==NULL) mark=1;
        else if(p2->jvex==i && p2->jlink==NULL) mark=2;
                else if(p2->ivex==i) p2=p2->ilink;
                else p2=p2->jlink;
            }
            if(mark==1) p2->ilink=p1;
            else p2->jlink=p1;
        }
        p2=G.adjmulist[j].firstedge;
        if(p2==NULL)
            G.adjmulist[j].firstedge=p1;
        else
        {
            mark=0;
            while(mark==0)
            {
                [color=FF0000]if(p2->ivex==j && p2->ilink==NULL) mark=1;[/color]                else if(p2->jvex==j && p2->jlink==NULL) mark=2;
                else if(p2->ivex==j) p2=p2->ilink;
                else p2=p2->jlink;
            }
            if(mark==1) p2->ilink=p1;
            else p2->jlink=p1;
        }
    }
}
只要输入最后一个节点就出错，调试显示是if(p2->ivex==i && p2->ilink==NULL) mark=1这句出错，哪位高人指点一二
本帖地址：  http://bbs.pfan.cn/post/159376.html

回复列表 （共17个回复）

沙发

lixuantea [专家分：0] 发布于 2006-04-21 20:38:00

没有人指点吗，我很急啊

板凳

康伟 [专家分：0] 发布于 2006-05-06 17:08:00

你把全部程序写出来看看看

3 楼

lt19870917 [专家分：750] 发布于 2006-05-07 14:43:00

#include "stdio.h"
#include "stdlib.h"
#include "iostream.h"
#define max 0
#define max_vertex_num 20
typedef int VRtype;
typedef enum{DG,DN,UDG,UDN} GraphKind;
typedef struct ArcCell{
    VRtype adj;//VRtype 是顶点关系类型.对无权图,用0或1表示相邻否;对带权图,则为权值类型
}ArcCell,AdjMatrix[max_vertex_num][max_vertex_num];//邻接矩阵

struct VertexType{
    char name;
    int data;
};

typedef struct{
    VertexType vexs[max_vertex_num];//顶点向量
    AdjMatrix arcs;
    int vexnum,arcnum;//图的当前顶点数和弧数
    GraphKind kind;
}MGraph;

//先对无权有向图进行操作
void CreateGraph(MGraph &g)
{
    int i,j,k;
    VertexType m,n;//两个顶点确定一条弧
    printf("顶点数和弧数:");
    scanf("%d,%d",&g.vexnum,&g.arcnum);
    printf("顶点:");
    for(i=0;i<g.vexnum;i++)
        cin>>g.vexs[i].name;
    for(;i<max_vertex_num;i++){
        g.vexs[i].name=NULL;
        g.vexs[i].data=NULL;
    }
    for(i=0;i<max_vertex_num;i++){
        for(j=0;j<max_vertex_num;j++)
            g.arcs[i][j].adj=0;
    }
    printf("弧:");
    for(i=0;i<g.arcnum;i++){
        cin>>m.name;
        cin>>n.name;
        for(j=0;j<g.vexnum;j++){
            if(m.name==g.vexs[j].name)
                break;
        }
        if(j==g.vexnum){
            printf("输入的弧尾不在顶点范围内,请重新输入\n");
            i--;
            continue;
        }
        for(k=0;k<g.vexnum;k++){
            if(n.name==g.vexs[k].name)
                break;
        }
        if(k==g.vexnum){
            printf("输入的弧头不在顶点范围内,请重新输入\n");
            i--;
            continue;
        }
        g.arcs[j][k].adj=1;
    }
    printf("图建立完毕\n");
}


int LocateVex(MGraph g,VertexType v)//返回顶点在数组中的位置
{
    int i;
    for(i=0;i<g.vexnum;i++){
        if(v.name==g.vexs[i].name)
            break;
    }
    if(i==g.vexnum)
        return(-1);//不存在
    return(i);
}


int GetVex(MGraph g,VertexType v)//返回顶点数据
{
    return(g.vexs[LocateVex(g,v)].data);
}


void PutVex(MGraph &g,VertexType v,int value)//对顶点赋值
{
    g.vexs[LocateVex(g,v)].data=value;
}

void InsertVex(MGraph &g,VertexType v)//插入顶点
{
    g.vexs[g.vexnum]=v;
    g.vexnum++;
}


void DeleteVex(MGraph &g,VertexType v)//删除顶点
{
    int i;
    for(i=0;i<g.vexnum;i++){
        if(g.arcs[LocateVex(g,v)][i].adj!=0){
            g.arcs[LocateVex(g,v)][i].adj=0;
            g.arcnum--;
        }
        if(g.arcs[i][LocateVex(g,v)].adj!=0){
            g.arcs[i][LocateVex(g,v)].adj=0;
            g.arcnum--;
        }
    }
    g.vexnum--;
    g.vexs[LocateVex(g,v)].name=NULL;
    g.vexs[LocateVex(g,v)].data=NULL;
}


4 楼

lt19870917 [专家分：750] 发布于 2006-05-07 14:43:00


//重写print
void print(MGraph g)//打印图的邻接矩阵(列为弧尾,行为弧头)
{
    int i,j,count=0,temp[max_vertex_num];
    printf("图的邻接矩阵为:\n");
    printf("        ");
    for(i=0;i<max_vertex_num;i++){
        if(g.vexs[i].name!=NULL){
            printf("%c  ",g.vexs[i].name);
            temp[count]=i;
            count++;
        }
    }
    printf("\n");
    for(i=0;i<count;i++){
        printf("       ");
        printf("%c",g.vexs[temp[i]].name);
        for(j=0;j<count;j++)
            printf("%d  ",g.arcs[temp[i]][temp[j]].adj);
        printf("\n");
    }
    printf("顶点的值为:\n");
    for(i=0;i<count;i++)
        printf("%c:%d  ",g.vexs[temp[i]].name,g.vexs[temp[i]].data);
}
    








//返回第一个邻接顶点
int FirstAdjVex(MGraph g,VertexType v)
{
    int spot,i=0;
    spot=LocateVex(g,v);
    for(i=0;i<g.vexnum;i++){
        if(g.arcs[spot][i].adj==1)
            return(i);
    }
    return(-1);//没有邻接顶点
}



int NextAdjVex(MGraph g,VertexType v,VertexType w)
{
    int spot1,spot2,i;
    spot1=LocateVex(g,v);
    spot2=LocateVex(g,w);
    for(i=spot2+1;i<g.vexnum;i++){
        if(g.arcs[spot1][i].adj==1)
            return(i);
    }
    return(-1);//没有
}

void InsertArc(MGraph &g,VertexType v,VertexType w)
{
    int spot1,spot2;
    spot1=LocateVex(g,v);
    spot2=LocateVex(g,w);
    if(spot1!=-1&&spot2!=-1)
        g.arcs[spot1][spot2].adj=1;
}


void DeleteArc(MGraph &g,VertexType v,VertexType w)
{
    int spot1,spot2;
    spot1=LocateVex(g,v);
    spot2=LocateVex(g,w);
    if(spot1!=-1&&spot2!=-1)
        g.arcs[spot1][spot2].adj=0;
}


//访问函数
void f(VertexType v)
{
    printf("%c  ",v.name);
}



//
void DFS(MGraph g,VertexType v,bool visit[])//同时可以得到连通分量
{
    int spot,stack[max_vertex_num],top=-1;
    spot=LocateVex(g,v);
    do{
        if(!visit[spot]){
            f(g.vexs[spot]);
            visit[spot]=true;
            top++;
            stack[top]=spot;
        }
        for(spot=FirstAdjVex(g,v);spot>=0;spot=NextAdjVex(g,v,g.vexs[spot])){
            if(!visit[spot])
                break;
        }
        if(spot>=0){
            v=g.vexs[spot];
            continue;
        }
        else{
            top--;
            if(top!=-1)
                spot=stack[top];
        }
    }while(top!=-1);
}






//深度优先搜索
void DFSTraverse(MGraph g)
{
    bool visit[max_vertex_num];
    int i;
    for(i=0;i<max_vertex_num;i++)
        visit[i]=false;
    for(i=0;i<g.vexnum;i++){
        if(!visit[i]) DFS(g,g.vexs[i],visit);
    }
}



//可一得到连通分量
void BFS(MGraph g,VertexType v,bool visit[])
{
      int spot,front=-1,rear=-1,queue[max_vertex_num];
      spot=LocateVex(g,v);
      f(v);
      visit[spot]=true;
      do{
          for(spot=FirstAdjVex(g,v);spot>=0;spot=NextAdjVex(g,v,g.vexs[spot])){
              if(!visit[spot]){
                  f(g.vexs[spot]);
                  visit[spot]=true;
                  rear=(rear+1)%max_vertex_num;
                  queue[rear]=spot;
              }
          }
          front=(front+1)%max_vertex_num;
          spot=queue[front];
      }while(rear==front);
}


//广度优先搜索
void BFSTraverse(MGraph g)
{
    int i;
    bool visit[max_vertex_num];
    for(i=0;i<max_vertex_num;i++)
        visit[i]=false;
    for(i=0;i<g.vexnum;i++){
        if(!visit[i]) BFS(g,g.vexs[i],visit);
    }
}


void main()
{
    MGraph T;
    int i;
    CreateGraph(T);
    printf("\n**对顶点赋值**\n");
    for(i=0;i<T.vexnum;i++)
        PutVex(T,T.vexs[i],i);
    print(T);
    printf("\n**深度优先搜索**\n");
    DFSTraverse(T);
    printf("\n广度优先搜索**\n");
    BFSTraverse(T);
}









        
        







    




    

5 楼

lt19870917 [专家分：750] 发布于 2006-05-07 14:44:00

以上是用数组表示图的抽象数据类型,以通过运行

6 楼

康伟 [专家分：0] 发布于 2006-05-07 20:35:00

用邻接多重表做的那个呢？？

7 楼

lt19870917 [专家分：750] 发布于 2006-05-08 22:05:00

还在写中

8 楼

lt19870917 [专家分：750] 发布于 2006-05-09 12:49:00

//访问函数
void f(VertexType v)
{
    printf("%c  ",v.name);
}



//
void DFS(MGraph g,VertexType v,bool visit[])//同时可以得到连通分量
{
    int spot,stack[max_vertex_num],top=-1;
    spot=LocateVex(g,v);
    do{
        if(!visit[spot]){
            f(g.vexs[spot]);
            visit[spot]=true;
            top++;
            stack[top]=spot;
        }
        for(spot=FirstAdjVex(g,v);spot>=0;spot=NextAdjVex(g,v,g.vexs[spot])){
            if(!visit[spot])
                break;
        }
        if(spot>=0){
            v=g.vexs[spot];
            continue;
        }
        else{
            top--;
            if(top!=-1)
                spot=stack[top];
        }
    }while(top!=-1);
}






//深度优先搜索
void DFSTraverse(MGraph g)
{
    bool visit[max_vertex_num];
    int i;
    for(i=0;i<max_vertex_num;i++)
        visit[i]=false;
    for(i=0;i<g.vexnum;i++){
        if(!visit[i]) DFS(g,g.vexs[i],visit);
    }
}



//可一得到连通分量
void BFS(MGraph g,VertexType v,bool visit[])
{
      int spot,front=-1,rear=-1,queue[max_vertex_num];
      spot=LocateVex(g,v);
      f(v);
      visit[spot]=true;
      do{
          for(spot=FirstAdjVex(g,v);spot>=0;spot=NextAdjVex(g,v,g.vexs[spot])){
              if(!visit[spot]){
                  f(g.vexs[spot]);
                  visit[spot]=true;
                  rear=(rear+1)%max_vertex_num;
                  queue[rear]=spot;
              }
          }
          front=(front+1)%max_vertex_num;
          spot=queue[front];
      }while(rear==front);
}


//广度优先搜索
void BFSTraverse(MGraph g)
{
    int i;
    bool visit[max_vertex_num];
    for(i=0;i<max_vertex_num;i++)
        visit[i]=false;
    for(i=0;i<g.vexnum;i++){
        if(!visit[i]) BFS(g,g.vexs[i],visit);
    }
}

用到ADT,只要把FirstAdjVex,NextAdjVex,按邻接多重表写就行了

9 楼

lt19870917 [专家分：750] 发布于 2006-05-09 12:52:00

#include "stdio.h"
#include "stdlib.h"
#include "iostream.h"
#define max_vertex_num 20
typedef int InfoType;
typedef char VertexType;
typedef enum{DG,DN,UDG,UDN} GraphKind;
struct ArcNode{
    int adjvex;//弧头的位置
    InfoType *info;//弧的权
    ArcNode *nextarc;
};

typedef struct VexNode{
    VertexType data;//顶点信息
    ArcNode *firstarc;//指向第一条以该顶点为弧尾的弧的指针
}VexNode,Adjlist[max_vertex_num];

typedef struct{
    Adjlist vertices;//顶点集合
    int vexnum,arcnum;
    int kind;
}ALGraph;


//对有权有向图进行操作(完全按照c语言编程)
void CreateGraph(ALGraph *g)
{
    int i,j,spot1,spot2,w;
    VertexType m,n;
    ArcNode *arc,*temp;
    printf("顶点数和弧数:");
    scanf("%d,%d",&(g->vexnum),&(g->arcnum));
    printf("顶点为:");
    for(i=0;i<g->vexnum;i++){
        cin>>g->vertices[i].data;
        g->vertices[i].firstarc=NULL;//初始化
    }
    for(;i<max_vertex_num;i++){
        g->vertices[i].data=NULL;
        g->vertices[i].firstarc=NULL;
    }
    printf("弧:");
    for(i=0;i<g->arcnum;i++){
        cin>>m;//弧尾
        cin>>n;//弧头
        cin>>w;//弧权
        for(j=0;j<g->vexnum;j++){
            if(g->vertices[j].data==m){
                spot1=j;
                break;
            }
        }
        for(j=0;j<g->vexnum;j++){
            if(g->vertices[j].data==n){
                spot2=j;
                break;
            }
        }
        arc=(ArcNode *)malloc(sizeof(ArcNode));
        arc->adjvex=spot2;
        arc->info=(int *)malloc(sizeof(int));
        *(arc->info)=w;
        arc->nextarc=NULL;
        if(g->vertices[spot1].firstarc==NULL){//建立没有头结点的链表要小心NULL
            g->vertices[spot1].firstarc=arc;
            continue;
        }
        temp=g->vertices[spot1].firstarc;
        while(temp->nextarc!=NULL)
            temp=temp->nextarc;
        temp->nextarc=arc;
        }
}

10 楼

lt19870917 [专家分：750] 发布于 2006-05-09 12:52:00

//返回顶点的位置
int LocateVex(ALGraph g,VexNode v)
{
    int i;
    for(i=0;i<max_vertex_num;i++){
        if(g.vertices[i].data==v.data)
            return(i);
    }
    return(-1);//没有
}


//
int FirstAdjVex(ALGraph g,VexNode v)
{
    int spot;
    spot=LocateVex(g,v);
    if(g.vertices[spot].firstarc!=NULL)
        return(g.vertices[spot].firstarc->adjvex);
    return(-1);//没有
}


//
int NextAdjVex(ALGraph g,VexNode v,VexNode w)
{
    int spot;
    ArcNode *arc;
    spot=LocateVex(g,v);
    arc=g.vertices[spot].firstarc;
    while(arc!=NULL&&arc->adjvex!=LocateVex(g,w))
        arc=arc->nextarc;
    if(arc!=NULL&&arc->nextarc!=NULL)
        return(arc->nextarc->adjvex);
    return(-1);//没有
}


void DeleteVex(ALGraph *g,VexNode v)
{
    int spot,i;
    ArcNode *arc,*temp;
    spot=LocateVex(*g,v);
    g->vertices[spot].data=NULL;
    g->vertices[spot].firstarc=NULL;
    for(i=0;i<max_vertex_num;i++){
        arc=g->vertices[i].firstarc;
        if(arc==NULL) continue;
        if(arc->adjvex==spot)
            arc=NULL;
        else{
            temp=arc->nextarc;
            while(temp!=NULL&&temp->adjvex==spot){
                temp=temp->nextarc;
                arc=arc->nextarc;
            }
            if(temp!=NULL){
                arc->nextarc=temp->nextarc;
                free(temp);
                continue;
            }
        }
    }
}



//
void InsertArc(ALGraph *g,VexNode v,VexNode w)
{
    int spot1,spot2;
    ArcNode *arc,*temp;
    spot1=LocateVex(*g,v);
    spot2=LocateVex(*g,w);
    if(spot1!=-1&&spot2!=-1){
        arc=g->vertices[spot1].firstarc;
        if(arc->adjvex==spot2)
            arc=NULL;
        else{
            temp=arc->nextarc;
            while(temp->adjvex==spot2){
                arc=arc->nextarc;
                temp=temp->nextarc;
            }
            arc->nextarc=temp->nextarc;
            free(temp);
        }
    }
}



//
void DeleteArc(ALGraph *g,VexNode v,VexNode w,int value)
{
    int spot1,spot2;
    ArcNode *arc,*temp;
    spot1=LocateVex(*g,v);
    spot2=LocateVex(*g,w);
    if(spot1!=-1&&spot2!=-1){
        arc=g->vertices[spot1].firstarc;
        while(arc==NULL)
            arc=arc->nextarc;
        temp=(ArcNode *)malloc(sizeof(ArcNode));
        temp->adjvex=spot2;
        temp->nextarc=NULL;
        temp->info=(int *)malloc(sizeof(int));
        *(temp->info)=value;
        arc=temp;
    }
}


//print函数
void print(ALGraph g)
{
    int i;
    ArcNode *arc;
    for(i=0;i<max_vertex_num;i++){
        if(g.vertices[i].data!=NULL){
            printf("顶点为:%c  ",g.vertices[i].data);
            printf("邻接点为:");
            arc=g.vertices[i].firstarc;
            while(arc!=NULL){
                printf("%c  ",g.vertices[arc->adjvex].data);
                arc=arc->nextarc;
            }
        printf("\n");
        }
    }
}

我来回复

您尚未登录，请登录后再回复。点此登录或注册

程序员工具箱 new

  • 更多工具

    • 代码片段

  • 模拟键盘（不可按）
  • 碰撞的唐三
  • 精彩奥运热点赛事的实时采集
  • 获取天气动态信息
  • 文件查找
  • python大数据抓取京东电脑销量数据
  • 爬虫技术不仅仅支持数据采集
  • 抓取脉脉APP上的职业信息
  • 爬虫中多线程的运用
  • 四则运算以及一元二次方程
  • 欢迎来共享你的NB代码

    • 本版新帖

  • 分析---外星人计算PI的程序
  • 八王后图形输出
  • 24点中的不可能组合
  • 《冰原探险》
  • 《丘比特的烦恼》
  • 《快乐的蜜月》
  • 《丘比特的烦恼》2
  • 《折线》
  • 《积木搭建问题》
  • 最短路径算法及应用
  • 递归算法及其应用
  • 程序设计中的数学方法
  • 黑洞数的验证
  • 上楼梯算法的java实现
  • 关于算法的学习建议