Раздел «Алгоритмы».TopologicalSortCPP:

Пример кода топологической сортировки

Формулировка задачи и теория

Логика такая:

/*
    "Topological sort"

INPUT:
    Number of edges E followed by E lines. 
    Each line has "edge description" — two words of length < 20, that is 
     
    EXAMPLE: 
    IN:
4 
sport medecine
medecine science
medecine health
knowledge science

    OUT:
sport
medecine
knowledge
science
health
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define M 15            // max term width
#define N 1000          // maximum number of terms
#define NE 100          // maximum edges from one vertex
#define P 10007         // hash table size
#define MAX_LINE_LENGTH  100    // max line length in input

typedef struct
{
  int to;
  int w;
} edge;

/* edge's weights  */
edge a[N][NE];

/* ne[i] number of edges from i-th term  */
int ne[N];

/*  number of terms */
int n = 0;

/*  vetex color aray */
int v[N];

/*  color for colouring component */
int c;

/*  hash table */
int hash_table[P];

/*  terms */
char term[N][M];

/*  number of found vetexes from which we have already exit */
int count;

/* returns id of the term (index of term in aray term) */
int
getid (char *s)
{
  unsigned long i, h1 = 0, h2 = 0;

  /* calculate two hash values */
  for (i = 0; s[i]; i++)
    {
      h1 *= 13;
      h1 += s[i] % 13;
      h2 *= 17;
      h2 += s[i] % 17;
    }
  h1 %= P;
  h2 %= P - 1;
  h2++;             // h2 should be >0 and  < P 

  while (hash_table[h1] != -1)
    {
      /* collision or term is already known ?  */
      if (strcmp (term[hash_table[h1]], s) == 0) return hash_table[h1];
      // it is collision
      h1 += h2;
      h1 %= P;
    }

  /* we have new term — add then to array terms*/
  hash_table[h1] = n;
  strcpy (term[n], s);
  return n++;
}

/* DFS procedure. Outputs id in proper order */
void
dfs (int root)
{
  int i;
  v[root] = c;
  for (i = 0; i < ne[root]; i++)
    if (v[a[root][i].to] == 0)
      dfs (a[root][i].to);
  printf ("%s\n", term[root]);
}


int
main ()
{
  int i, j, id1, id2, m;

  /* Weight of the edge  */
  int w;

  /* Last scanned terms */
  char term1[M];
  char term2[M];
  char in[MAX_LINE_LENGTH];

  for (i = 0; i < P; i++) hash_table[i] = -1;
  for (i = 0; i < N; i++) ne[i] = 0;

  while (fgets (in, MAX_LINE_LENGTH, stdin) != NULL)
    {
        if(sscanf (in, "%s%s", term1, term2) == 2)
        {
          id1 = getid (term1);
          id2 = getid (term2);
          a[id2][ne[id2]].to = id1;
          a[id2][ne[id2]].w = w;
          ne[id2]++;
        }
    }

  c = 0;
  for (i = 0; i < n; i++) v[i] = 0;
  for (i = 0; i < n; i++) if (v[i] == 0)
     {
        c++;
        dfs (i);
    }

  return 0;
}

-- ArtemVoroztsov - 18 Mar 2004

AlgorithmClasifyForm
Type: Код
Scope: Графы
Strategy: Перебор с возвратом
Complexity: Medium