Graph structure

BreadthFirstSearch.cpp

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

#define unvisited 1
#define visited 2
#define processed 3

#define fill(a, b) fill_n((a).begin(), n, (b))

typedef vector<int> list;

void BreadthFirstSearch(Graph &g, int start) {
  int n = g.vertices.size();
  list parents(n);
  list distance(n);
  list state(n);
  fill(parents, -1);
  fill(distance, numeric_limits<int>::max());
  fill(state, unvisited);

  queue<int> q;

  distance[start] = 0;
  q.push(start);

  while (!q.empty()) {
    int curV = q.front();
    state[curV] = visited;
    Node *tmp = g.vertices[curV];
    int y;

    for (int i = 0; i < tmp->adjacencies.size(); i++) {
      y = tmp->adjacencies[i]->y;
      if (state[y] == unvisited) {
        state[y] = visited;
        parents[y] = curV;
        distance[y] = distance[curV] + 1;
        q.push(y);
      }
    }

    state[curV] = processed;
    q.pop();
  }

  cout << "V\tP\tD" << endl;
  for (int i = 0; i < g.vertexIndices.size(); i++) {
    int v = g.vertexIndices[i];
    cout << v << "\t" << parents[v] << "\t" << distance[v] << endl;
  }
}

int main(int argc, char **argv) {
  Graph g(false);
  g.ReadIn();
  g.Print();

  BreadthFirstSearch(g, 1);

  return 0;
}

DepthFirstSearch.cpp

#include "Graph.h"

#define WHITE 1
#define GRAY  2
#define BLACK 3

typedef vector<int> list;

void DFSVisit(int v, Graph const &g, int &counter, list &discovered, list &processed, list &pred, list &colour) {
  cout << " " << v;
  colour[v] = GRAY;
  discovered[v] = ++counter;

  Node *tmp = g.vertices[v];
  int y;
  for (int i = 0; i < tmp->adjacencies.size(); i++) {
    y = tmp->adjacencies[i]->y;
    if (colour[y] == WHITE) {
      pred[y] = v;
      DFSVisit(y, g, counter, discovered, processed, pred, colour);
    }
  }
  colour[v] = BLACK;
  processed[v] = ++counter;
}

void DepthFirstSearch(Graph const &g, int start) {
  int n = g.vertices.size();
  list discovered(n);
  list pred(n);
  list processed(n);
  list colour(n);
  int counter = 0;
  int v;

  for (int i = 0; i < g.vertexIndices.size(); i++) {
    v = g.vertexIndices[i];
    discovered[v] = -1;
    pred[v] = -1;
    processed[v] = -1;
    colour[v] = WHITE;
  }

  DFSVisit(start, g, counter, discovered, processed, pred, colour);

  for (int i = 0; i < g.vertexIndices.size(); i++) {
    v = g.vertexIndices[i];
    if (colour[v] == WHITE)
      DFSVisit(v, g, counter, discovered, processed, pred, colour);
  }
}

int main(int argc, char **argv) {
  Graph g(false);
  cout << "Reading and printing graph..." << endl;
  g.ReadIn();
  g.Print();
  cout << endl;
  cout << "Depth first search..." << endl;
  DepthFirstSearch(g, 1);
  cout << endl;

  return 0;
}

Graph.cpp

#include "Graph.h"

Edge::Edge(int a, int w) {
  y = a; weight = w;
}

Graph::Graph(bool d) {
  directed = d;
}

void Graph::Resize(int x) {
  if (vertices.capacity() < x)
    vertices.resize(x);
}

void Graph::InsertEdge(int x, int y, int weight = 1) {
  Resize(((x > y) ? x : y) + 1);
  InsertVertex(x);
  InsertVertex(y);

  vertices[x]->adjacencies.push_back(new Edge(y, weight));
  if (!directed)
    vertices[y]->adjacencies.push_back(new Edge(x, weight));
}

void Graph::InsertVertex(int x) {
  if (vertices[x] == NULL) {
    Node *t = new Node;
    vertices[x] = t;
    vertexIndices.push_back(x);
  }
}

void Graph::ReadIn() {
  freopen("input.txt", "r", stdin);
  int v, edges;
  int x, y;
  scanf("%d %d", &v, &edges);
  Resize(v);
  
  for (int i = 0; i < edges; i++) {
    scanf("%d %d", &x, &y);
    InsertEdge(x, y);
  }
}

void Graph::Print() {
  Node *tmp;
  for (int i = 0; i < vertexIndices.size(); i++) {
    tmp = vertices[vertexIndices[i]];
    cout << vertexIndices[i];
    for (int j = 0; j < tmp->adjacencies.size(); j++) {
      cout << " " << tmp->adjacencies[j]->y;
    }
    cout << endl;
  }
}

Graph.h

#include <iostream>
#include <vector>

using namespace std;

class Edge {
  public:
    int y;
    int weight;

    Edge(int y, int w);
};

struct Node {
  vector<Edge *> adjacencies;
};

class Graph {
  public:
    vector<Node *> vertices;
    vector<int> vertexIndices;
    bool directed;

    Graph(bool directed);

    void Resize(int x);
    void InsertEdge(int x, int y, int weight);
    void InsertVertex(int x);

    void ReadIn();
    void PrintStats();
    void Print();
};