Depth First Search C++ implementation using adjacency list with two linked list

Question

I am a university student and this is my first time asking a question here. First of all thank you for taking the time to read. We have a project which is about Graphs. So far I did the creation of the graph through matrix and adjacency list . My version of the adjacency list is formed of 2 linked lists (just to allow adding as much vertex I want) . Now I am trying to make the Depth First Search . I did some research and seriously I didn't understand much , so i followed my own thinking.It is working but I am not sure if it is right or if the complexity is O(V+E) v refers to vertex and E to edges.. Can anyone read it and tell me if it's right ? and if it is how is the complexity O(V+E)? PS: please only use c++ as it's the only language I know. Thank you a lot for your help

what I did in the DFS is

1-do a while loop that goes through all vertex and calls DFS on each vertex 2- on each vertex , DFS is called , the color of the vertex will be grey ('g') 3-another while loop that goes through the children of target vertex (the edges) 4-on each children , another while loop will be searching for the corresponding edge through search-> value == child->value
5-when it finds the vertex it will call DFS again (so repeat step 2 till 5) 6-when done , color vertex black one after another

here are the codes :

EdgeNode.h

class EdgeNode
{
public:
    int value;
    EdgeNode *Next;
};

VertexNode.h

#include "EdgeNode.h"
class VertexNode
{
public:
    int value;
    int parentIndex;
    char color;
    EdgeNode *Child;
    VertexNode *Next;
};

Graph.h

#include "VertexNode.h"

class Graph{
public:

    int NbVertex;
    int time;
    VertexNode *s;
    Graph();
    void AddVertex(int value);
    bool AddEdge(int parentIndex, int value);
    void PrintVertex();
    void PrintGraph();
    void DepthFirstSearch();
    void DFS(VertexNode *V);


};

Graph.cpp

#include <iostream>
#include "Graph.h"
#include <string>
using namespace std;


Graph::Graph()
{
    s = NULL;
    NbVertex = 0;
}

void Graph::AddVertex(int value)
{
    if (NbVertex == 0)
    {
        s = new VertexNode;
        s->value = value;
        s->parentIndex = NbVertex+1;
        s->color = 'w';
        s->Child = NULL;
        s->Next = NULL;
    }

    else
    {
        VertexNode *z = s;
        while (z->Next != NULL)
        {
            z = z->Next;
        }
        z->Next = new VertexNode;
        z->Next->parentIndex = NbVertex+1;
        z->Next->color = 'w';
        z->Next->value = value;
        z->Next->Child = NULL;
        z->Next->Next = NULL;
    }


    NbVertex++;
}


bool Graph::AddEdge(int parentIndex, int value)
{
    if (NbVertex == 0)
        cout << "Graph is empty" << endl;

    VertexNode *z = s;

        while (z != NULL)
        {
            if (z->parentIndex == parentIndex)
            {


                if (z->Child == NULL)
                {
                    EdgeNode *y = new EdgeNode;
                    y->value = value;
                    y->Next = NULL;
                    z->Child = y;

                }

                else
                {
                    EdgeNode *y = z->Child;
                    while (y->Next != NULL)
                    {
                        if (y->value == value)
                        {
                            cout << "The edge already exists"<<endl;
                            return false;
                        }

                        y = y->Next;
                    }
                    y->Next = new EdgeNode;
                    y->Next->value = value;
                    y->Next->Next = NULL;

                }

                return true;

            }

            z = z->Next;

        }

        cout << "The index was not found" << endl;
    return false;

}


void Graph :: PrintVertex()
{
    VertexNode *z = s;
    int count = 1;
    while (z != NULL)
    {
        cout << "vertex " << count << " : " << endl;
        cout << "Value : " << z->value << endl;
        cout << "Index : " << z->parentIndex << endl;
        cout << "Next : " << z->Next << endl;
        cout << "Child : " << z->Child << endl;
        cout << "Color : "  << z->color << endl;
        cout << endl;
        count++;
        z = z->Next;
    }

    cout << "time is : " << time;
}


void Graph::PrintGraph()
{
    VertexNode *z = s;
    int countVertex = 1;
    while (z != NULL)
    {
        cout << "vertex " << countVertex << " : " << endl;
        cout << "Value : " << z->value << endl;
        cout << "Index : " << z->parentIndex << endl;
        cout << "Next : " << z->Next << endl;
        cout << "Child : " << z->Child << endl;
        cout << endl;
        countVertex++;
        if (z->Child != NULL)
        {
            int countChild=1;
            EdgeNode *y = z->Child;
            while (y != NULL)
            {
                cout << "Child " << countChild << " : " << endl;
                cout << "Value : " << y->value << endl;
                cout <<"Next : " << y->Next << endl;
                cout << "-------------------"<<endl;
                countChild++;
                y = y->Next;
            }

        }

        cout << "*************************************"<<endl;

        z = z->Next;
    }
}



void Graph :: DepthFirstSearch()
{
    time = 0;
    VertexNode *z = s;
    while (z != NULL)
    {
        if (z->color == 'w')
        {
            DFS(z);
        }
        z = z->Next;
    }

}
void Graph::DFS(VertexNode *V)
{
    cout << "(" << V->value;
    V->color = 'g';
    time++;

    EdgeNode *Y = V->Child;
    while (Y != NULL)
    {
        VertexNode *Search = s;
        while (Search != NULL)
        {
            if (Search->value == Y->value)
            {
                if (Search->color == 'w')
                {
                    DFS(Search);
                }
                /*else
                {
                    Search->color = 'b';
                }*/
            }

            Search = Search->Next;

        }

        Y = Y->Next;
    }

    V->color = 'b';
    time++;
    cout << V->value << ")";
}

this is the DFS

void Graph :: DepthFirstSearch()
{
    time = 0;
    VertexNode *z = s;
    while (z != NULL)
    {
        if (z->color == 'w')
        {
            DFS(z);
        }
        z = z->Next;
    }

}
void Graph::DFS(VertexNode *V)
{
    cout << "(" << V->value;
    V->color = 'g';
    time++;

    EdgeNode *Y = V->Child;
    while (Y != NULL)
    {
        VertexNode *Search = s;
        while (Search != NULL)
        {
            if (Search->value == Y->value)
            {
                if (Search->color == 'w')
                {
                    DFS(Search);
                }
                /*else
                {
                    Search->color = 'b';
                }*/
            }

            Search = Search->Next;

        }

        Y = Y->Next;
    }

    V->color = 'b';
    time++;
    cout << V->value << ")";
}

Answer 1

I don't know how organized your project should be, but the code for a graph built with adjacence list can take about 10 lines.

Quickly looking at it, your DFS seems right. Theoretically, the DFS (or BFS) time is O(V + E) just because it will pass through all the vertexes and all the edges (totalizing O(|V| + |E|).

If you care about code reading and organization, keep on going, but if you prefer less code instead, I'm sure you can find much smaller implementations of graphs.

There is a 5 line implementation of DFS that works fine.

void DFS(graph G, int v){
    mark[v] = true;
    cout<<"Visiting "<<v<<endl;
    for(auto u : G[v]) //this means "for all u in the adjacence list of v"
        if(!mark[u]) DFS(G, u);
}