《数据结构》C++代码 BFS与DFS

       BFS,广度优先搜索,一层一层去遍历图,故称广度优先。实现方式:队列。

       DFS,深度优先搜索,撞墙才回头的遍历,称为深度优先。实现方式:递归(栈)。

       这两种遍历方式,是访问图的基本方式。如果拿树做对比的话,BFS对应层次遍历,DFS则对应三种基本遍历方法(先序、中序、后序);遍历树起点只有一个根,而图则需要以每个没被遍历过的点作为起点,方能遍历完全。

       没啥可说的,直接看代码。

题目描述:输入一个图,第一行N、M表示N个点、M条边,下面M行每行输入u、v表示有一条单向边(u,v);输出图的DFS和BFS序列:

输入方式:文件"map1.in"

输出方式:屏幕

代码:

#include <iostream>
#include <cstdio>
using namespace std;

const int maxn = 10000;

int N,M,Start,End;
struct edge
{
    int v;
    edge *next;

    edge(int _v=0) { v=_v; }
}*E[maxn];
void AddEdge(int u,int v)
{
    edge *p=new edge(v);
    p->next=E[u]; E[u]=p;
}

void input()
{
    cin>>N>>M>>Start>>End;

    for(int i=1;i<=N;++i) E[i]=0;

    int u,v;
    for(int i=1;i<=M;++i)
    {
        cin>>u>>v;
        AddEdge(u,v);
    }
}

bool mark[maxn];
void DFS(int u)
{
    if(mark[u]) return;

    cout<<u<<" "; mark[u]=true;
    for(edge *p=E[u];p;p=p->next)
    {
        int v=p->v;
        DFS(v);
    }
}

class Queue
{
    int Q[maxn],i,j;
public:
    Queue() { i=j=0; }
    void clear() { i=j=0; }
    void in(int u) { Q[j++]=u; }
    int out() { return Q[i++]; }
    bool empty() { return i==j; }
    int size() { return j-i; }
};

Queue Q;
void BFS(int u)
{
    Q.clear();
    Q.in(u); mark[u]=true;
    while(!Q.empty())
    {
        u=Q.out();
        cout<<u<<" ";
        for(edge *p=E[u];p;p=p->next)
        {
            int v=p->v;
            if(mark[v]==false) { Q.in(v); mark[v]=true; }
        }
    }
}

int main()
{
    freopen("map1.in","r",stdin);

    input();

    for(int i=1;i<=N;++i) mark[i]=false;
    for(int i=1;i<=N;++i) DFS(i);
    cout<<endl;

    for(int i=1;i<=N;++i) mark[i]=false;
    for(int i=1;i<=N;++i)
        if(mark[i]==false) BFS(i);
    cout<<endl;

    fclose(stdin);
    return 0;
}
时间: 12-01

《数据结构》C++代码 BFS与DFS的相关文章

图的遍历(bfs 和dfs)

BFS的思想: 从一个图的某一个顶点V0出发,首先访问和V0相邻的且未被访问过的顶点V1.V2.……Vn,然后依次访问与V1.V2……Vn相邻且未被访问的顶点.如此继续,找到所要找的顶点或者遍历完整个图. 由此可以看出,用BFS进行搜索所搜索的顶点都是按深度进行扩展的,先找到到V0距离为1的所有顶点,然后找到距离V0为2的顶点……所以BFS所搜索到的都是最短的路径. 由于要将距离V0为d(d>0)的且未被方位的点都记录起来,我们采用队列这种数据结构.队列的特点是先进先出(FIFO),从某个顶点出

HDU 2102 A计划 (BFS或DFS)

题意:中文题. 析:是一个简单的搜索,BFS 和 DFS都可行, 主要是这个题有一个坑点,那就是如果有一层是#,另一个层是#或者*,都是过不去的,就可以直接路过, 剩下的就是一个简单的搜索,只不过是两层而已,可能一个就是在#必须传送,这个题目已经说的很清楚了. 代码如下: BFS: #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <string>

HDU 1312 Red and Black(基础bfs或者dfs)

Red and Black Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 11843    Accepted Submission(s): 7380 Problem Description There is a rectangular room, covered with square tiles. Each tile is color

15 图-图的遍历-基于邻接矩阵实现的BFS与DFS算法

算法分析和具体步骤解说直接写在代码注释上了 TvT 没时间了等下还要去洗衣服 就先不赘述了 有不明白的欢迎留言交流!(估计是没人看的了) 直接上代码: 1 #include<stdio.h> 2 #include<queue> 3 #include<iostream> 4 using namespace std; 5 typedef struct{ 6 int Vex[10];//顶点表 7 int Edge[10][10]; 8 int vexnum,arcnum;

SPFA的BFS与DFS实现及判负环问题

经过笔者的多次实践(失败),在此温馨提示:用SPFA判负环时一定要特别小心! 首先SPFA有BFS和DFS两种实现方式,两者的判负环方式也是不同的. DFS是如果找到一个节点已经在递归栈中则表示出现负环(即你层层向下搜索后又回到了起点,很明显有负环),BFS是用一个数组记录每一个节点的入队次数,如果某个节点入队次数超过n(节点数)次则表示出现负环(根据SPFA的原理,每一个点最多被扩展n次就会出结果的,如果超过了n次算法还没结束,自然是有负环).看起来是简单,但有以下注意事项: 如果只是判负环,

[Algorithms] Graph Traversal (BFS and DFS)

Graph is an important data structure and has many important applications. Moreover, grach traversal is key to many graph algorithms. There are two systematic ways to traverse a graph, breadth-first search (BFS) and depth-frist search (DFS). Before fo

ACM第一天研究懂的AC代码——BFS问题解答——习题zoj2165

代码参考网址:http://blog.csdn.net/slience_perseverance/article/details/6706354 试题分析: 本题是研究red and black的一个标题,实际上可以通过深度优先搜索的方式进行查找.前后左右的方格只要不是红色的就可以进行计数那么最后可以到达的个数会有多少呢?本人菜鸟一枚,确实解题有很大的困难,所以在参考别人的AC之后有很大的感触,这里先将代码粘贴出来后分析吧. //关于BFS问题解答//参考网址//http://blog.csdn

zoj 3811 Untrusted Patrol(bfs或dfs)

Untrusted Patrol Time Limit: 3 Seconds      Memory Limit: 65536 KB Edward is a rich man. He owns a large factory for health drink production. As a matter of course, there is a large warehouse in the factory. To ensure the safety of drinks, Edward hir

poj 1724ROADS(bfs和dfs做法)

1 /* 2 dfs比较好想,就是测试数据的问题,导致在遍历边的时候要倒着遍历才过! 3 */ 4 #include<iostream> 5 #include<cstdio> 6 #include<cstring> 7 #include<vector> 8 #include<algorithm> 9 #define Max 0x3f3f3f3f 10 using namespace std; 11 12 struct node{ 13 int D