Efficient algorithms - Lecture 7

Topic: Graphs

Graphs

This class will introduce the concept of a graph and the definitions associated with it. Later on, the most important definitions related to graphs will also appear here.

graphs representation

We can distinguish the following graph representations:

Edges list
Incidence matrix
Array of edges list
Double-array representation

Graph search algorithms

BFS

Breadth-first search.

DFS

Depth-first search.

Codes that can help

Template for array (list) of list

template < class V, class E > struct Graph {
  struct Edge : E {int v; Edge(E p, int w) : E(p), v(w) {}};
  struct Vertex : V,vector < Edge > {
  };
  vector < Vertex  > g;
  Graf(int n=0) : g(n) {}
  void AddEdge(int p, int k, E d) {
    Edge v(d,k);
    g[p].PB(v);
  }
  void AddEdge(int p, int k) {E d; AddEdge(p,k,d);}
}

struct Vs{int t,s;};
struct Ve{};
int main() {
  Graph < Vs,Ve > gr(n);

Process an array of edges into a double-array representation

  int n,m;
  int t[101], s[2001];

    cin >> n >> m;
    int i, dane[1001][2];

    for (i=0; i <=n; i++) t[i]=0;
    for (i=0; i < m; i++)
    {
      cin >> dane[i][1] >> dane[i][2];
      t[dane[i][1]+1]++;
      t[dane[i][2]+1]++;
    }

    t[1]=1;
    for (i=1; i < n; i++) t[i+1]+=t[i];

    for (i=0; i < m; i++)
    {
      s[t[dane[i][1]]++]=dane[i][2];
      s[t[dane[i][2]]++]=dane[i][1];
    }

    for (i=n+1; i > 0; i--) t[i+1]=t[i];
    t[1]=1;

Loop through all neighbors of vertex x:

   for (i=t[x]; i < t[x+1]; i++) // you can find the neighbors of vertex i in s[i]