Форум программистов, компьютерный форум CyberForum.ru

Удаление цикла в ориентированном графе - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
22.08.2011, 15:26     Удаление цикла в ориентированном графе #1
Помогите реализовать такой вот алгоритм:
Задан ориентированный граф. Необходимо найти и удалить из него все циклы. Пример графа:
1 2
2 3
2 4
3 1
3 5
4 5
Находим циклы: {1 2 3 1} => Заменяем вершины 2 3 на 1, тем самым получаем граф:
1 1
1 1
1 4
1 1
1 5
4 5
Удаляем дубли и петли:
1 4
1 5
4 5

Реализовать то я его нормально не смог. Вот что вышло:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstdlib>
#define SIZE 100
using namespace std;
 
bool graph[SIZE][SIZE];
int cycle[SIZE];
int n,m,k=0;
 
void findcycle(int i);
int main()
{
 int i,a,b,j;
 memset(graph,false,sizeof(graph));
 cin >> n >> m;
 for (i=0; i<m; i++) cin >> a >> b, graph[a][b]=true;
 for (i=1; i<=n; i++)
  {
   k=1;
   cycle[0]=i;
   findcycle(i);
  }
 for (i=1; i<=n; i++)
 for (j=1; j<=n; j++)
  {
   if (graph[i][j]) cout << i << " " << j << endl;
  }
 return 0;
}
 
void findcycle(int i)
{
 int j,l,p,t,q;
 for (j=1; j<=n; j++)
  {
   if (graph[i][j])
    {
     cycle[k]=j;
     k++;
     for (l=0; l<k; l++)
     for (p=l+1; p<k; p++)
      {
       if (cycle[p]==cycle[l])
        {
         cout << cycle[p] << " = " << cycle[l] << endl;
         for (q=0; q<k-1; q++) cout << cycle[q] << " "; cout << cycle[k-1] << endl;
         cout << "p= " << p << endl;
         for (t=l+1; t<=p; t++)
          {
           cout << "Deleting: " << cycle[t-1] << " " << cycle[t] << endl;
           graph[cycle[t-1]][cycle[t]]=false;
           for (q=1; q<k; q++)
            {
             if (graph[cycle[t]][q])
              {
               graph[cycle[t]][q]=false;
               graph[cycle[l]][q]=true;
              }
            }
          }
         return;
        }
      }
     findcycle(j);
    }
  }
}
Помогите реализовать как то
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.08.2011, 15:26     Удаление цикла в ориентированном графе
Посмотрите здесь:

C++ Простой калькулятор в объектно-ориентированном стиле
Поиск всех контуров в ориентированном графе C++
Используя одну переменную цикла укажите возможные способы объявления заголовка счетного цикла. C++
C++ Поиск отрицательного цикла (контура) в графе
C++ Ранжирование вершин на ориентированном графе без контуров по отношению к вершине
C++ Алгоритм поиска в глубину в ориентированном графе
Std::list удаление элемента во время цикла C++
C++ Нахождение отрицательного цикла в графе и вывод цикла
C++ Удаление ребра в графе
Классы в объектно-ориентированном программировании. С++ C++
Применение цикла if для определения простых чисел. If внутри цикла for C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
-=ЮрА=-
Заблокирован
Автор FAQ
22.08.2011, 16:26     Удаление цикла в ориентированном графе #2
Вот реализация твоего алгоритма (дубли просто не вывожу, но думаю написать функцию по их удалению после того как удалили циклы - плёвое дело)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream.h>
 
void rem_circules(int n, int * left, int * right);
void repl_vershini(int n, int i, int rem1, int rem2, int repl, int * left, int * right);
 
int main()
{
    char ch;
    int i,n,*left,*right;
    do
    {
        cout<<"Vvedite chislo vetvei grapha: ";
        cin>>n;
        left  = new int[n];
        right = new int[n];
 
        cout<<"\tVvod vetvei\r\n";
        for(i = 0; i < n; i++)
        {
            cout<<"\t Vetv' ["<<i + 1<<"]\r\n";
            cout<<"left = ";cin>>left[i];
            cout<<"right= ";cin>>right[i];
        }
        cout<<"Vid grapha\r\n";
        for(i = 0; i < n; i++)
            cout<<left[i]<<" "<<right[i]<<"\r\n";
        cout<<"Rem circules\r\n";
        rem_circules(n, left, right);
        cout<<"Vid grapha\r\n";
        for(i = 0; i < n; i++)
            cout<<left[i]<<" "<<right[i]<<"\r\n";
 
        cout<<"Rem dubli\r\n";
        cout<<"Vid grapha\r\n";
        for(i = 0; i < n; i++)
        {
            if(left[i] != right[i])
                cout<<left[i]<<" "<<right[i]<<"\r\n";
        }
 
        delete [] left;
        delete [] right;
        cout<<"Y - New input\r\n";
        cin>>ch;
    }
    while(ch == 'Y' || ch == 'y');
    return 0;
}
 
void rem_circules(int n, int * left, int * right)
{
    for(int i = 0,j; i < n; i++)
    {
        for(j = i; j < n; j++)
        {
            if(
                right[i] + 1 == left[j] && 
                left[i] == right[j] && 
                left[i] != left[j])
            {
                cout<<"Circle naiden v vetvi["<<j + 1<<"]\r\n";
                repl_vershini(n, i, right[i], left[j], left[i], left, right);
                right[i] = left[i];
            }
        }
    }
}
 
void repl_vershini(int n, int i, int rem1, int rem2, int repl, int * left, int * right)
{
    for(int j = 0; j < n; j++)
    {
        if(j != i)
        {
            if(left[j] == rem1 || left[j] == rem2)
                left[j] = repl;
            if(right[j] == rem1 || right[j] == rem2)
                right[j] = repl;
        }
    }
}
[Результат работы]

Vvedite chislo vetvei grapha: 6
Vvod vetvei
Vetv' [1]
left = 1
right= 2
Vetv' [2]
left = 2
right= 3
Vetv' [3]
left = 2
right= 4
Vetv' [4]
left = 3
right= 1
Vetv' [5]
left = 3
right= 5
Vetv' [6]
left = 4
right= 5
Vid grapha
1 2
2 3
2 4
3 1
3 5
4 5
Rem circules
Circle naiden v vetvi[4]
Vid grapha
1 1
1 1
1 4
1 1
1 5
4 5
Rem dubli
Vid grapha
1 4
1 5
4 5
Y - New input
Yandex
Объявления
22.08.2011, 16:26     Удаление цикла в ориентированном графе
Ответ Создать тему
Опции темы

Текущее время: 06:12. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru