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

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

Войти
Регистрация
Восстановить пароль
 
Obsidian2010
0 / 0 / 0
Регистрация: 25.09.2012
Сообщений: 21
#1

Обход неориентированного графа в ширину. В конце выдаёт путь: 1 - C++

21.06.2013, 22:57. Просмотров 706. Ответов 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
#include <iostream>
#include <queue>
#include <conio.h>
 
using namespace std;
 int n;// число вершин графа
int mass[100][100];//матрица смежности
 
void BFS()
{
      queue<int> q;//очередь 
      int met[100];//массив меток
      q.push(0);//помещаем первую вершину в очередь
      met[0] = 1;//помечаем ее как просмотренную
 
      while (q.size() > 0)//пака не просмотрели все вершины
      {
             int u = q.front();//извлекаем из очереди вершину
            q.pop();
            cout << u+1 << " ";//выводим ее
            for (int i = 0; i < n; ++i)//цикл по всем вершинам
                  if (mass[u][i] == 1 && met[i] != 1)//если вершина
//смежна с данной и непросмотрена 
                  {
                        q.push(i);//помещаем ее в очередь
                        met[i] = 1;//помечаем
                  }
                 
      }
 
}
int main()
{
      freopen("input.txt", "r", stdin);
      cin >> n;
      for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                  cin >> mass[i][j];
      cout << "One of the ways: " << endl;
      BFS();
      _getch();
      return 0;
}
6
0 1 0 0 1 0
1 0 0 0 1 1
0 0 0 1 1 0
0 0 1 0 1 0
1 1 1 1 0 0
0 1 0 0 0 0

One of the ways: 1 2 5 6 3 4

Что в этой программе не так?(вместо 1 2 5 6 3 4 выдаёт 1)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.06.2013, 22:57
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Обход неориентированного графа в ширину. В конце выдаёт путь: 1 (C++):

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

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

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

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

2
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
22.06.2013, 02:13 #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
#include <iostream>
#include <queue>
#include <conio.h>
#include <algorithm>
 
using namespace std;
int n;
int mass[100][100];
 
void BFS()
{
    queue<int> q;
    int met[100];
    q.push(0);
    fill(met, met + 100, 0);
    met[0] = 1;
    cout << 0 << ", ";
 
    while (!q.empty()) {
        int u = q.front();
        q.pop();
 
        for (int i = 0; i < n; ++i)
            if (mass[u][i] && !met[i])
            {
                q.push(i);
                met[i] = 1;
                cout << i << ", ";
            }
    }
}
 
int main()
{
    freopen("input.txt", "r", stdin);
    cin >> n;
    for (int i = 0; i < n; ++i, cout << endl)
        for (int j = 0; j < n; ++j) {
            cin >> mass[i][j];
            cout << mass[i][j] << " ";
        }
    cout << "One of the ways: " << endl;
    BFS();
    return 0;
}
0 1 0 0 1 0
1 0 0 0 1 1
0 0 0 1 1 0
0 0 1 0 1 0
1 1 1 1 0 0
0 1 0 0 0 0
One of the ways:
0, 1, 4, 5, 2, 3,
1
MrGluck
Модератор
Эксперт CЭксперт С++
7278 / 4439 / 650
Регистрация: 29.11.2010
Сообщений: 12,018
22.06.2013, 02:21 #3
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
#include <fstream>
#include <queue>
#define N 10
using namespace std;
 
int main()
{
    ofstream o("result.txt");
    ifstream in("A.txt");
    if (!in) return 1;
    // ------------------------------инициализация------------------------------
    queue <int> q; // очередь для хранения номеров вершин
    bool visited[N]; //false - вершина не рассмотрена, true - рассмотрена
    bool inqueue[N]; //false - вершина не в очереди, true - в очереди
    bool A[N][N]; // матрица смежности
    int start = 0; // номер стартовой вершины
    int cur; // номер посещаемой вершины
    for (int i = 0; i < N; i++)
    {
        visited[i] = inqueue[i] = false;        
        for (int j = 0; j < N; j++)
            in>> A[i][j];
    }
    q.push (start); // записываем начальную вершину в очередь
    visited[start] = inqueue[start] = true;
    // --------------------------------общий шаг--------------------------------
    while (!q.empty())
    {
          cur = q.front();
          o<< cur<< " ";
          visited[cur] = true;
          q.pop();
          for (int i = 0; i < N; i++)
          {
              if (!inqueue[i] && A[cur][i])
              {
                  q.push (i);
                  inqueue[i] = true;
              }
          }
    }
    in.close();  o.close();
    return 0;
}
Добавлено через 40 секунд
N - размер матрицы смежности. Делал на втором курсе еще.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.06.2013, 02:21
Привет! Вот еще темы с ответами:

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

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

Вывести количество вершин неориентированного графа, смежных с данной - C++
Есть задание по с++ совершенно не понимаю как делать. Кому не сложно, напишите прогу: Создать граф, используя список смежности....

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


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

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

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