/*
 无向图(邻接矩阵)
 */
#include <iostream>
using namespace std;
const int maxsize=10;
int visited[maxsize]={0};
template<typename T>
class MGraph
{
private:
    T vertex[maxsize];
    int edge[maxsize][maxsize];
    int vertexNum,edgeNum;
public:
    MGraph(T a[],int n,int e);
    void DFtraverse(int v);
    void BFtraverse(int v);
};
template<typename T>
MGraph<T>::MGraph(T a[],int n,int e)
{
    int i,j,k;
    vertexNum=n;
    edgeNum=e;
    for(i=0;i<vertexNum;i++)
    {
        vertex[i]=a[i];
    }
    for(i=0;i<vertexNum;i++)
    {
        for(j=0;j<vertexNum;j++)
        {
            edge[i][j]=0;
        }
    }
    for(k=0;k<edgeNum;k++)
    {
        cin>>i>>j;
        edge[i][j]=1;
        edge[j][i]=1;
    }
}
template<typename T>
void MGraph<T>::DFtraverse(int v)
{
    cout<<vertex[v];
    visited[v]=1;
    for(int j=0;j<vertexNum;j++)
    {
        if(edge[v][j]==1&&visited[j]==0)
            DFtraverse(j);
    }
}
template<typename T>
void MGraph<T>::BFtraverse(int v)
{
    int w,j,Q[maxsize];
    int front=-1,rear=-1;
    cout<<vertex[v];
    visited[v]=1;
    Q[++rear]=v;
    while (rear!=front)
    {
        w=Q[++front];
        for(j=0;j<vertexNum;j++)
        {
            if(edge[w][j]==1&&visited[j]==0)
            {
                Q[++rear]=j;
                cout<<vertex[j];
                visited[j]=1;
            }
        }
    }
}
int main()
{
    char ch[]={'1','2','3','4','5','6'};
    MGraph<char> MG(ch,6,6);
    cout<<"深度优先遍历:"<<endl;
    for(int i=0;i<maxsize;i++)
    {
        visited[i]=0;
    }
    MG.DFtraverse(0);
    cout<<"广度优先遍历:"<<endl;
    for(int i=0;i<maxsize;i++)
    {
        visited[i]=0;
    }
    MG.BFtraverse(0);
}