呵呵,居然一篇代码解决了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; }