Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

Type code online

Basic BFS and derived codes

#include <stdio.h>
#include <vector>
#include <queue>
 
using namespace std;
 
// Graph representation
int N, M;
vector<vector<int> > edge;
 
 
void readGr(){
	scanf( "%d%d", &N, &M );
	edge.resize( N, vector<int>(0) );
 
	int n1, n2;
	for( int i = 0; i < M; i++ ) {
		scanf( "%d%d", &n1, &n2 );
		edge[n1].push_back( n2 );  // add edge
		edge[n2].push_back( n1 );  // add edge
	}
}
 
// print Graph, may help in debugging (sometimes greatly!) 
void prGr(){
  for( int i = 0; i < N; i++ ){
    printf( "%d _", i );
    for( int j = 0; j < edge[i].size(); j++ )
      printf( " %d", edge[i][j] );
    printf( "\n" );
  }
}
 
/*
Example methods based on BFS.
All methods work in O(|E|) time, 
however, they are a mere concept illustration
a therefore might be far from optimized.
*/
 
// --------------------------------------------------------------
 
void BFS( int start ){
  std::queue< int > q;
  std::vector< bool > fresh( N, true );
  q.push( start );
  fresh[start] = false;
 
  int currn, neigh;
  while( !q.empty() ){
    currn = q.front(); q.pop();
    for( int j = 0; j < edge[currn].size(); j++ ){
      neigh = edge[currn][j];
      if( fresh[neigh] ){
        q.push( neigh );
        fresh[neigh] = false;
        printf(" BFS edge: %d -> %d\n", currn, neigh );
      }
    }
  }
}
 
// --------------------------------------------------------------
 
bool isConnected(){
/**/  int start = 0;   // change #1
  std::queue< int > q;
  std::vector< bool > fresh( N, true );
  q.push( start );
  fresh[start] = false;
 
  int currn, neigh;
  while( !q.empty() ){
    currn = q.front(); q.pop();
    for( int j = 0; j < edge[currn].size(); j++ ){
      neigh = edge[currn][j];
      if( fresh[neigh] ){
        q.push( neigh );
        fresh[neigh] = false;
      }
    }
  }
 
/**/  // change #2
  for( int i = 0; i < N; i++ )
    if( fresh[i] ) return false;
  return true;
}
 
// --------------------------------------------------------------
 
bool isTree(){
/**/  int start = 0;   // change #1
  std::queue< int > q;
/**/  std::vector< bool > pred( N, -1 ); // change #2
  q.push( start );
 
  int currn, neigh;
  while( !q.empty() ){
    currn = q.front(); q.pop();
    for( int j = 0; j < edge[currn].size(); j++ ){
      neigh = edge[currn][j];
/**/    if( pred[neigh] == -1 ){  // change #3, formal, is neigh fresh?
        q.push( neigh );
        pred[neigh] = currn;
      }
/**/  else if( neigh != pred[currn] ) return false; // change #4
    }
  }
 
/**/  return true;  // change #5
}
 
// --------------------------------------------------------------
 
void distancesFrom( int start ){
  std::queue< int > q;
  std::vector< bool > fresh( N, true );
/**/  std::vector< int > dist( N, N+1 );  // change #1
 
  q.push( start );
  fresh[start] = false;
/**/  dist[start] = 0; // change #2
 
  int currn, neigh;
  while( !q.empty() ){
    currn = q.front(); q.pop();
    for( int j = 0; j < edge[currn].size(); j++ ){
      neigh = edge[currn][j];
 /**/ dist[neigh] = min(dist[neigh], 1+dist[currn]); // change #3
      if( fresh[neigh] ){
        q.push( neigh );
        fresh[neigh] = false;
      }
    }
  }
 
 /**/ // change #4
  for( int i = 0; i < N; i++ )
    printf( "dist(%d %d) = %d\n", start, i, dist[i]);
}
 
// --------------------------------------------------------------
 
 
void shortestPathFromTo( int start, int target ){
  std::queue< int > q;
  std::vector< bool > fresh( N, true );
/**/ std::vector< int > pred( N, -1 ); // change #1
 
/**/  q.push( target );  // change #2  -- swap target and start
/**/  fresh[target] = false;
 
  int currn, neigh;
  while( !q.empty() ){
    currn = q.front(); q.pop();
    for( int j = 0; j < edge[currn].size(); j++ ){
      neigh = edge[currn][j];
      if( fresh[neigh] ){
        q.push( neigh );
        fresh[neigh] = false;
/**/    pred[neigh] = currn;  // change #3
      }
    }
  }
 
 /**/ // change #4  -- list the path
  printf("shortest path: %d", start);
  while( start != target ) {
    start = pred[start];
    printf( " -> %d", start);
  }
  printf( "\n" );
}
 
// --------------------------------------------------------------
 
int distanceFromTo( int start, int target ){
  std::queue< int > q;
  std::vector< bool > fresh( N, true );
/**/  std::vector< int > dist( N, N+1 );  // change #1
 
  q.push( start );
  fresh[start] = false;
/**/  dist[start] = 0; // change #2
 
  int currn, neigh;
  while( !q.empty() ){
    currn = q.front(); q.pop();
    for( int j = 0; j < edge[currn].size(); j++ ){
      neigh = edge[currn][j];
/**/  dist[neigh] = min(dist[neigh], 1+dist[currn]); // change #3
/**/  if( neigh == target ) return dist[neigh]; // change #4
      if( fresh[neigh] ){
        q.push( neigh );
        fresh[neigh] = false;
      }
    }
  }
/**/ return -1; // change #5
}
 
// --------------------------------------------------------------
 
int mostDistantNode( int start ){
  std::queue< int > q;
  std::vector< bool > fresh( N, true );
/**/  std::vector< int > dist( N, N+1 );  // change #1
 
  q.push( start );
  fresh[start] = false;
/**/  dist[start] = 0; // change #2
 
  int currn, neigh;
  while( !q.empty() ){
    currn = q.front(); q.pop();
    for( int j = 0; j < edge[currn].size(); j++ ){
      neigh = edge[currn][j];
 /**/ dist[neigh] = min(dist[neigh], 1+dist[currn]); // change #3
      if( fresh[neigh] ){
        q.push( neigh );
        fresh[neigh] = false;
      }
    }
  }
 
 /**/ // change #4
 int maxdist = 0, maxdistnode = start;
  for( int i = 0; i < N; i++ )
    if( dist[i] > maxdist )
    { maxdist = dist[i]; maxdistnode = i;}
 return maxdistnode;
}
 
// --------------------------------------------------------------
 
int treeDiameter() {
  // just a demo(!), distanceFromTo performs additional redundant search.
  int node1 = mostDistantNode( 0 ); // start anywhere
  int node2 = mostDistantNode( node1 );
  return distanceFromTo( node1, node2 );
}
 
// --------------------------------------------------------------
 
// Fill in yourself:
// bool isBipartite(){
// }
 
// --------------------------------------------------------------
 
int main() {
 
  readGr();
  prGr();
  BFS( 3 );
  printf( "Connected: %s\n", isConnected()? "Yes" : "No" );
  printf( "Is a tree: %s\n", isTree() ? "Yes" : "No" );
  distancesFrom( 1 );
  shortestPathFromTo( 4, 0 );
  if( isTree() ) printf( "Tree Diameter: %d\n", treeDiameter() );
 
return 0;
}

Dijkstra and MST codes

// MST and Dijkstra compared
// Note the sort method in Kruskal alg.
 
import java.util.*;
import java.io.*;
 
public class Solvers {
 
static void dijkstraNsquared(Graph g, int start,  final int [] dist, int [] pred ) {
  int INF = Integer.MAX_VALUE;
  int currnode = start, currdist, neigh;
  boolean [] closed = new boolean [g.N];
 
  for(int i = 0; i < g.N; i++) pred[i] = i;
  Arrays.fill(dist, INF);
  Arrays.fill(closed, false);
  dist[start] = 0;
 
  for( int i = 0; i < g.N; i++ ){
    // find the closest node
    currdist = INF;
    for( int j = 0; j < g.N; j++)
      if( !closed[j] && dist[j] < currdist ){
        currdist = dist[j];
        currnode = j;
      }
 
    // expand the closest node and close it
    for( int j = 0; j < g.dg[currnode]; j++ ){
      neigh = g.edge[currnode][j];
      if( !closed[neigh] && ( dist[neigh] > dist[currnode] + g.w[currnode][j]) ) {
        dist[neigh] = dist[currnode] + g.w[currnode][j];
        pred[neigh] = currnode;
      }
     closed[currnode] = true;
    }
  } // for N steps
}
 
public static void dijkstraElogN(Graph g, int start, final int [] dist, int [] pred ) {
  int currnode = start, currdist, neigh;
  int INF = Integer.MAX_VALUE;
  boolean [] closed = new boolean[g.N];
 
  PriorityQueue <Integer> pq
    = new PriorityQueue<Integer> (g.N,
          new Comparator<Integer>() {
            @Override
            public int compare(Integer n1, Integer n2) {
              if( dist[n1] < dist[n2] ) return -1;
              if( dist[n1] > dist[n2] ) return 1;
              return 0;
            }
          }
      );
 
  pq.add(start);
  for(int i = 0; i < g.N; i++) pred[i] = i;
  Arrays.fill(dist, INF);
  Arrays.fill(closed, false);
  dist[start] = 0;
 
  for(int i = 0; i < g.N; i++) {
    // take the closest node
    while( closed[currnode = pq.poll()] == true );
    // and expand it
    for( int j = 0; j < g.dg[currnode]; j++ ){
      neigh = g.edge[currnode][j];
      if( !closed[neigh] && ( dist[neigh] > dist[currnode] + g.w[currnode][j]) ) {
        dist[neigh] = dist[currnode] + g.w[currnode][j];
        pred[neigh] = currnode;
        pq.add(neigh);
      }
     closed[currnode] = true;
    }
  }
}
 
 
static void MST_Nsquared(Graph g, int start,  final int [] dist, int [] pred ) {
  int INF = Integer.MAX_VALUE;
  int currnode = start, currdist, neigh;
  boolean [] closed = new boolean [g.N];
 
  for(int i = 0; i < g.N; i++) pred[i] = i;
  Arrays.fill(dist, INF);
  Arrays.fill(closed, false);
  dist[start] = 0;
 
  for( int i = 0; i < g.N; i++ ){
    // find the closest node
    currdist = INF;
    for( int j = 0; j < g.N; j++)
      if( !closed[j] && dist[j] < currdist ){
        currdist = dist[j];
        currnode = j;
      }
 
    // expand the closest node and close it
    for( int j = 0; j < g.dg[currnode]; j++ ){
      neigh = g.edge[currnode][j];
      if( !closed[neigh] && ( dist[neigh] > g.w[currnode][j]) ) {
        dist[neigh] = g.w[currnode][j];
        pred[neigh] = currnode;
      }
     closed[currnode] = true;
    }
  } // for N steps
}
 
 
 
public static void MST_ElogN(Graph g, int start, final int [] dist, int [] pred ) {
  int currnode = start, currdist, neigh;
  int INF = Integer.MAX_VALUE;
  boolean [] closed = new boolean[g.N];
 
  PriorityQueue <Integer> pq
    = new PriorityQueue<Integer> (g.N,
          new Comparator<Integer>() {
            @Override
            public int compare(Integer n1, Integer n2) {
              if( dist[n1] < dist[n2] ) return -1;
              if( dist[n1] > dist[n2] ) return 1;
              return 0;
            }
          }
      );
 
  pq.add(start);
  for(int i = 0; i < g.N; i++) pred[i] = i;
  Arrays.fill(dist, INF);
  Arrays.fill(closed, false);
  dist[start] = 0;
 
  for(int i = 0; i < g.N; i++) {
    // take the closest node
    while( closed[currnode = pq.poll()] == true );
    // and expand it
    for( int j = 0; j < g.dg[currnode]; j++ ){
      neigh = g.edge[currnode][j];
      if( !closed[neigh] && ( dist[neigh] > g.w[currnode][j]) ) {
        dist[neigh] = g.w[currnode][j];
        pred[neigh] = currnode;
        pq.add(neigh);
      }
     closed[currnode] = true;
    }
  }
}
 
 
public static void MST_Kruskal(Graph g, int [] edgesMST ) {
 
  // store edges in one arr and sort them
  int [] edges = new int[g.M*3];
  int k = 0;
  for( int i = 0; i < g.N; i++ )
    for( int j = 0; j < g.dg[i]; j++ ) {
      if( i <  g.edge[i][j] ) {
        edges[k++] = g.w[i][j];
        edges[k++] = i;
        edges[k++] = g.edge[i][j];
      }
    }
   qSort3( edges, 0, edges.length-3 );
 
   // construct the MST with UF
   initUF( g.N );
   int edgesCount = 0, set1, set2;
   k = 0;
   while( edgesCount < g.N-1 ){
     set1 = UF_find(edges[k+1]); set2 = UF_find(edges[k+2]);
     if( set1 != set2 ) {  // found an edge of MST
       UF_union( set1, set2 );
       edgesCount++;
       edgesMST[edgesCount*2-2] = edges[k+1]; edgesMST[edgesCount*2-1] = edges[k+1] ;
     }
     k += 3;
   }
}
 
 
 
  public static void main( String[] args ) {
  int [] p = {3, 10, 11, -3, 22, 25, 7, 33, 34, 4, 42, 43, 2, 56, 56 };
  qSort3(p, 0, p.length-3);
  list(p);
 
 
  }
 
 
static void list (int [] a) {
  for( int x : a )
    System.out.printf("%2d ", x);
  System.out.printf("\n");
}
 
 
 
static void qSort(double a[], int low, int high) {
  int iL = low, iR = high;
  double pivot = a[low];
  double aux;
  do {
    while (a[iL] < pivot) iL++;
    while (a[iR] > pivot) iR--;
    if (iL < iR) {
      //swap(a,iL, iR);
      aux = a[iL]; a[iL] = a[iR]; a[iR] = aux;
       iL++; iR--;
    }
    else
      if (iL == iR) { iL++; iR--;}
 
  } while( iL <= iR);
 
  if (low < iR)  qSort(a, low, iR);
  if (iL < high) qSort(a, iL, high);
}
 
 
// always points to i%3=0 elem which stores the key
static void qSort3(int a[], int low, int high) {
  int iL = low, iR = high;
  int pivot = a[low];
  int aux;
  do {
    while (a[iL] < pivot) iL+=3;
    while (a[iR] > pivot) iR-=3;
    if (iL < iR) {
      //swap(a,iL, iR);
      for(int k = 0; k < 3; k++ )
      { aux = a[iL+k]; a[iL+k] = a[iR+k]; a[iR+k] = aux; }
      iL+=3; iR-=3;
    }
    else
      if (iL == iR) { iL+=3; iR-=3;}
 
  } while( iL <= iR);
 
  if (low < iR)  qSort3(a, low, iR);
  if (iL < high) qSort3(a, iL, high);
}
 
// uf
 
static int [] sets;
static int [] sizes;
static int elem1;
 
 
static void initUF(int n) {
  sets = new int [n];
  sizes = new int [n];
  for(int i = 0; i < n; i++) {
    sets[i] = i;
    sizes[i] = 1;
  }
}
 
static void UF_union(int a, int b) {
  //System.out.printf(" unioning %d %d \n", a, b);
  if (sizes[b] > sizes[a]) {
    sets[a] = b;
    sizes[b] += sizes[a];
  }
  else {
    sets[b] = a;
    sizes[a] += sizes[b];
  }
}
 
static int UF_find(int a) {
  elem1 = a;
  while (a != sets[a])
    a = sets[a];
  sets[elem1] = a;  // shorten the path
  return a;
}
 
static void listSet(int a) {  // for debuggin purposes only
  int finda = UF_find(a);
  for(int i = 0; i < sets.length; i++)
    if(UF_find(i) == finda)
      System.out.printf("%d ", i);
  System.out.printf("\n");
}
 
}

Elementary DAG manipulation

#include <stdio.h>
#include <climits>
#include <vector>
 
using namespace std;
 
int N, E, NIL = -1;
vector<vector<int> > arc;
vector<vector<int> > wei;
 
vector<bool> visited;
vector<int> topSort;
 
 
void readGr(){
  scanf( "%d%d", &N, &E );
  arc.resize( N, vector<int>(0) );
  wei.resize( N, vector<int>(0) );
  visited.resize( N );
 
  int n1, n2, w;
  for( int i = 0; i < E; i++ ) {
    scanf( "%d%d%d", &n1, &n2, &w );
    arc[n1].push_back( n2 );  // add directed arc
    wei[n1].push_back( w );   // add arc weight
  }
}
 
void prGr(){
  for( int i = 0; i < N; i++ ){
    printf( "%d _", i );
    for( int j = 0; j < arc[i].size(); j++ )
      printf( " %2d:%2d", arc[i][j], wei[i][j] );
    printf( "\n" );
  }
}
 
void DFS_rec( int node ){
  visited[node] = true;
  for( int j = 0; j < arc[node].size(); j++ )
    if( !visited[arc[node][j]] )
      DFS_rec( arc[node][j]);
  topSort.push_back( node );
}
 
void DFS(){
  std::fill(visited.begin(), visited.end(), false);
  topSort.clear();
 
  for( int start = 0; start < N; start++ )
    if( !visited[start] )
      DFS_rec( start );
}
 
int findIndexOfMax( std::vector<int> & v ){
  int max = INT_MIN, imax = -1;
  for( int i = 0; i < v.size(); i++ )
    if( v[i] > max ) {
      max = v[i];
      imax = i;
  }
  return imax;
}
 
void printPath( std::vector<int> & path, int start ){
  printf( "Longest path: \n" );
  while( start != NIL ){
    printf( " %d", start );
    start = path[start];
  }
  printf( "\n" );
}
 
void longestPath() {
  std::vector< int > pathNext( N, NIL );
  std::vector< int > dist( N, 0 );
 
  int currnode, neigh;
  for( int i = 0; i < N; i++ ){ // progress in reverse top order
    currnode = topSort[i];
    for( int j = 0; j < arc[currnode].size(); j++ ){
      neigh = arc[currnode][j];
      if ( dist[currnode] < dist[neigh] + 1 ){
        dist[currnode] = dist[neigh] + 1;
        pathNext[currnode] = neigh;
      }
    }
  }
  int start = findIndexOfMax( dist );
  printPath( pathNext, start );
}
 
 
void longestPathWeight() {
  std::vector< int > pathNext( N, NIL );
  std::vector< int > dist( N, 0 );
 
  int currnode, neigh;
  for( int i = 0; i < N; i++ ){ // progress in reverse top order
    currnode = topSort[i];
    for( int j = 0; j < arc[currnode].size(); j++ ){
      neigh = arc[currnode][j];
      if ( dist[currnode] < dist[neigh] + wei[currnode][j] ){
        dist[currnode] = dist[neigh] + + wei[currnode][j];
        pathNext[currnode] = neigh;
      }
    }
  }
  int start = findIndexOfMax( dist );
  printPath( pathNext, start );
}
 
///////////////////////////   M A I N   /////////////////////////////////
int main() {
 
  readGr();
  prGr();
  DFS();
  printArr( topSort );
  longestPathWeight();
    return 0;
}
 
/*
5 5
0 1 10
1 2 20
2 3 30
2 4 40
0 2 150
*/

courses/a4b36acm1/2016_zs/code.txt · Last modified: 2018/10/03 03:51 (external edit)