m0_67603793 2022-11-22 20:00 采纳率: 50%
浏览 23
已结题

用C语言实现:邻接表创建无向图,并且用DFS和BFS方式遍历输出该图结构

用C语言实现:邻接表创建无向图,并且用DFS和BFS方式遍历输出该图结构,需源码。

  • 写回答

2条回答 默认 最新

  • 语言-逆行者 2022-11-22 21:47
    关注

    我有源码

    #include<stdio.h>
    #include<stdlib.h>
    #define MaxWeight 1000//如果二维数组的某数据为1000,则输出符号∞
    #define MaxVert  100   //邻接表最大顶点个数
    typedef char DataType;
    
    //2.1.1邻接表结构体类型
    typedef struct ArcNode            
    {
        DataType adjvex;        //邻接边的顶点值 
        int weight;             //权值
        struct ArcNode *nextarc;  // 单链表的下一个顶点指针   
    } ArcNode;
    //2.1.2顶点表的结构体
    typedef struct Vnode           
    {
        DataType data;                //顶点元素             
        ArcNode *firstarc;       //邻接边的头指针           
    } VNode;
    //2.1.3顶点数组表的结构体
    typedef struct
    {
        VNode vertices[MaxVert];          //邻接表指针代替一维数组  
        int vexnum,arcnum;       //图的当前顶点数和边数             
    } ALGraph; 
    //判断邻接表顶点是否存在,并找到在数组中的下标位置
    int FindV(ALGraph *G,DataType V)
    {
        int i;
        for(i=0;i<G->vexnum;i++)
        {
            if(V==G->vertices[i].data)
                return i;
        }
        printf("该顶点不存在!");
        return -1;
    }
    //邻接表初始化
    void InitiateBiao(ALGraph *g)
    {
        int i;
        g->arcnum=0;
        g->vexnum=0;
        for(i=0;i<MaxVert;i++)
        {
            g->vertices[i].firstarc=NULL;//置邻接边单链表头指针为空
        }
    }
    //2.2创建有n个顶点序号和m条边的无向图,用邻接表来储存
    void CreateMGraphBiao(ALGraph *g,int n,int m)
    {
        int i,j,k,value;
        DataType v1,v2;
        ArcNode *p1=NULL,*p2=NULL;
        g->arcnum=m;
        g->vexnum=n;
        //顶点数表据域填值初始化顶点表指针域
        for(i=0;i<n;i++)
        {
            printf("输入顶点%d元素:",i+1);
            getchar();
            scanf_s("%c",&(g->vertices[i].data));//填数据
            g->vertices[i].firstarc=NULL;        //顶点结构体指针域为空
        }
        printf("\n");
        //输入边的信息构造邻接表
        printf("请输入边的信息(两顶点和权值):(空格隔开)\n");
        for(i=0;i<g->arcnum;i++)
        {//输入边的信息,并确定v1,v2在G中的位置,即顶点在vertices指针所指向的一维下标
            printf("请输入第%d条边信息:",i+1);
            getchar();
            scanf("%c %c %d",&v1,&v2,&value);
            j=FindV(g,v1);
            k=FindV(g,v2);
            if(j==-1&&k==-1)
            {
              printf("该顶点不存在!");
              return ;
            }
            p1=(ArcNode*)malloc(sizeof(ArcNode));
            p1->adjvex=g->vertices[k].data;//寻找下标k对应的值赋值给结点ANode中的adjvex
            p1->weight=value;
            p1->nextarc=g->vertices[j].firstarc;//改链,头插法
            g->vertices[j].firstarc=p1;
            /*
            对称插点
            */
            p2=(ArcNode*)malloc(sizeof(ArcNode));
            p2->adjvex=g->vertices[j].data;//寻找下标j对应的值赋值给结点ANode中的adjvex
            p2->weight=value;
            p2->nextarc=g->vertices[k].firstarc;//改链,头插法
            g->vertices[k].firstarc=p2;
        }
    }
    //2.3输出邻接表
    void OutputBiao(ALGraph *G)
    //输出邻接表G
    {   printf("\n");
        printf("        无向图的邻接表如下:\n");
        int i;
        ArcNode *p;
        for (i=0; i<G->vexnum; i++)
        {
            printf("\n  vertices[%d]%c:",i,G->vertices[i].data);
            p=G->vertices[i].firstarc;
            while (p!=NULL)
            {
                printf("-->%c权值[%d]",p->adjvex,p->weight);
                p=p->nextarc;
            }
            printf("\n");
        }
    }
    //4.0
    void Visit(DataType item)
    {
    printf("%c-->",item);
    }
    //5.2邻接表:图的广度优先遍历
    int main()
    {   
        int n,m,e,sz;
        char vi,vj;
        ALGraph g;
        int N,M;
        printf("|        图的储存方式     |\n");
        printf("|       1、邻接表         |\n");
        printf("输入顶点数和边数:(空格隔开)");
        getchar();//吃掉回车符
        scanf_s("%d%d",&N,&M);
        InitiateBiao(&g);
        CreateMGraphBiao(&g,N,M);
        OutputBiao(&g);
        
    return 0;
    }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 11月30日
  • 已采纳回答 11月22日
  • 修改了问题 11月22日
  • 创建了问题 11月22日

悬赏问题

  • ¥100 基于delphi10.2几个功能的程序demo
  • ¥15 TinyMCE如何去掉自动弹出的“链接…”工具?
  • ¥15 微信支付转账凭证,如何解决
  • ¥15 在win10下使用指纹登录时,界面上的文字最后一个字产生换行现象
  • ¥20 使用AT89C51微控制器和MAX7219驱动器来实现0到99秒的秒表计数,有开始和暂停以及复位功能,下面有仿真图,请根据仿真图来设计c语言程序
  • ¥15 51单片机 双路ad同步采样
  • ¥15 使用xdocreport 生成word
  • ¥15 请教怎么用MATLAB求坐标
  • ¥15 gradle整合es,在创建索引时报错
  • ¥15 关于模型训练的一个问题