C语言图的建立及BFS,DFS遍历

概述C语言图的建立及BFS,DFS遍历

下面是内存溢出 jb51.cc 通过网络收集整理的代码片段。

内存溢出小编现在分享给大家，也给大家做个参考。

#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define MAX 20   //图可以存储的最大节点数为20；struct tnode{    struct tnode * next;//指向下一个临节点    int data;//存放邻节点在数组中的位置};struct node{    int valu;//存放节点的值    struct tnode * link;//指向邻节点};struct picture{    struct node nd[MAX];    //声明一个节点数组    int count;  //图中的节点数    char a; //建立的图的类型};struct picture * createpicture();int search(struct picture *p,int value);//查找value在nd数组中的位置voID bfs(struct picture * q,int i,int visit[]); //广度优先遍历voID dfs(struct picture * q,int visit[]);//深度优先遍历voID traversedfs(struct picture *p);voID traversebfs(struct picture *p);int main(){    char a;    struct picture *p;    p=createpicture();    while(1)    {        getchar();        printf("现在将对图进行遍历，若使用广度优先遍历，请输入a,若使用深度优先遍历请输入b，清屏请输入c,退出请输入d:\n");        scanf("%c",&a);        if(a=='a')        {        printf("深度优先遍历如下：\n");        traversebfs(p);        }        if(a=='b')        {        printf("广度优先遍历如下：\n");        traversedfs(p);        }        if(a=='c')        system("cls");        if(a=='d')        exit(0);    }    return 0;}struct picture * createpicture(){    int i,j,k,l;//l中存放返回的节点在数组中的位置    char a;    struct picture *p;    p=(struct picture *)malloc(sizeof(struct picture));    struct tnode * t;    printf("请输入你要建立的图中的节点数以及图的类型(a表示无向图b表示有向图):\n");    scanf("%d %c",&i,&a);    p->count=i;    p->a=a;    printf("请依次输入各节点的值(每输完一个节点的值按回车结束)：\n");    for(i=0;i<p->count;i++)    {        scanf("%d",&j);        p->nd[i].valu=j;        p->nd[i].link=NulL;    }    for(i=0;i<p->count;i++)    {        printf("输入与数据值为%d的节点相邻的节点的数据值(每输完一个节点的值按回车结束),若不再含有相邻的值请输入-1\n",p->nd[i].valu);        while(1)        {            scanf("%d",&k);            if(k==-1)                break;            l=search(p,k);            if(l!=-1)            {                t=(struct tnode *)malloc(sizeof(struct tnode));                t->data=l;                t->next=p->nd[i].link;                p->nd[i].link=t;            }            else                printf("无此数据值!\n");            //getchar();        }    }    return p;}int search(struct picture *p,int value){    int i;    for(i=0;i<p->count;i++)    {        if(value==p->nd[i].valu)        {            return i;        }    }    return -1;}voID traversedfs(struct picture *p){    int i;    int visit[MAX];//申明一个标志数组,将其初始值置为0,0表示该节点未被访问过，1表示该节点被访问过    for(i=0;i<p->count;i++)    {        visit[i]=0;    }    for(i=0;i<p->count;i++)    {        if(visit[i]==0)        {            dfs(p,i,visit);        }    }    //getchar();}voID dfs(struct picture * q,int visit[])//i表示数组的下标值visit的下标与p中的下标是一一对应的关系{    struct tnode * w;    printf("%d\n",q->nd[i].valu);    visit[i]=1;    w=q->nd[i].link;    while(w!=NulL)    {        if(visit[w->data]==0)        {            dfs(q,w->data,visit);        }        else        {            w=w->next;        }    }  }voID traversebfs(struct picture *p){    int i;    int visit[MAX];//申明一个标志数组,0表示该节点未被访问过，1表示该节点被访问过    for(i=0;i<p->count;i++)    {        visit[i]=0;    }    for(i=0;i<p->count;i++)    {        if(visit[i]==0)        {            bfs(p,visit);        }    }    //getchar();}voID bfs(struct picture * q,int visit[]){    struct tnode *w;    int a[MAX];//声明一个队列    int f,r;    int v;    f=r=0;    visit[i]=1;    printf("%d\n",q->nd[i].valu);    a[r]=i;    r++;//进行入队 *** 作    while(f!=r)    {        v=a[f];        f++;//岀队 *** 作        w=q->nd[v].link;        while(w!=NulL)        {            if(visit[w->data]==0)            {            visit[w->data]=1;            printf("%d\n",q->nd[w->data].valu);            a[r]=w->data;            r++;            }            w=w->next;        }    }}

以上是内存溢出(jb51.cc)为你收集整理的全部代码内容，希望文章能够帮你解决所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

总结

以上是内存溢出为你收集整理的C语言图的建立及BFS,DFS遍历全部内容，希望文章能够帮你解决C语言图的建立及BFS,DFS遍历所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。