This is an implementation of a directed graph (data structure), its traversals, and its complementary algorithms. These include:

• Breadth First Search (traversal)
• Depth First Search (traversal)
• Topological Sort (traversal)
• Algorithm to check if graph is cyclic
• Algorithm to check if graph is a tree
• Algorithm to check if graph is bipartite

The graphs are represented using an adjacency list as well as an adjacency matrix, and are generated by reading files. Currently, the program is set to read 4 files, therefore generating 4 graphs; but it may be changed to read up to any number of files.

Project uses C++11

Place all files in the same folder and run main.cpp. The results will be shown in terminal.

To read more or less files, and therefore test more or less graphs, simply change the value of the variable numberFiles in the main function. All files must be named in the following format: graph_#.txt, example: graph_4.txt.

Here are the contents of one of the files:
4
4
0,1
0,3
1,3
3,2

The first line is for the number of vertices in the graph, the second for the number of adjacencies, and the rest represent the adjacencies. For example, there is a directed adjacency from vertex 0 to vertex 1. Notice every adjacency is written on its own line and is represented by two numbers seperated by a comma.

The breadth first search algorithm is a way to traverse and/or search a graph. This is an implementation of a traversal. It uses a queue to visit the vertices. This algorithm uses a "neighbors" approach. First it creates a boolean array to mark the vertices that have been visited, starting with all of them as not visited. It visits the starting vertex, marks it as visited, and enqueues it. Then it enters a loop where it prints the first vertex of the queue, dequeues it, visits all its adjacent vertices, marks them as visited, and enques them. Only the vertices that haven't already been visited will be enqueued. This process will be repeated until the queue is empty. For every iteration, it will visit a vertex and all its adjacent vertices. Therefore, assuming all vertices can be reached, by the end of the traversal it will have visited all vertices and all adjacencies. This is why the breadth first search algorithm has a big O complexity of O(V+E), where V is the number of vertices and E the number of "edges" or adjacencies.

In graph.h

void breadthFirstSeach(int firstVertex) {
    //Create a boolean array and mark all vertices as not visited
    bool *visited = new bool[number_vertices_];
    for(int i=0; i<number_vertices_; ++i)
        visited[i] = false;

    //Queue to store visited vertices
    queue<int> q;

    //Mark starting vertex as visited and enqueue it
    visited[firstVertex] = true;
    q.push(firstVertex);

    //Iterator for getting adjacent vertices
    list<int>::iterator i;

    //While the queue is not empty
    while(!q.empty()) {
        //Get first vertex and print it
        firstVertex = q.front();
        cout << firstVertex << " ";
        //Dequeue vertex
        q.pop();

        //Visit all adjacent vertices of current vertex
        for(i=adj_list_[firstVertex].begin(); i!=adj_list_[firstVertex].end(); ++i) {
            //If the vertex hasn't been visited, enqueue it and mark as visited
            if(!visited[*i]) {
                q.push(*i);
                visited[*i] = true;
            }
        }
    }
}

The depth first search algorithm is another way to traverse and/or search a graph. This is also an implementation of a traversal. This algorithm uses a recursive function to visit the vertices. This method also uses an array of boolean values to mark the visited vertices. It uses a "path" approach: it will visit vertices going down a path from the starting vertex, printing the vertices and marking them as visited, until it reaches a dead end or a vertex that has already been visited. Then it repeats the process for all vertices in the "path". Again, assuming all vertices can be reached, by the end of the traversal it will have visited all vertices and their respective adjacencies, so it will have visited the total number of adjacencies. Therefore, it also has a big O complexity of O(V+E).

In graph.h

void depthFirstSearch(int firstVertex) {
    //Create a boolean array and mark all vertices as not visited
    bool *visited = new bool[number_vertices_];
    for(int i=0; i<number_vertices_; ++i)
        visited[i] = false;

    //Call recursive helper function
    recursiveDepthFirstSearch(firstVertex,visited);
}

void recursiveDepthFirstSearch(int currentVertex, bool visited[]) {
    //Mark current vertex as visited and print
    visited[currentVertex] = true;
    cout << currentVertex << " ";

    //Recur for all adjacent vertices that have not been visited yet
    list<int>::iterator i;
    for(i=adj_list_[currentVertex].begin(); i!=adj_list_[currentVertex].end(); ++i) {
        if(!visited[*i])
            recursiveDepthFirstSearch(*i,visited);
    }
}

A topological sort is yet another way to traverse/search a graph. This is also an implementation of a traversal. It's very similar to depth first search in the way it visits the vertices. The difference is that a topological traversal will always visit all the vertices regardless of whether they can be reached via the graph's connections, storing them in a stack and printing until the end. It's also worth noting that it will only push the current vertex to the stack when all it's adjacent vertices have already been visited and added to the stack. In this way, every vertex will be printed before its adjacent vertices. A topological sort is only possible in directed acyclic graphs, which is why before calling the topological sort function, it's important to check if the graph is cyclic. Because this process is essentially the same as a depth first search, it also has a big O complexity of O(V+E). This is easy to see: in the function topologicalSort there is a loop the size of the number of vertices (V), and in the function recursiveTopologicalSort there is a loop the size of the current vertex's adjacencies, so that by the end of the traversal it will have visited the total number of adjacencies (E).

In graph.h

void topologicalSort() {
    //Create a boolean array and mark all vertices as not visited
    bool *visited = new bool[number_vertices_];
    for(int i=0; i<number_vertices_; ++i)
        visited[i] = false;

    //Stack to store visited vertices
    stack<int> topologicalStack;

    //Call recursive function for all vertices
    for(int i=0; i<number_vertices_; ++i) {
        //Only call if it hasn't been visited
        if(!visited[i])
            recursiveTopologicalSort(i,visited,topologicalStack);
    }

    //Print stack
    while(!topologicalStack.empty()) {
        cout << topologicalStack.top() << " ";
        topologicalStack.pop();
    }
}

void recursiveTopologicalSort(int currentVertex, bool visited[], stack<int>& topologicalStack) {
    //Mark current vertex as visited
    visited[currentVertex] = true;

    //Recur for all adjacent vertices
    list<int>::iterator i;
    for(i=adj_list_[currentVertex].begin(); i!=adj_list_[currentVertex].end(); ++i) {
        //Only recur if it hasn't been visited
        if(!visited[*i])
            recursiveTopologicalSort(*i, visited, topologicalStack);
    }

    //Push current vertex to stack
    topologicalStack.push(currentVertex);
}