dfs 及其 bfs 一些练习

背景题目

图的深度优先遍历序列

Time Limit(Common/Java):1000MS/3000MS          Memory Limit:65536KByte
Total Submit:811            Accepted:262

Description

图(graph)是数据结构 G=(V,E)，其中V是G中结点的有限非空集合,结点的偶对称为边(edge)；E是G中边的有限集合。设V={0,1,2,……,n-1}，图中的结点又称为顶点(vertex)，有向图(directed graph)指图中代表边的偶对是有序的，用<u，v>代表一条有向边（又称为弧），则u称为该边的始点（尾），v称为边的终点（头）。无向图(undirected graph)指图中代表边的偶对是无序的，在无向图中边(u，v )和(v，u)是同一条边。

输入边构成无向图，求以顶点0为起点的深度优先遍历序列。

Input

第一行为两个整数n、e，表示图顶点数和边数。以下e行每行两个整数，表示一条边的起点、终点，保证不重复、不失败。1≤n≤20，0≤e≤190

Output

前面n行输出无向图的邻接矩阵，最后一行输出以顶点0为起点的深度优先遍历序列，对于任一起点，首先遍历的是终点序号最小的、尚未被访问的一条边。每个序号后输出一个空格。

Sample Input

4 5
0 1
0 3
1 2
1 3
2 3

Sample Output

0 1 0 1 
1 0 1 1 
0 1 0 1 
1 1 1 0 
0 1 2 3 

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <queue>
using namespace std;
int n,e;
int mmap[25][25],vis[25];
void dfs(int x)
{
    printf("%d ",x);
    vis[x]=1;
    for(int i=0; i<n; i++)
        if(vis[i]==0 && mmap[x][i]==1)
            dfs(i);
}
/*void bfs()
{
    queue<int> q;
    q.push(0);
    vis[0]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        printf("%d ",x);
        for(int i=0; i<n; i++)
            if(vis[i]==0&&map[x][i]==1)
            {
                vis[i]=1;
                q.push(i);
            }
    }
}*/
int main()
{
    int a,b;
    while(scanf("%d%d",&n,&e)!=EOF)
    {
        memset(mmap,0,sizeof(mmap));
        for(int i=0; i<e; i++)
        {
            scanf("%d%d",&a,&b);
            mmap[b][a]=mmap[a][b]=1;
        }
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
                printf("%d ",mmap[i][j]);
            printf("\n");
        }
        memset(vis,0,sizeof(vis));
        for(int i=0; i<n; i++)
            if(vis[i]==0)
                dfs(i);
        printf("\n");
    }
    return 0;
}