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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
#1

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

22.08.2011, 15:26. Просмотров 1200. Ответов 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++
Нужно найти все контуры. Контур - путь, у которого начало и конец совпадают. Т.е. например (1;5)(5;2)(2;4)(4;1). Имею вектор с...

Класс для поиска простых контуров на ориентированном графе - C++
Ребят, помогите прогу написать :gsorry: завтра сдавать, а я не знаю ничего совсем :gsorry::gcray: Класс для поиска простых контуров на...

Ранжирование вершин на ориентированном графе без контуров по отношению к вершине - C++
Помогите сделать алгоритм по данному коду. Задание: Написать и исследовать программу, осуществляющюю ранжирование вершин на ориентированном...

Используя метод поиска в ширину, найти и вывести путь в ориентированном графе между двумя вершинами - 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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.08.2011, 16:26
Привет! Вот еще темы с ответами:

Нахождение отрицательного цикла в графе и вывод цикла - C++
Вот программа по нахождению отрицательного цикла в графе и вывод цикла void Floyd(int GR, int parents , int V) { int checking; int...

Поиск отрицательного цикла (контура) в графе - C++
Всем привет! Помоги пожалуйста с программой! :-mass), затем я её модифицирую: for (int i = 0; i &lt; n; ++i) for (int j = 0; j &lt;...

Удаление ребра в графе - C++
Здравствуйте.У меня есть граф который представлен в файле матрицей смежности, загружаю в двумерный массив. Получается делать по нему обход...

Std::list удаление элемента во время цикла - C++
Добрый вечер, Как бы удалить элеммент без &quot;сбора итераторов&quot;. #include &lt;iostream&gt; #include &lt;list&gt; using namespace std; static...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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