#include <iostream>

#include <vector>

#include <set>

#include <algorithm>

using namespace std;  

// define vertex in graph

typedef struct Vertex {

    int id;

    vector<int> neighbors;

    Vertex() {

    	id = -1;

	}

    Vertex(int nid){

    	id = nid;

	}

} Vertex;

// define graph

typedef struct Graph {

    // Vertex of Graph

    vector<Vertex> vertexes;

    // number of vertexes

    int nVertexes;

    bool isDAG;

	// construct function

    Graph(int n, bool isDAG) : nVertexes(n), isDAG(isDAG) { vertexes.resize(n); }  

    // add edge.

    bool addEdge(int id1, int id2) {

        if (max(id1, id2) >= vertexes.size())

		    return false;

        if (isDAG) {

            vertexes[id1].neighbors.push_back(id2);

        }

        else {

            vertexes[id1].neighbors.push_back(id2);

            vertexes[id2].neighbors.push_back(id1);

        }

        return true;

    }  

    // depth first search

    vector<int> DFS(int start) {

        set<int> visited;

        vector<int> g, result;

        g.push_back(start);

        visited.insert(start);

        result.push_back(start);

        bool found;

        while(g.size() > 0) {

            int id = g[g.size()-1];

            found = false;

            for(int i = 0; i < vertexes[id].neighbors.size(); i++) {

                int id1 = vertexes[id].neighbors[i];

                if (visited.count(id1) == 0) {

                    g.push_back(id1);

                    result.push_back(id1);

                    visited.insert(id1);

                    found = true;

                    break;

                }

            }

            // all neighbors have been visited

            if (!found) {

                int id2 = g[g.size()-1];

                //result.push_back(-1 * id2);

                //cout << "pop " << id2 << " ";

                g.pop_back();

            }

        }

        return result;

    }

    // breadth first search

    vector<int> BFS(int start) {

		set<int> visited;

        vector<int> g, result;

		// temporary store

        g.push_back(start);

        visited.insert(start);

        while(g.size() > 0) {

            int id = g[0];

            g.erase(g.begin());

            result.push_back(id);

            for(int i = 0; i < vertexes[id].neighbors.size(); i++) {

                int id1 = vertexes[id].neighbors[i];

                // if id1 is unvisited

                if (visited.count(id1) == 0) {

                    g.push_back(id1);

                    visited.insert(id1);

                }

            }

        }

        return result;

    }

} Graph;  

int main() {

    Graph g(8, true);

    g.addEdge(0, 1);

    g.addEdge(0, 3);

    g.addEdge(1, 2);

    g.addEdge(3, 4);

    g.addEdge(3, 5);

    //g.addEdge(4, 5);

    //g.addEdge(4, 6);

    g.addEdge(5, 6);

    g.addEdge(5, 7);

    //g.addEdge(6, 7);

    vector<int> bv = g.BFS(0);

    cout << "宽度优先搜索节点顺序：";

    for(int j = 0; j < bv.size(); j++)

        cout << bv[j] << " ";

    cout << endl;  

    bv = g.DFS(0);

    for(int j = 0; j < bv.size(); j++)

        cout << bv[j] << " ";

    cout << endl; 

    cout << "深度优先搜索节点顺序：";

    Graph g1(6, false);

    g1.addEdge(0, 1);

    g1.addEdge(0, 4);

    g1.addEdge(0, 5);

    g1.addEdge(1, 5);

    g1.addEdge(4, 5);

    g1.addEdge(5, 2);

    g1.addEdge(5, 3);

    g1.addEdge(2, 3);

    vector<int> route = g1.DFS(0);

    for(int i = 0; i < route.size(); i++)

        cout << route[i] << " ";

    cout << endl;  

    return 0;

}