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

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

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

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

12.12.2009, 20:55. Просмотров 3070. Ответов 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 ); 
    }
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.12.2009, 20:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос обход графа в ширину! (C++):

Обход графа в ширину - C++
Как обойти граф в ширину? есть граф: int graf = { { 1, 6 },// где на каждой строке указаны смежные вершины { 2, 3 }, ...

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

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

Обход графа в ширину - 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; и т.д.

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.12.2009, 20:55
Привет! Вот еще темы с ответами:

Обход дерева в ширину - C++
Кто нибудь может скинуть мне программу обхода дерева в ширину?

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

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

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


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

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

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