大连意动网站建设有限公司怎么样,什么叫做优化,南京网页设计哪家好,电脑网站 发展移动端题目描述 小K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个#xff08;也有可能没有#xff09;参考文献的链接指向别的博客文章。小K 求知欲旺盛#xff0c;如果他看了某篇文章#xff0c;那么他一定会去看这篇文章的参考文献#xff08;如果他之前已经看过这篇参考… 题目描述 小K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个也有可能没有参考文献的链接指向别的博客文章。小K 求知欲旺盛如果他看了某篇文章那么他一定会去看这篇文章的参考文献如果他之前已经看过这篇参考文献的话就不用再看它了。 假设洛谷博客里面一共有 (≤105)n(n≤105) 篇文章编号为 1 到 n以及 (≤106)m(m≤106) 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章请帮助小 K 设计一种方法使小 K 可以不重复、不遗漏的看完所有他能看到的文章。 这边是已经整理好的参考文献关系图其中文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。 请对这个图分别进行 DFS 和 BFS并输出遍历结果。如果有很多篇文章可以参阅请先看编号较小的那篇(因此你可能需要先排序)。 输入格式 共 1m1 行第 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的函数然后输出即可。需要注意的是该题目有个条件访问时需要按照从小到大的顺序所以输入两个顶点时需要对它们进行排序首先按照第一个顶点排序如果第一个顶点相等就按照第二个点排但是非常重要的一点是由于我的邻接表是采用的头插法先插入表的反而在边表的后面所以我在排序时要从大到小排。
#includestdio.h
#includestdlib.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(i1;in;i){for(ji1;jn;j)if(a[i].va[j].v) {ta[i];a[i]a[j];a[j]t;}else if(a[i].va[j].va[i].ua[j].u) {ta[i];a[i]a[j];a[j]t;}}
// for(i1;in;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);pG-A[i].firstpoint;while(p){if(!vis[p-data])dfs(G,p-data);pp-next;}
}
void bfs(struct graph *G)
{int i,j,que[MAX]{0};struct bb *p;int head1,tail1;for(i1;iG-d;i)vis[i]0;for(i1;iG-d;i){if(vis[i]0){vis[i]1;printf(%d ,G-A[i].data);que[tail]i;tail;while(tailhead){jque[head];head;pG-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;}pp-next;}}}}
}
int main()
{int i,j,vu[MAX][2];struct bb *e;struct graph G;scanf(%d %d,G.d,G.b);for(i1;iG.d;i){G.A[i].datai;G.A[i].firstpointNULL;}for(i1;iG.b;i)//存边 {scanf(%d %d,r[i].v,r[i].u);}sort(r,G.b);//for(i1;iG.b;i) printf(%d %d\n,r[i].v,r[i].u);for(j1;jG.b;j){//scanf(%d %d,v,u);e(struct bb*)malloc(sizeof(struct bb));e-datar[j].u;e-nextG.A[r[j].v].firstpoint;G.A[r[j].v].firstpointe;// e(struct bb*)malloc(sizeof(struct bb));// e-datav;// e-nextaG.A[u].firstpoint;// G.A[u].firstpointe;} for(i1;iG.d;i) if(vis[i]0) dfs(G,i);printf(\n);bfs(G);
}
