首页 > 代码库 > 数据结构之 图论---图的深度遍历( 输出dfs的先后遍历节点 )

数据结构之 图论---图的深度遍历( 输出dfs的先后遍历节点 )

图的深度遍历

Time Limit: 1000MS Memory limit: 65536K

题目描述

请定一个无向图,顶点编号从0到n-1,用深度优先搜索(DFS),遍历并输出。遍历时,先遍历节点编号小的。

输入

输入第一行为整数n(0 < n < 100),表示数据的组数。 对于每组数据,第一行是两个整数k,m(0 < k < 100,0 < m < k*k),表示有m条边,k个顶点。 下面的m行,每行是空格隔开的两个整数u,v,表示一条连接u,v顶点的无向边。

输出

输出有n行,对应n组输出,每行为用空格隔开的k个整数,对应一组数据,表示DFS的遍历结果。

示例输入

14 40 10 20 32 3

示例输出

0 1 2 3


#include <math.h>#include <string.h>#include <stdio.h>#include <iostream>#include <string>#include <algorithm>#include <queue>using namespace std;int map[102][102];int vis[102];int n;queue<int>q;void dfs(int dd){    int j;    for(j=0; j<n; j++)    {        if(!vis[j] && map[dd][j]==1 )        {            q.push(j);            vis[j]=1;            dfs(j);        }    }}int main(){    int t;    cin>>t;    int i, j;    int m; //n个顶点,从0开始,m条边    int u, v;    while(t--)    {        cin>>n>>m;        memset(map, 0, sizeof(map));        memset(vis, 0, sizeof(vis));        for(i=0; i<m; i++)        {            cin>>u>>v;            map[u][v]=1;            map[v][u]=1;        }        for(i=0; i<n; i++)        {            if(!vis[i])            {                q.push(i);                vis[i]=1;                dfs(i);            }        }        int ff=1;        while(!q.empty())        {            int dd=q.front();            if(ff==1)            {                cout<<dd;                ff=0;            }            else              cout<<" "<<dd;            q.pop();        }        cout<<endl;    }    return 0;}

 

数据结构之 图论---图的深度遍历( 输出dfs的先后遍历节点 )