2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Алгоритм поиск компонент сильной связности
Сообщение30.10.2014, 14:37 


20/10/12
235
Добрый день, уважаемые участники форума!
Помогите определить неточность в алгоритме Косарайю.
На всех тестах, что я выдумываю - он рабочий, но точно известно, что это не так.
Намекните хотя бы на граф, на котором алгоритм свалится.

код: [ скачать ] [ спрятать ]
Используется синтаксис C++
//здесь мы обходим вершины транспонированного графа и добавляем их в стек по порядку обработки

Stack dfs(Queue *Gt, int n)
{
        int i, v, flag;
        int *visited = (int *)malloc(n * sizeof(int));
        Stack MyStack, order;
        Node *p;

        MyStack.head = NULL;
        order.head = NULL;

        for( i = 0; i < n; ++i ) visited[i] = 0;

         for(v = 0; v < n; ++v)
        {
         if(!visited[v])
         {
           push(v, &MyStack);
           while(!is_empty_stack(&MyStack))
           {
                    v = top(&MyStack);
                p = Gt[v].exclude;
                       
                        for(flag = 1; p != NULL; p = p->next)
              if(!visited[p->vnum])
                          {
                             flag = 0;
                             push(p->vnum, &MyStack);
                          }

                visited[v] = 1;
                        if(flag)
                   push(pop(&MyStack), &order);                                    
            }
         }
        }
        del_stack(&MyStack);
        free(visited);

        return order;
}

//обход, но уже в порядке обхода - т.е. по компонентам
int compounds(Queue *G, int n, Stack S)
{
        int i, v, flag, ret = 0;
        int *visited = (int *)malloc(n * sizeof(int));
        Stack MyStack;
        Node *p;

        assert(visited);

        MyStack.head = NULL;

        for( i = 0; i < n; ++i ) visited[i] = 0;

    while(!is_empty_stack(&S))
   {
     v = pop( &S );

     if(!visited[v])
         {
           ret++;
           push(v, &MyStack);

           while(!is_empty_stack(&MyStack))
           {
                    v = top(&MyStack);         
                p = G[v].exclude;

                for(flag = 1; p != NULL; p = p->next)
                  if(!visited[p->vnum])
                          {
                             flag = 0;
                             push(p->vnum, &MyStack);
                          }
             
            visited[v] = 1;
                        if(flag)
               pop(&MyStack);
            }
         }
        }

    del_stack(&MyStack);
    del_stack(&S);
    free(visited);     
    return ret;
}
 

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group