# Graph as adjacency lists: BFS DFS Topological Sort

I have written some code to practise graphs. Graph is represented as vector<list<int>> . Would you share some feedback with me? Are algorithms correct and perform well?

I implemented graph using vector<list<>> because of the name "adjacency lists". However now I think using unordered_map would be cleaner and would perform better, right? I plan to modify it later with a tamplate.

# graph.h

#include <vector>
#include <list>
#include <iostream>
#include <iterator>
#include <queue>
#include <stack>

class Graph {
public:
Graph(): numOfVert {}, adjacencyLists {} {}
Graph(int n): numOfVert {n}{
adjacencyLists.resize(n);
}
void addEdge(std::pair<int,int> p);
void topoSort();
void DFS(int start);
void BFS(int start);
void print();
private:
int numOfVert;
std::vector<std::list<int>> adjacencyLists;
};

void Graph::addEdge(std::pair<int,int> p){
if(p.first >= numOfVert || p.second >= numOfVert){
numOfVert = p.second > p.first ? p.second + 1 : p.first + 1;
adjacencyLists.resize(numOfVert);
}
adjacencyLists[p.first].push_back(p.second);
}

void Graph::print(){
for(unsigned i = 0; i != adjacencyLists.size(); ++i){
std::cout << i << " | ";
std::copy(adjacencyLists[i].cbegin(),
adjacencyLists[i].cend(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
}
}

void Graph::DFS(int start){
std::cout << "DFS: ";
std::vector<int> visited(numOfVert, 0);
std::stack<int> s; s.push(start);
while(!s.empty()){
int curr = s.top(); s.pop();
std::cout << curr << " ";
for(const auto x: adjacencyLists.at(curr)){
if(visited.at(x) == 0){
s.push(x);
visited.at(x) = 1;
}
}
}
std::cout << "\n";
}

void Graph::BFS(int start){
std::cout << "BFS: ";
std::vector<int> visited(numOfVert, 0);
std::queue<int> q; q.push(start);
while(!q.empty()){
int curr = q.front(); q.pop();
std::cout << curr << " ";
visited.at(curr) = 1;
for(const auto x: adjacencyLists.at(curr)){
if(visited.at(x) == 0){
q.push(x);
visited.at(x) = 1;
}
}
}
std::cout << "\n";
}

void Graph::topoSort(){
std::vector<int> incom_rank (numOfVert, 0);
std::queue<int> next;
std::queue<int> sorted;
// create array of incoming edge rank
for(unsigned i = 0; i != adjacencyLists.size(); ++i){
for(const auto x: adjacencyLists.at(i)) ++incom_rank.at(x);
}
// populating queue next
for(unsigned i = 0; i != incom_rank.size(); ++i){
if(incom_rank.at(i) == 0) next.push(i);
}
while(!next.empty()){
int curr = next.front(); next.pop();
sorted.push(curr);
for(const auto x: adjacencyLists.at(curr)){
--incom_rank.at(x);
if(incom_rank.at(x) == 0) next.push(x);
}
}
// print out toposorted graph
std::cout << "TSort: ";
while(!sorted.empty()){
std::cout << sorted.front() << " ";
sorted.pop();
}
}


# main.cpp

#include "Graph.h"
#include <set>

int main(){
Graph g(10);
std::set<std::pair<int,int>> E {{0,2},{1,3},{2,3},{2,4},{4,5},{3,5},{5,6},
{6,7},{5,10},{7,12},{11,12},{8,9},{9,10},
{10,11},{12,13}};
for(auto& x: E) g.addEdge(x);
g.print();
g.topoSort();
}