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

Question

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

Answer 1

我有源码

#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;
}

Answer 2

• 建议你看下这篇博客👉 ：C语言无向图的邻接表储存以及DFS、BFS的实现