DFS&BFS.cpp

#include <iostream>
#include <fstream>
using namespace std;
ofstream fout ("Graph.out");
int a[101][101], n, s[50];
struct Graph
{
    int n,e;
    int a[101][101];
};
Graph g;
void ReadingGraph(Graph&g)
{
             int x, y;
             cout<<"numbers of nodes=";cin>>g.n;
             cout<<"numbers of edges=";cin>>g.e;
             for(int i=1;i<=g.e;i++)
        {
             cout<<"the nodes adjacent to the edge "<<i<<"are: ";
             cin>>x>>y;
             g.a[x][y]=g.a[y][x]=1;
        }
}
void DFS(int node)
{
    int i, k, p, stack[30], next[30];
    for(i=1; i<=g.n; i++)
        next[i]=0;
    p=1; //the first item
    stack[1]=node;
    fout<<node<<" ";
    s[node]=1;
    while(p>=1)//as long as the stack is not empty
    {
        i=stack[p];//access the element from the top of the stack
        for(k=next[i]+1; (k<=g.n) && (!g.a[i][k] || (g.a[i][k] && s[k])); k++)
            next[i]=k;
        if(k<=g.n)
        {
            fout<<k<<" ";
            s[k]=1;
            stack[++p]=k;
        }
        else p--;
    }
}
void BFS(int node)
{
    int q[50], first, last, v, j;
    first=last=1;
    q[1]=node;
    fout<<node<<" ";
    s[node]=1;
    while(first<=last)
    {
        v=q[first];
        first++;
        for(j=1; j<=g.n; j++)
            if((g.a[v][j]) && (!s[j]))
            {
                q[++last]=j;
                fout<<j<<" ";
                s[j]=1;
            }
    }
}
void init()
{
    for(int i=1; i<=n; i++)
        s[i]=0;
}
int main()
{
    int k;
    ReadingGraph(g);
    cout<<"First node:";
    cin>>k;
    fout<<"DFS:";
    DFS(k);
    fout<<endl;
    init();
    fout<<"BFS:";
    BFS(k);
    fout<<endl;
    return 0;
}