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

Обход вершин графа в глубину стеком - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.83
Nkey
308 / 61 / 10
Регистрация: 21.12.2011
Сообщений: 267
05.06.2013, 07:30     Обход вершин графа в глубину стеком #1
Применить стек для обхода вершин графа, заданного с помощью матрицы смежности, в глубину.

Есть код.. Но он не совсем правильно работает.. Как вывести порядок обхода? Т.е. весь маршрут.. К примеру 2->4->3->1

stack.h:
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
#define STACK struct stack
 
STACK
{
   int info ;
   STACK *next ;
};
 
extern void push( STACK **s, int item);
extern int pop ( STACK **s);
extern int peek( STACK **s);
 
void push (STACK **s, int item)//Добавление элемента
{
   STACK *new_item; 
   new_item = (STACK *) malloc (sizeof(STACK));
   new_item -> info = item;
   new_item -> next = *s ;
   *s = new_item;
}
 
int pop (STACK **s)//Удаление элемента
{
   int error;
   STACK *old_item = *s;
   int old_info = 0;
   if ( *s )
   {
      old_info = old_item -> info;
      *s = ( *s ) -> next;
      free (old_item );
      error = 0;
   }
   else error = 1;
   return ( old_info );
}
int take_out (STACK **s, int *error)
{
   STACK *old_item = *s ;//начало очереди
   int old_info = 0 ;
   if (*s)//если очередь не пуста
   {
      old_info = old_item -> info;
      *s = ( *s ) -> next;
      free (old_item );//уничтожение элемента
      *error = 0;
   } else *error = 1;
   return (old_info);
}
 
 
int peek (STACK **s)//Чтение элемента 
{
   int error;
   if (*s)
   {
      error = 0; return (*s) -> info;
   }
   else
   {
      error = 1; return 0;
   }
}
void show_stack(stack *s)//Печать стека
{
   printf("\n");
   if (s)
   {
      printf(" %d ", s->info); show_stack(s->next);
   }
}
 
int isempty( STACK **s)
{
   if (*s) return 0;//если непусто
   else return 1;
}
исходник:
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 "stdafx.h"
#include <iostream>
#include <math.h>
#include "stack.h"
 
int i,j,z,x,m;
int p=0;
int b[8];
int k=0;
int c[8];
int n=8;                  // номера предшествующих вершин
int a[8][8]={ 
          0,1,1,0,0,0,0,0, // матрица смежности
          1,0,0,0,0,0,1,0,
          1,0,0,1,0,0,0,0,
          0,0,1,0,1,1,0,0,
          0,0,0,1,0,0,1,1,
          0,0,0,1,0,0,1,0,
          0,1,0,0,1,1,0,0,
          0,0,0,0,1,0,0,0 };
 
int main()
{
    setlocale(LC_ALL,"");
    /*STACK *s1 = 0, *s2 = 0;
    int *error;
    push (&s1, p);//добавить
    printf("Добавили в стек %d", p);
    printf("\nУдалили из стека %d", pop (&s1));
    for (i=0; i<n; i++)
    {
        for (p=0; p<n; p++)
        {
            if (a[i][p]==1)//если ячейка матрицы = 1
            {
                push (&s1, p);//добавить
                printf("\nДобавили в стек %d", p);
            }
        }
        printf("\nУдалили из стека %d", pop (&s1));
    }
    getchar();*/
 
    return 0;
}
Добавлено через 18 часов 29 минут
Проблема актуальна
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.06.2013, 07:30     Обход вершин графа в глубину стеком
Посмотрите здесь:

Обход графа в глубину C++
Обход в ширину графа C++
C++ Хитрый обход дерева в глубину
C++ Организовать обход в глубину
Компоненты связности графа поиском в глубину C++
Обход графа в ширину C++
C++ Матрица смежности графа - поиск в глубину
Обход неориентированного графа в глубину C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,419
05.06.2013, 07:40     Обход вершин графа в глубину стеком #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
#include <fstream>
#include <stack>
#include <vector>
#include <iostream>
#include <clocale>
#define N 10
using namespace std;
 
void designing(int* , int, int, ofstream&); // конструирование маршрута
 
int main()
{
    setlocale(LC_ALL, "Russian");
    ofstream o("result.txt");
    ifstream in("A.txt");
    if (!in) return 1;
    // ------------------------------инициализация------------------------------
    stack <int> st; // стек для хранения номеров вершин
    bool instack[N]; //false - вершина не в стеке, true - в стеке
    bool DUG[N][N]; // матрица смежности
    int start, end; // номер стартовой и конечной вершин
    int rang[N]; // длина пути
    int VON_PUNKT[N]; // номер вершины, из которой попали в текущую
    cout<< "Введите начальную вершину: ";
    do{ cin>> start;} while (start < 0 || start > 9);
    cout<< "Введите конечную вершину: ";
    do{ cin>> end;} while (end < 0 || end > 9 || end == start);
    for (int i = 0; i < N; i++)
    {
        VON_PUNKT[i] = start;
        rang[i] = 999;
        instack[i] = false;
        for (int j = 0; j < N; j++)
            in>> DUG[i][j];
    }
    // записываем начальную вершину в очередь
    st.push (start);
    instack[start] = true;
    VON_PUNKT[start] = -1;
    rang[start] = 0;
    // --------------------------------общий шаг--------------------------------
    while (!st.empty())
    {
          int besuch = st.top();
          st.pop();
          for (int i = 0; i < N; i++)
          {
              if (!instack[i] && DUG[besuch][i])
              {
                  st.push (i);
                  instack[i] = true;
                  rang[i] = rang[besuch] + 1;
                  VON_PUNKT[i] = besuch;
              }
          }
    }
    // --------------------------запись пути в файл ----------------------------
    designing(VON_PUNKT, rang[end], end, o);
    in.close();  o.close();
    return 0;
}
 
void designing(int *p, int rang, int end, ofstream &o)
{
    vector <int> v;
    vector <int>::iterator cur;
    for (int i = end; i != -1; i = p[i])
        v.push_back(i);
    o<< "Количество переходов: "<< rang<< endl;
    for (cur = v.end() - 1; cur >= v.begin(); cur--)
        o<< *cur<< " ";
}
Матрица смежности:
Код
0 0 0 1 0 1 0 0 0 0
0 0 1 0 1 0 0 0 0 0
0 1 0 0 0 0 1 0 1 0
1 0 0 0 0 1 0 1 0 0
0 1 0 0 0 1 1 0 0 0
1 0 0 1 1 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 1 0
Nkey
308 / 61 / 10
Регистрация: 21.12.2011
Сообщений: 267
05.06.2013, 11:57  [ТС]     Обход вершин графа в глубину стеком #3
MrGluck, спасибо... работает! завтра пойду сдавать)
Yandex
Объявления
05.06.2013, 11:57     Обход вершин графа в глубину стеком
Ответ Создать тему
Опции темы

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