ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Stanislav Shwartsman                 2:400/520      02 Jul 2001  15:31:39
 To : Aleksey Mashihin
 Subject : help
 -------------------------------------------------------------------------------- 
 

 
 01 Jul 01 01:37, you wrote to me:
 
  AM> А ты не можешь кинуть пример или хотя бы обьяснить на основе простой
  AM> программы Что такое DFS ?
 
  Deep-First Search, смысл алгоритма - посчитать для каждой вершины
  "open time" и "close time". Эти два значения очень помогают во многих
  алгоритмах и задачах.
 
  В частности вот так они могут помочь в задаче о поиске компонентов
  связности:
 
  1. В данном графе G запустим DFS и получим open и close time для всех
     вершин.
 
  2. Отсортируем вершины в порядке убывания close time
 
  3. Запустим DFS в графе G', полученном обращением всех его дуг, по порядку,
     полученному в (2) пункте. Если граф не ориентированный (направление
     значения не имеет), то дуги можно не переворачивать ;)
 
  результат: Деревья DFS, которые получились = компоненты связности.
 
  Правда если граф не ориентированный, то действительно можно придумать
  чего-то более интеллектуальное. Это решение для ориентированных графов.
 
 === Cut ===
 #include <stdio.h>
 #include <stdlib.h>
 
 enum COLORS { WHITE, GRAY, BLACK };
 
 struct vertex_info {
    int parent, color, open_time, close_time;
 };
 
 void DFS(int *graf, vertex_info *vertices, int n_vertices);
 void DFS_visit(int *graf, vertex_info *vertices, int vertex, int n_vertices);
 
 static int systime = 0;     // global variable
 
 void DFS(int *graf, vertex_info *vertices, int n_vertices)
 {
     systime = 0;
     for(int i=0;i<n_vertices;i++) {
     vertices[i].parent = -1;
     vertices[i].color = WHITE;
     }
     for(int i=0;i<n_vertices;i++)
     if(vertices[i].color == WHITE)
        DFS_visit(graf, vertices, i, n_vertices);
 }
 
 void DFS_visit(int *graf, vertex_info *vertices, int u, int n_vertices)
 {
     systime++;
     vertices[u].open_time = systime;
     vertices[u].color = GRAY;           // vertex 'u' has been visited
 
     for(int v=0;v<n_vertices;v++) {
     if(graf[u*n_vertices+v] != 0) {     // explore edge (u,v)
        if(vertices[v].color == WHITE) { // still not visited
         vertices[v].parent = u;
         DFS_visit(graf, vertices, v, n_vertices);
        }
     }
     }
 
     systime++;
     vertices[u].close_time = systime;
     vertices[u].color = BLACK;          // vertex 'u' has been closed
 }
 
 int graf_calc_number_of_edges(int *graf, int size)
 {
     int edges = 0;
     for(int i=0;i<size;i++) for(int j=0;j<size;j++) {
     if(graf[i+j*size] != 0) ++edges;    // edge
     }
     return edges;
 }
 
 void graf_print(int *graf, int n_vertices)
 {
     printf("\n   ");
     for(int i=0;i<n_vertices;i++) printf("  %c", i + 'A');
     for(int i=0;i<n_vertices;i++) {
     printf("\n%c  ", i + 'A');
     for(int j=0;j<n_vertices;j++) {
        if(graf[i+j*n_vertices] == 0) printf(" --");
        else printf(" %2d", graf[i+j*n_vertices]);
     }
     }
     printf("\n");
 }
 
 void main(void)
 {
     //  A   B   C   D   E   F   // 6 vertices
     int graf[6*6] = {
     0,  1,  0,  1,  0,  0,  // A
     0,  0,  0,  0,  1,  0,  // B
     0,  0,  0,  0,  1,  1,  // C
     0,  1,  0,  0,  0,  0,  // D
     0,  0,  0,  1,  0,  0,  // E
     0,  0,  0,  0,  0,  1,  // F
     };
 
     int n_vertices = 6;
     int n_edges = graf_calc_number_of_edges(graf, n_vertices);
     vertex_info vertices[6];
 
     graf_print(graf, n_vertices);
     printf("\nVertices: %d, Edges: %d\n", n_vertices, n_edges);
 
     DFS(graf, vertices, n_vertices);       // starting ...
 
     printf("\nOpen Time : ");
     for(int i=0;i<n_vertices;i++) printf("%2d ", vertices[i].open_time);
     printf("\nClose Time: ");
     for(int i=0;i<n_vertices;i++) printf("%2d ", vertices[i].close_time);
     printf("\n");
 }
 === Cut ===
 
     E-mail: gate@fidonet.org.il
     Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)
 
 Bye !
 Stanislav     (AKA Night's Man)                        [Team Technion]
 ---
  * Origin: Gate From Another World ... From Haifa, Israel (2:400/520)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    help   Aleksey Mashihin   28 Jun 2001 22:41:36   Re: help   andyc@nikom.tagil.ru   29 Jun 2001 13:31:56   help   Stanislav Shwartsman   29 Jun 2001 13:26:57   Re: help   andyc@nikom.tagil.ru   02 Jul 2001 07:18:02   help   Stanislav Shwartsman   29 Jun 2001 13:23:48   help   Aleksey Mashihin   01 Jul 2001 01:37:10   help   Stanislav Shwartsman   02 Jul 2001 15:31:39   help   Ivan Mak   29 Jun 2001 23:38:05   help   Aleksey Mashihin   01 Jul 2001 01:41:34   help   Ivan Mak   01 Jul 2001 16:43:31