P5318 【深基18.例3】查找文献

题目描述

小K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。

假设洛谷博客里面一共有 �(�≤105)n(n≤105) 篇文章（编号为 1 到 �n）以及 �(�≤106)m(m≤106) 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。

这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。

请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。

输入格式

共 �+1m+1 行，第 1 行为 2 个数，�n 和 �m，分别表示一共有 �(�≤105)n(n≤105) 篇文章（编号为 1 到 �n）以及�(�≤106)m(m≤106) 条参考文献引用关系。

接下来 �m 行，每行有两个整数 �,�X,Y 表示文章 X 有参考文献 Y。

输出格式

共 2 行。 第一行为 DFS 遍历结果，第二行为 BFS 遍历结果。

输入输出样例

输入 #1复制

8 9
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8

输出 #1复制

1 2 5 6 3 7 8 4 
1 2 3 4 5 6 7 8 

1. 该题就是一个图的遍历问题，两种遍历方法，bfs和dfs。

2.说到bfs和dfs我们就来简单的介绍一下它们。

bfs(广度优先搜索)：该算法从根节点开始遍历整个图形或树，并按照距离根节点的距离逐层遍历整个图形或树。一般使用队列来实现，首先将根节点加入队列中，然后处理队列中的所有节点，将它们相邻的节点加入队列中，以此类推，直到队列为空或者找到目标节点为止。

dfs(深度优先搜索)：该算法从图的某个顶点出发，沿着一条路尽可能深的访问图中的节点，直到该路径已经访问到不能再访问的节点为止，然后回溯到前面的节点，再尝试访问其他路径，直到图中所有的节点都被访问过。

3.该题目同样要使用邻接表，因为数据太大。建好表以后直接调用bfs和dfs的函数然后输出即可。需要注意的是，该题目有个条件，访问时需要按照从小到大的顺序，所以输入两个顶点时需要对它们进行排序，首先按照第一个顶点排序，如果第一个顶点相等就按照第二个点排，但是非常重要的一点是，由于我的邻接表是采用的头插法，先插入表的反而在边表的后面，所以我在排序时要从大到小排。

#include"stdio.h"
#include"stdlib.h"
#define MAX 100005 
struct b
{int v,u;
}r[MAX];
struct bb//边表节点 
{int data;struct bb *next;
};
typedef struct dd//顶点表 
{int data;struct bb *firstpoint;
}headlist[MAX];
struct graph
{headlist A;int d,b;
};
void sort(struct b *a,int n)
{int i,j;struct b t;for(i=1;i<=n;i++){for(j=i+1;j<=n;j++)if(a[i].v>a[j].v) {t=a[i];a[i]=a[j];a[j]=t;}else if(a[i].v==a[j].v&&a[i].u<a[j].u) {t=a[i];a[i]=a[j];a[j]=t;}}
//	for(i=1;i<=n;i++) printf("%d %d\n",a[i].v,a[i].u);
}
int vis[MAX]={0};
void dfs(struct graph *G,int i)
{struct bb *p;vis[i]=1;printf("%d ",G->A[i].data);p=G->A[i].firstpoint;while(p){if(!vis[p->data])dfs(G,p->data);p=p->next;}	
}
void bfs(struct graph *G)
{int i,j,que[MAX]={0};struct bb *p;int head=1,tail=1;for(i=1;i<=G->d;i++)vis[i]=0;for(i=1;i<=G->d;i++){if(vis[i]==0){vis[i]=1;printf("%d ",G->A[i].data);que[tail]=i;tail++;while(tail>head){j=que[head];head++;p=G->A[j].firstpoint;while(p){if(!vis[p->data]){vis[p->data]=1;printf("%d ",G->A[p->data].data);que[tail]=p->data;tail++;}p=p->next;}}}}
}
int main()
{int i,j,vu[MAX][2];struct bb *e;struct graph G;scanf("%d %d",&G.d,&G.b);for(i=1;i<=G.d;i++){G.A[i].data=i;G.A[i].firstpoint=NULL;}for(i=1;i<=G.b;i++)//存边 {scanf("%d %d",&r[i].v,&r[i].u);}sort(r,G.b);//for(i=1;i<=G.b;i++) printf("%d %d\n",r[i].v,r[i].u);for(j=1;j<=G.b;j++){//scanf("%d %d",&v,&u);e=(struct bb*)malloc(sizeof(struct bb));e->data=r[j].u;e->next=G.A[r[j].v].firstpoint;G.A[r[j].v].firstpoint=e;//	e=(struct bb*)malloc(sizeof(struct bb));//	e->data=v;//	e->next=aG.A[u].firstpoint;//	G.A[u].firstpoint=e;}	for(i=1;i<=G.d;i++) if(vis[i]==0) dfs(&G,i);printf("\n");bfs(&G);
}