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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.92
КсенияСергеевна
0 / 0 / 0
Регистрация: 07.09.2009
Сообщений: 45
#1

обход графа в ширину! - C++

12.12.2009, 20:55. Просмотров 3064. Ответов 0
Метки нет (Все метки)

Здравствуйте!!
вот задание: "Задано прямоугольное клеточное поле и число k. Построить k различных непрерывных разрезов этого поля на два клеточных поля равной площади. "
мне препод примерно сказал как делать(обход графа в ширину,но соответственно не полного графа,а относительно моей задачи)
я написала код,по примеру, не особо разобралась!
помогите пожалуйста исправить ошибки!
и там не правильно rand написан,исправьте,пожалуйста!!

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
# include "stdafx.h"
# include <stdio.h> 
# include <alloc.h> 
# define SI sizeof (int)                       //элемент структуры смежности графа 
 
 
struct VER { int kol; int mv; int *adj; };     //число вершин
int n, h; 
struct VER *Vt;  
File *p, *f;  
 
 
 
 
 void vvod_graf ( ) 
 { 
 int i, j, N, kol; 
 p = fopen( "spisok_Adj.in", "r" );            
 if (fscanf (p, "%d", &n ) != EOF)             
 {
     h=n/2;
     Vt = (struct VER *) calloc (n, SI);       //выделение памяти основным элементам
     for ( i = 0; i < n; i++)                  //ввод метки вершины графа
     {  
         fscanf (p, "%d", &Vt [i] . mv ); 
         fscanf (p, "%d", &Vt [i] . kol ); 
         kol = Vt [i].kol;                      
         Vt [i] . adj = (int*) calloc (kol, SI); //выделение памяти списку смежности
 
         if (kol)
         { 
             for ( j = 0; j < kol; j++ )
             { 
                 fscanf (p, "%d", &N ); Vt [i]. adj [j] = N – 1; 
             } 
         } 
     } 
 } 
 fclose ( p ); 
 } 
 
 
 
 
  void Proverka ( int u ) 
  { 
      int i, v, flag = 1,l=0;
      Mark [u] = 2; 
      
      while (flag)
      {  
          for (i = 0; i < Vt [u ] . kol; i++)
          {  
              v = Vt [u ] . adj[i]; 
              
              if (Mark [v] = = 1)
              {
                  Mark [v] = 2;
                  l++;
              }
              else if (! Mark [v] ) 
                  Mark [v] = 1;
          }  
          
          for (i = 0; i < n && Mark [i] != 1; i++) ; 
          
          if (i == n)
              flag = 0; 
          else
          {
              u = i; 
              Mark [u] = 2;
          }
          
          if (l>=h) 
              flag = 0;
      } 
  }
 
 
 
void main ( void )
{ 
    int i, j, s, k, flag; 
    
    vvod_graf ( );
    Mark = (int*) calloc ( n, SI );         //выделение памяти под массив меток
    
    for ( i = 0; i < n; i++) 
        Mark [i] = 0;  
    
    printf ("\n Задайте K"); 
    scanf ( "%d", &k );
    
    for(j=0;j<=k;j++)
    { 
        s=rand(1,k);
        s --; 
        
        proverka ( s );                     // вывод результатов 
        
        f = fopen( "spisok.out", "w" ); 
        printf (f, "%d ", s+1 ); 
        printf (f, "\n" ); 
        
        for ( i = 0; i < n; i++ ) 
        { 
            if (i != s && ! Mark [i] ) 
                printf (f, "%d ", Vt [ i ] . mv); 
        } 
 
        printf (f, "\n"); 
        fclose ( f ); 
    }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.12.2009, 20:55     обход графа в ширину!
Посмотрите здесь:

Обход графа в ширину - Breadth First Search (BFS) - C++
Всем привет! Я не понимаю алгоритм обхода в глубину BFS:( Кто может помощь?

Обход неориентированного графа в ширину. В конце выдаёт путь: 1 - C++
#include &lt;iostream&gt; #include &lt;queue&gt; #include &lt;conio.h&gt; using namespace std; int n;// число вершин графа int mass;//матрица...

Обход в ширину - C++
Помогите написать обход в ширину на C++ без библиотек &lt;vector&gt; и т.д.

Обход дерева в ширину - C++
имеется такой кусок программы. требуется обойти дерево в ширину. библиотека #include &lt;queue&gt; подключена void...

Дерево поиска. Обход в ширину. - C++
Организовать двоичное дерево поиска, состоящее из целых чисел. Вывести содержимое его узлов, обходя это дерево в ширину.

Обход графа в глубину - C++
Покажите кто-нибудь как работает &quot;обход графа&quot; в графе в консоле А именно вывод глубины графа,сколько ребер обошел ,где был уже... ...

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

Обход графа и вывод пути - C++
#include &quot;stdafx.h&quot; #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; #include&lt;vector&gt; #include&lt;queue&gt; using namespace...

Обход всех вершин графа - C++
Нужно найти путь с наименьшим весом с вершины 0 в 0, 1 в 1 и т.д. Обязательно обойти каждую вершину не более 1 раза. Граф взвешенный. ...

Обход неориентированного графа в глубину - C++
#include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;vector&gt; #include &lt;conio.h&gt; #include &lt;locale.h&gt; using namespace std; int...

Многопоточный обход графа в глубину - C++
Доброго времени суток. Подскажите многопоточный алгоритм обхода графа в глубину (нужно распараллелить алгоритм поиска компонент связности)....

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


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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