返回顶部

收藏

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

更多
#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 i,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",&amp;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",&amp;i,&amp;a);
    p->count=i;
    p->a=a;
    printf("请依次输入各节点的值(每输完一个节点的值按回车结束):\n");
    for(i=0;i<p->count;i++)
    {
        scanf("%d",&amp;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",&amp;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 i,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,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,i,visit);
        }
    }
    //getchar();
}
void bfs(struct picture * q,int i,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;
        }
    }
}

标签:c/c++

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. yuer 发表 2018-07-27 08:46:07 coredump之百米之内必有解药
  2. hev 发表 2018-04-28 06:11:38 一个简单、轻量的 Linux 协程实现
  3. hev 发表 2017-10-19 15:56:11 FSH – 助你接入私有网络中的 Linux 终端
  4. gonwan 发表 2015-04-15 08:03:07 Database Access Layer in C++
  5. gonwan 发表 2015-12-28 08:41:13 Basic Usage of Boost MultiIndex Containers
  6. gonwan 发表 2016-01-19 03:37:54 Coroutines in C++/Boost
  7. Haoxiang Li 发表 2017-10-25 20:29:02 MXNet C++ Deployment
  8. yuer 发表 2017-10-20 07:52:47 基于leveldb的持久消息队列SDK
  9. yuer 发表 2017-10-07 07:51:32 c++11完美转发
  10. 博主 发表 2016-09-03 00:00:00 C++编译期类型信息的利用
  11. yuer 发表 2017-09-06 03:03:29 libcurl访问unix socket
  12. yuer 发表 2017-09-07 08:14:58 valgrind检测php扩展的warning

发表评论