现在的位置: 首页 > 编程语言 > 正文

关于邻接表实现适用两种深搜(DFS)和广搜(BFS)的代码

2017年07月15日 编程语言 ⁄ 共 1761字 ⁄ 字号 评论关闭

呵呵,居然一篇代码解决了DFS和BFS两个问题。

一般的深搜广搜的节点都是单一的一个字符,这里我就不说那种了,毕竟比较简单些。

这里要讲的是节点是字符串的深广搜。

在我写好这个用邻接表实现DFS时,运行结果纠结了我,运行结果是广搜的答案。

我郁闷了,明明照着DFS的思想,怎么写成了BFS了。于是我整理了一下思绪。

结果出来了。我改了一句话,刚刚的DFS运行得出的结果就变了,答案显示完全正确。

感觉好兴奋啊,一篇代码解决了两个问题。我觉得解决两个问题的关键就在于结构体定义的 num。

 

不过时间复杂度有点高,最坏的情况下达到了O(n^3);

求大神们指点一下,怎么改进。

 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 10 //节点字符串的长度
#define Max 100  //最大节点数
typedef struct point
{
    char name[N];//节点字符串
    int num; //节点序号
    struct point *next;
} Point;

typedef struct
{
    Point p[Max];
} Graph;//图
Graph G;
int dist[Max];//标记数组
void fs(Point *q)//搜索函数
{
    Point *p=q;
    if(!dist[q->num])
    {
        printf("%s ",q->name);
        dist[q->num]=1;//已经输出过就要标记
    }
    while(p->next!=NULL)
    {
        if(dist[p->next->num]!=1)//如果下个节点没被搜过,即输出过,则搜
        {
            fs(&G.p[p->next->num]);//深搜
            //fs(p->next);//广搜
        }
        p=p->next;//继续找所邻接的下一个节点
    }
}
void continues(Point *q,Point *p1)//将*p1所代表的节点复制出来,然后邻接在*q所代表的节点的后面
{
    Point *p;
    p=(Point*)malloc(sizeof(Point));
    strcpy(p->name,p1->name);
    p->num=p1->num;
    p->next=NULL;
    while(q->next!=NULL)q=q->next;
    q->next=p;
    return ;
}
int main()
{
    int i,j,n,flag,m,k;
    char s1[N],s2[N];
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d\n",&k);//有多少个节点
        memset(dist,0,sizeof(dist));
        for(i=1; i<=k; i++)//输入表示各节点的字符串
        {
            scanf("%s",G.p[i].name);
            G.p[i].next=NULL;//顺便初始化
            G.p[i].num=i;//赋值个序号
        }
        scanf("%d",&flag);//是有向图还是无向图,有1,无0
        scanf("%d",&m);//有多少条边
        while(m--)
        {
            scanf("%s",s1);//输入边,若是有向边,则这个是起点,下面一个是终点
            scanf("%s",s2);
            if(flag==1)//若是有向图
                for(i=1; i<=k; i++)
                {
                    if(!strcmp(s1,G.p[i].name))//寻找出起点
                    {
                        for(j=1; j<=k; j++)
                        {
                            if(!strcmp(s2,G.p[j].name))//寻找出终点
                            {
                                continues(&G.p[i],&G.p[j]);break;//邻接,退出
                            }
                        }
                        break;//找到了当然要退出循环
                    }
                }
            else//若是无向图
            {
                for(i=1; i<=k; i++)
                {
                    if(!strcmp(s1,G.p[i].name))//寻出对应的节点
                    {
                        for(j=1; j<=k; j++)
                        {
                            if(!strcmp(s2,G.p[j].name))//寻出对应的节点
                            {
                                continues(&G.p[i],&G.p[j]);//互相邻接
                                continues(&G.p[j],&G.p[i]);
                                break;//退出
                            }
                        }
                        break;//当然要退出
                    }
                }
            }

        }
        for(i=1; i<=k; i++)//开始一个一个的给我搜
            fs(&G.p[i]);
        printf("\n");
    }
    return 0;
}

 

抱歉!评论已关闭.