duyet do thi

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <queue>
#include <stack>
#include <fstream>
#define INP "input.INP"
using namespace std;

typedef int item;
typedef struct GRAPH
{
    char *name;
    item ** G;
    int n;
} Graph;

int *visit;
void input(Graph &Gr)
{
    ifstream inp(INP);
    if (inp == NULL)
    {
        cout<<"Khong thay file input";
        return;
    }
    inp >> Gr.n ;

    Gr.name = new char [Gr.n];
    for (int i=0; i<Gr.n; i++)
        inp >> Gr.name[i];
    Gr.G = new int *[Gr.n];

    for (int i=0; i<Gr.n; i++)
    {
        Gr.G[i] = new int [Gr.n];
        for (int j=0; j<Gr.n; j++)
            inp >> Gr.G[i][j];
    }
}

void output(Graph Gr)
{
    cout<<endl<<"Ma tran ke cua do thi"<<endl<<endl;
    for (int i=0; i<Gr.n; i++)
        cout<<setw(2)<<Gr.name[i];
    cout<<endl<<endl;
    for (int i=0; i<Gr.n; i++)
    {
        for (int j=0; j<Gr.n; j++)
            cout<<setw(2)<<Gr.G[i][j];
        cout<<endl;
    }
}

void Menu(int &select, int &begin)
{
    cout<<endl<<"Moi ban chon cach duyet do thi:"<<endl;
    cout<<"1: Duyet do thi theo chieu sau dung de quy - DFS"<<endl;
    cout<<"2: Duyet do thi theo chieu sau dung stack - DFS_stack"<<endl;
    cout<<"3: Duyet do thi theo chieu rong dung queue - BFS"<<endl;
    cout<<"4: Thoat !"<<endl;
    cin >> select;
    if (select !=4 )
    {
        cout<<"Nhap dinh bat dau duyet (tu dinh 0->12) : ";
        cin>>begin;
    }
}

void DFS (Graph Gr, int i)//Thu tuc duyet DFS, duyet theo chieu sau su dung ky thuat de quy.
{
    visit[i] = 1;
    cout<<setw(5)<<Gr.name[i];
    for (int j=0; j<Gr.n; j++)
        if (Gr.G[i][j])
            if (!visit[j])
                DFS (Gr,j);
}

void DFS_stack (Graph Gr, int i)//Thu tuc duyet DFS, duyet theo chieu sau su dung stack khu de quy.
{
    visit[i] = 1;
    stack <int> S;
    S.push(i);
    while (!S.empty())
    {
        i = S.top();
        S.pop();
        cout<<setw(5)<<Gr.name[i];
        for (int j = 0; j<Gr.n; j++)
            if (Gr.G[i][j])
                if (!visit[j])
                {
                    visit[j] = 1;
                    S.push(j);
                }
    }
}

void BFS (Graph Gr, int i)//Thu tuc duyet BFS, duyet theo chieu rong su dung queue.
{
    queue <int> Q;
    visit[i] = 1;
    Q.push(i);
    while (!Q.empty())
    {
        i = Q.front();
        Q.pop();
        cout<<setw(5)<<Gr.name[i];
        for (int j=0; j<Gr.n; j++)
            if (Gr.G[i][j])
                if (!visit[j])
                {
                    visit[j] = 1;
                    Q.push(j);
                }
    }
}


int main()
{

    Graph Gr;
    int select = 1, Begin;
    input(Gr);
    visit = new int [Gr.n];

    while (select)
    {
        system("cls");
        fill (visit, visit + Gr.n, 0);
        output(Gr);
        Menu(select, Begin);
        switch (select)
        {
            case 1:
            {
                cout<<"Duyet do thi theo chieu sau dung de quy - DFS"<<endl;
                DFS (Gr,Begin);
                cout<<endl;
                system("pause");
                break;
            }
            case 2:
            {
                cout<<"2: Duyet do thi theo chieu sau dung stack - DFS_stack"<<endl;
                DFS_stack (Gr,Begin);
                cout<<endl;
                system("pause");
                break;
            }
            case 3:
            {
                cout<<"3: Duyet do thi theo chieu rong dung queue - BFS"<<endl;
                BFS (Gr,Begin);
                cout<<endl;
                system("pause");
                break;
            }
        }
        if (select == 4) break;
    }
    system("cls");
    cout<<"***** Duyet do thi - [email protected] - CNTT&TT Thai Nguyen *****"<<endl;
    system("pause");
    return 0;
}