Graph representation and graph traversal

A graph is a data structure that represent a collection of vertices and edges, that store connectivity information,

I will show how to represent a graph in 2 ways, and two graph traversal algorithms dfs, bfs. Finally i will add the snippets to load a graph, and dfs, bfs algorithms in c++.

You can get more theory information here: http://en.wikipedia.org/wiki/Graph_theory

Representation

A Adjacency matrix: Is a connectivity table represented in a 2D matrix int AdjMat[v][v]. For an unweighted graph we can set AdjMat[i][j] = 1 if there is connectivity otherwise the weigth.

B Adjacency List: Is a vector of vector of pairs. Here we store the information of the nodes in pairs. Neighbor and weight.

Graph Traversal

This is a video that explains in a clearly way two graph traversal algorithms, Deep First Search, Breadth First Search.

Snippets

BFS

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define MAXN    500

using namespace std;

vector < vector <int> > graph(MAXN);
bool discovered[MAXN];//keeps track if a node has been reached
int parent[MAXN];//stores the nodes ancestor that discovered it for the first time
int distances[MAXN];//stores the distance to reach each node from the source

void init_graph(int vertices)
{
    int i;
    for(i = 0; i < vertices; i++)
    {
        discovered[i] = false;
        graph[i].clear();
        distances[i] = parent[i] = -1;
    }
}

void read_graph(int edges)
{
    int vertex1,  vertex2;
    int i;
    for(i = 0; i < edges; i++)
    {
        scanf("%d %d", &vertex1, &vertex2);
        graph[vertex1].push_back(vertex2);
        graph[vertex2].push_back(vertex1);
    }
}

void bfs(int start)
{
    int current;//current node being processed
    int next;//reached node by current
    unsigned int i;
    queue<int> vertices;//vertices to process
    distances[start] = 0;
    discovered[start] = true;
    vertices.push(start);
    while(!vertices.empty())
    {
        current = vertices.front();
        vertices.pop();
        for(i = 0; i < graph[current].size(); i++)//for each node connected to current
        {
            next = graph[current][i];
            if(!discovered[next])//if it hasn't been reached
            {
                discovered[next] = true;//mark it as reached
                parent[next] = current;//store its parent
                distances[next] = distances[current]+1;//save the distance
                vertices.push(next);//push it to the queue for further analysis
            }
        }
    }
}

void find_path(int vertex)//recursive procedure to find the path
{
    if(vertex == -1)
        return;
    find_path(parent[vertex]);
    printf("%d ", vertex);
}

int main()
{
    int vertices;
    int edges;
    int start;
    int dest_path;
    int i;
    scanf("%d %d", &vertices,  &edges);
    init_graph(vertices);
    read_graph(edges);
    scanf("%d", &start);
    bfs(start);
    for(i = 0; i < vertices; i++)
        printf("%d ",distances[i]);
    printf("\n");
    scanf("%d", &dest_path);
    find_path(dest_path);
    return 0;
}

DFS

 

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

typedef pair<int, int> ii;      // In this chapter, we will frequently use these
typedef vector<ii> vii;      // three data type shortcuts. They may look cryptic
typedef vector<int> vi;   // but shortcuts are useful in competitive programming

#define DFS_WHITE -1 // normal DFS, do not change this with other values (other than 0), because we usually use memset with conjunction with DFS_WHITE
#define DFS_BLACK 1

vector<vii> AdjList;

void printThis(char* message) {
  printf("==================================\n");
  printf("%s\n", message);
  printf("==================================\n");
}

vi dfs_num;     // this variable has to be global, we cannot put it in recursion
int numCC;

void dfs(int u) {          // DFS for normal usage: as graph traversal algorithm
  printf(" %d", u);                                    // this vertex is visited
  dfs_num[u] = DFS_BLACK;      // important step: we mark this vertex as visited
  for (int j = 0; j < (int)AdjList[u].size(); j++) {
    ii v = AdjList[u][j];                      // v is a (neighbor, weight) pair
    if (dfs_num[v.first] == DFS_WHITE)         // important check to avoid cycle
      dfs(v.first);      // recursively visits unvisited neighbors v of vertex u
} }

int main() {
  int V, total_neighbors, id, weight;

  /*
  // Use the following input:
  // Graph in Figure 4.1

  */

  //freopen("in_01.txt", "r", stdin);

  scanf("%d", &V);
  AdjList.assign(V, vii()); // assign blank vectors of pair<int, int>s to AdjList
  for (int i = 0; i < V; i++) {
    scanf("%d", &total_neighbors);
    for (int j = 0; j < total_neighbors; j++) {
      scanf("%d %d", &id, &weight);
      AdjList[i].push_back(ii(id, weight));
    }
  }

  printThis("Standard DFS Demo (the input graph must be UNDIRECTED)");
  numCC = 0;
  dfs_num.assign(V, DFS_WHITE);    // this sets all vertices' state to DFS_WHITE
  for (int i = 0; i < V; i++)                   // for each vertex i in [0..V-1]
    if (dfs_num[i] == DFS_WHITE)            // if that vertex is not visited yet
      printf("Component %d:", ++numCC), dfs(i), printf("\n");   // 3 lines here!

  return 0;
}