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

Граф - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.94
nas
0 / 0 / 0
Регистрация: 10.11.2010
Сообщений: 26
13.03.2011, 18:22     Граф #1
Найти все вершины неориентированного графа, к которым существует путь заданной длины от выделенной его вершины.
не могу разобраться, здесь нужно применять алгоритм Уоршалла или этот алгоритм только для орграфов? Заранее благодарю
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.03.2011, 18:22     Граф
Посмотрите здесь:

C++ Граф
Граф C++
Считать граф из файла (граф задан матрицей) представить его в виде списка и записать список заново в файл C++
Граф C++
C++ Граф в С
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
13.03.2011, 18:26     Граф #2
nas, Если нужен алгоритм Уоршалла, его реализация на С++ есть здесь.
nas
0 / 0 / 0
Регистрация: 10.11.2010
Сообщений: 26
14.03.2011, 17:37  [ТС]     Граф #3
спасибо, он у меня есть, но не знаю как его применить и можно ли вообще его применять для неорграфов?

Добавлено через 23 часа 4 минуты
Вообще не могу разобраться с представлением графа матрицей. Как описать массив если заранее не известно сколько будет вершин в графе. Как составить матрицу достижимости и т. д. В общем помогите пожалуйста.
Ma3a
Эксперт C++
612 / 456 / 31
Регистрация: 28.01.2011
Сообщений: 605
14.03.2011, 17:46     Граф #4
Так сделай граф например через списки смежности, то бишь хранишь список из вершин для каждой из которых есть список смежных с ней вершин.
Что-то вроде
C++
1
2
typedef std::pair<int,std::vector<int> > adjacency_list_t;
typedef std::vector< adjacency_list > graph_t;
std::vector - динамический массив, так что по поводу того, что неизвестно, сколько будет вершин заранее, можно не волноваться, размер изменять можно.
nas
0 / 0 / 0
Регистрация: 10.11.2010
Сообщений: 26
15.03.2011, 14:35  [ТС]     Граф #5
Нет, по задаче нужно представление с помощью матриц...
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
15.03.2011, 14:44     Граф #6
nas, Ну посмотри код в той теме, которую тебе посоветовали... Там ведь все это строится... И именно через матрицы...
nas
0 / 0 / 0
Регистрация: 10.11.2010
Сообщений: 26
15.03.2011, 15:38  [ТС]     Граф #7
не получается написать функцию возведения матрицы смежности в степень
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
15.03.2011, 19:31     Граф #8
нет, нужно применить алгоритм Дейкстры с начальной вершины, а затем сравнить значения в каждой вершине со значением заданой длинны

Добавлено через 43 минуты
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
#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
 
int main()
{
   std::locale::global(std::locale(""));
   std::cout << "Введите начальную вершину: " << std::endl;
   int start;
   std::cin  >> start;
   std::cout << "Введите количeство вершин: " << std::endl;
   int n;
   std::cin  >> n;
   int length;
   std::cout << "Введите нужную длинну пути: " << std::endl;
   std::cin  >> length;
   std::cout << "Введите матрицу размером "  
             << n << "x" << n << ":" 
             << std::endl;
   std::vector <std::vector <int> > g(n, std::vector<int>(n, 0));
   for (size_t i = 0; i < n; i++)
      for (size_t j = 0; j < n; j++)
            std::cin >> g[i][j];
   
   const int infinity = std::numeric_limits<int>::max();
   std::vector <int>  d(n, infinity);
   d[start-1] = 0;
   std::queue <int> bfs;
   bfs.push(start-1);
   while (!bfs.empty())
   {
      int now = bfs.front();
      bfs.pop();
      for (size_t i = 0; i < n; i++)
            if (g[now][i] != 0 && d[now] + g[now][i] < d[i])
            {
                        d[i] = d[now] + g[now][i];
                        bfs.push(i);
            }
   }
   std::cout << "Следующие вершины расположеные за " 
             << length 
             << "\nот вершины " 
             << start << ":"
             << std::endl;
 
   for (size_t i = 0; i < n; i++)
      if (d[i] == length) 
            std::cout << i+1 << " ";
   std::cout << std::endl;
 
   return 0;
}
вот код, который подходит как для неориентированого графа так и для орграфа.
Граф задает матрица, путь находит алгоритм Дейкстры через явно заданую очередь


Добавлено через 46 минут
nas, все так как нужно?
Может что-то переделать, чем-то помочь?
nas
0 / 0 / 0
Регистрация: 10.11.2010
Сообщений: 26
15.03.2011, 19:47  [ТС]     Граф #9
в нашем пособии написано, что можно найти число путей длины n из i-ой вершины в j-ую , используя арифметические операции над матрицами, а именно:путем вычисления степеней матрицы смежности. И я пыталась именно этим способом, ничего не получилось...только матрицу достижимости составила, в общем, если вы меня поняли
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
15.03.2011, 19:59     Граф #10
Цитата Сообщение от nas Посмотреть сообщение
если вы меня поняли
ок, понял, сейчас набросаю код...

Добавлено через 5 минут
Цитата Сообщение от nas Посмотреть сообщение
длины n
если имеется ввиду число ребер, то подходит описаный вами метод, а если имеется ввиду сума весов ребер, по которым проходим, то код, который я написал.
Так нужно первое?
nas
0 / 0 / 0
Регистрация: 10.11.2010
Сообщений: 26
16.03.2011, 14:23  [ТС]     Граф #11
нужно длины n
задача:
найти все вершины неориентированного графа, к которым существует путь заданной длины от выделенной его вершины

Добавлено через 18 часов 11 минут
В смысле число ребер
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.03.2011, 15:05     Граф
Еще ссылки по теме:

Граф C++
Двудольный граф C++
Граф C++

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

Или воспользуйтесь поиском по форуму:
nas
0 / 0 / 0
Регистрация: 10.11.2010
Сообщений: 26
20.03.2011, 15:05  [ТС]     Граф #12
выкладываю решение задачи, может кому приготится)
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
#include <iostream.h>
 
 
class Graph
{
 private:
  int **a;
 
 public:
  void vvod(int);
  void vyvod(int);
  void reshen(int,int,int);
  void delet(int);
};
 
void Graph::vvod(int n)
{
  a= new int *[n];
  for (int i=0; i<n; i++)
    a[i] = new int [n];
  cout<<"Ââîäèòå ýëåìåГ*ГІГ» Г¬Г*òðèöû ñìåæГ*îñòè ГЇГ® ñòðîêГ*Г¬: \n";
  for (i=0; i<n; i++)
    {
     for (int j=0; j<n; j++)
      {if (i>j) continue;
        cout <<"a["<<i+1<<"] ["<<j+1<<"] =";
        cin >>a[i][j];
        if (i!=j) a[j][i]=a[i][j];
      }
    }
}
 
void Graph::vyvod(int n)
{
 cout<<"Г¬Г*òðèöГ* ñìåæГ*îñòè: \n";
 for (int i=0; i<n; i++)
    {
     for (int j=0; j<n; j++)
      cout <<a[i][j]<<" ";
     cout<<"\n";
    }
}
 
 
void Graph::reshen(int n, int r,int v)
{int u=0;int **b;int **res;
 b= new int *[n];
 for (int i=0; i<n; i++)
    b[i] = new int [n];
 res= new int *[n];
 for ( i=0; i<n; i++)
    res[i] = new int [n];
 for (i=0;i<n;i++)
    for (int j=0;j<n;j++)
     b[i][j] = a[i][j];
 int m=1;
  while (m<r)
  {
    for ( i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
      {int Sum = 0;
      for (int k = 0; k <n; k++)
        Sum += b[i][k]*a[k][j];
      res[i][j] = Sum;}
  for (i=0;i<n;i++)
    for (int j=0;j<n;j++)
     b[i][j] = res[i][j];
    m++;
  }
 cout<<"âåðøèГ*Г»: \n";
 for (i=0; i<n; i++)
    if ((i+1)==v) for (int j=0; j<n; j++)
                         if ((b[i][j]>0)&&(i!=j)) {cout <<(j+1)<<" ";u=1;}
 if (!u) cout<<"ГІГ*ГЄГЁГµ âåðøèГ* Г*ГҐГІ";
  for ( i = 0; i <n; i++)
      delete b[i];
  delete[] b;
    for ( i = 0; i <n; i++)
      delete res[i];
  delete[] res;
}
 
void Graph::delet(int n)
{
  for (int i = 0; i <n; i++)
      delete a[i];
  delete[] a;
}
 
void main()
{Graph A;
 int n,r,v;
 cout<<"÷èñëî âåðøèГ*: ";
 cin>>n;
 A.vvod(n);
 A.vyvod(n);
 cout<<"Ââåäèòå âåðøèГ*Гі: ";
 cin>>v;
 if (v<=n)
 {cout<<"ââåäèòå äëèГ*Гі ГЇГіГІГЁ: \n";
 cin>>r;
 A.reshen(n,r,v);
 }else cout<<"ГІГ*êîé âåðøèГ*Г» Г*ГҐГІ ";
 A.delet(n);
}
Yandex
Объявления
20.03.2011, 15:05     Граф
Ответ Создать тему
Опции темы

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