bool processed[MAXV + 1];

bool discovered[MAXV + 1];

int parent[MAXV + 1];

void initialize_search(graph *g)

{

    int i;

    for (i = 1; i < g->nvertices; i++)

    {

        processed[i] = discovered[i] = false;

        parent[i] = -1;

    }

}

void process_vertex_late(int v)

{

}

void process_vertex_early(int v)

{

    printf("processed vertex %d\n", v);

}

void process_edge(int x, int y)

{

    printf("processed edge (%d %d)\n", x, y);

}

void bfs(graph *g, int start)

{

    std::queue <int> q;

    

    int v;

    int y;

    edgenode *p;

    

    q.push(start);

    discovered[start] = true;

    

    while(!q.empty())

    {

        v = q.front();

        q.pop();

        process_vertex_early(v);

        processed[v] = true;

        p = g->edges[v];

        while (p != NULL)

        {

            y = p->y;

            if ((processed[y] ==  false) || g->directed)

                process_edge(v, y);

            if (discovered[y] == false)

            {

                q.push(y);

                discovered[y] = true;

                parent[y] = v;

            }

            p = p->next;

        }

        process_vertex_late(v);

    }

}

void find_path(int start, int end, int parents[])

{

    if ((start == end) || (end == -1))

        printf("\n%d", start);

    else

    {

        find_path(start, parents[end], parents);

        printf(" %d", end);

    }

}

void connected_components(graph *g)

{

    int c, i;

    

    initialize_search(g);

    

    c = 0;

    for (i = 1; i <= g->nvertices; i++)

        if (discovered[i] == false)

        {

            c = c + 1;

            printf("Component %d:", c);

            bfs(g, i);

            printf("\n");

        }

}

int main(int argc, const char * argv[]) {

    graph *myGraph = (graph *)malloc(sizeof(graph));

    //read_graph(myGraph, false);

    // Or

    load_graphA(myGraph, false);

    

    print_graph(myGraph);

    

    initialize_search(myGraph);

    bfs(myGraph, 1);

    find_path(1, 4, parent);

}