class vnode
{
public:
    string nodename;
    bool visted;//进行图的遍历时用于标记图是否被访问过
    node *next;
    vnode()
    {
        visted = false;
        next = NULL;
    }
};

class node
{
public:
    string nodename;
    int nodeindex;//节点的索引，用于快速定位节点在顶点数组中的位置
    int weight;//权值，用于存储顶点之间的信息
    node *next;
    node() { next = NULL; }
};

class Graph
{
public:
    Graph();                
    ~Graph();
    bool DeepFirstSearch(int nodeindex);
    void ClearVisited();
    bool WideFirstSearch(int nodeindex);protected:
    vnode *pvnode;
    int vnumber;
};

Graph::Graph()
{
    cout << "请输入节点的个数:";
    cin >> vnumber;
    pvnode = new vnode[vnumber];        //通过new创建顶点数组
    for (int i = 0; i < vnumber; i++)   //通过for循环将图的信息输入
    {
        cout << endl;
        cout << "请输入节点:";
        cin >> pvnode[i].nodename;
        string check;                   //输入某个顶点的邻接点时，以"#"作为输入的结束标志
        while (1)
        {
            cout << "请输入节点的相邻节点:";
            cin >> check;
            if (check == "#") { break; }//如果输入的"#"就跳出输入循环
            node *temp = new node;      //如果不是，就分配节点内存，完善相关信息
            temp->nodename = check;
            cout << "请输入相邻节点的序号和权值:";
            cin >> temp->nodeindex >> temp->weight;
            temp->next = pvnode[i].next;  //并将新输入的节点放到相应的链表中
            pvnode[i].next = temp;
        }
    }
}
Graph::~Graph()                         //释放内存时，先释放链表占用的内存，然后释放数组占用的内存
{
    node*currentnode = NULL;             //释放链表占用的内存
    node*temp = NULL;
    for (int i = 0; i < vnumber; i++)
    {
        currentnode = pvnode[i].next;
        while (currentnode != NULL)
        {
            temp = currentnode->next;    //保存当前节点的下一个节点的内存
            delete currentnode;          //释放当前节点的内存
            currentnode = temp;          //下一个节点作为当前的节点
        }
    }
    delete[]pvnode;                      //释放数组占用的内存
}

bool Graph::DeepFirstSearch(int nodeindex)
{
    if (nodeindex < 0 || nodeindex >= vnumber)            //判断指定的起始节点是否合法
    {
        cout << "The nodeindex does not exist..";
        return false;
    }
    if (pvnode[nodeindex].visted == false)                //判断当前节点是否被访问过，如果没有，则继续
    {
        cout << pvnode[nodeindex].nodename << " ";        //输出节点的名字
        pvnode[nodeindex].visted = true;                  //修改访问记录
        node *currentnode=pvnode[nodeindex].next;         //找到当前节点相邻的一个节点
        while (currentnode != NULL)
        {
            DeepFirstSearch(currentnode->nodeindex);      //通过递归继续上述操作
            currentnode = currentnode->next;              //换当前节点的另一个相邻节点试试
        }
    }
    return true;
}

bool Graph::WideFirstSearch(int nodeindex)
{
    if (nodeindex < 0 || nodeindex >= vnumber)          //判断输入的节点索引是否合法
    {
        cout << "The nodeindex does not exist..";
        return false;
    }
    Queue<int> queue(vnumber);
    cout << "广度优先搜索的遍历结果为:";
    cout << pvnode[nodeindex].nodename << " ";          //将起始节点的名字打印出来
    pvnode[nodeindex].visted = true;                    //更改起始节点的访问记录
    queue.EnQueue(nodeindex);                           //起始节点入队列
    int temp=0;                    
    node *currentnode = NULL;
    while (queue.QueueEmpty() == false)                 //对于每一个入队的节点，
    {
        queue.DeQueue(temp);
        currentnode = pvnode[temp].next;                //按入队顺序访问其相邻的全部节点
        while (currentnode!= NULL)
        {
            if (pvnode[currentnode->nodeindex].visted == false)
            {
                cout << currentnode->nodename << " ";
                pvnode[currentnode->nodeindex].visted = true;     //已经访问过的节点更改访问记录并入队
                queue.EnQueue(currentnode->nodeindex);            
            }
            currentnode = currentnode->next;
        }
    }
    cout << endl;
    return true;
}

void Graph::ClearVisited()
{
    for (int i = 0; i < vnumber; i++)
    {
        pvnode[i].visted = false;
    }
}