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

Алгоритм и представления матрицы смежности - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.81
zmei89
31 / 6 / 1
Регистрация: 10.09.2010
Сообщений: 824
16.12.2011, 22:20     Алгоритм и представления матрицы смежности #1
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
46
47
48
49
int main ()
{
        vector < vector<int> > g; // граф
        const int n = 4; // число вершин
        int s = 0; // стартовая вершина (вершины везде нумеруются с нуля)
         // чтение графа
        int Adj[n][n]={ {0,0,1,0},
        {0,0,1,0},
        {0,0,0,1},
        {0,2,0,0} }; 
        for (int i = 0; i<n; i++)
        {
                g.push_back(vector<int>());
                for(int j = 0; j<n; j++)
                {
                                        if(Adj[i][j])
                                                g[i].push_back(j);
                        /*g[i].push_back(0);
                        g[i][j]=Adj[i][j];*/
                }
        }
        queue<int> q;
        q.push (s);
        vector<bool> used (n);
        vector<int> d (n), p (n);
            used[s] = true;
        p[s] = -1;
        while (!q.empty()) {
                int v = q.front();
                q.pop();
                for (size_t i=0; i<g[v].size(); ++i) 
                {
                        int to = g[v][i];
                        if (!used[to]) 
                        {
                                used[to] = true;
                                q.push (to);
                                d[to] = d[v] + 1;
                                p[to] = v;
                        }
                }
        }
        for (int i = 0; i<n; i++)
                cout << d[i] << "  ";
        
        cout << endl;
        system("pause");
        return 0;
}
так идем дальше в интернете нашел пример Списки смежных вершин чтоб добавить в задачу смежные вершины

Данный метод хранения графа наиболее часто используется при решении задач с большими ограничениями по памяти и по времени (например, 2 сек и 64 Мбайт памяти на ограничения V< 10000, E < 1000 – случай разреженного графа). Его суть заключается в том, чтобы для каждой вершины Т хранить номера вершин, в которые можно попасть из Т, и вес соответствующих ребер (дуг). Для этого необходимо реализовать такую структуру данных, как список. В языках высокого уровня, таких, как С++ и Java, они уже реализованы. Далее нужно реализовать структуру данных (struct в C++ и record в Pascal) – запись с полями «вершина» и «вес». После этого заводим массив списков с V ячейками (количество вершин) и к каждой ячейке «привязываем» список созданного нами типа (структуры).

Приведем листинг на языке С++:
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
// ...
#include <list>
// ...
// ...
 
struct ToLength
{
      int to;     //номер вершины
      int length;//вес ребра
 
      ToLength() //пример первичной инициализации (зависит от постановки задачи)
      {
            to = -1;
            length = 0;
      }
      ToLength(int t, int l)  // инициализация входными числами
      {
            to = t;
            length = l;
      }
};
 
int main()
{
      // ...
list<ToLength> mass[v];
      // ...
      return 0;
}
Задача 2 Реализовать алгоритм поиска кратчайшего пути. Алгоритм Дейкстры. Представление графа – матрица смежности.


Но нужно подправить под заданиче


Данная программа выполняет поиск по заданной матрице весов. Далее указываем начальную точку в графе и программа расчитывает все кратчайшие растояния от начальной точки до остальных следующим видом:путь от нач. точки до n-ой: - n-ая промежуточная промежуточная... начальная, вес пути - х
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
116
117
118
119
120
#include <iostream.h>
#include <conio.h>
#include <windows.h>
#include<iomanip.h>
        
char NEWT[256];
char*RUS(char*TEXT) {
CharToOem(TEXT,NEWT);
return NEWT;}
 
int v;
int main()
{       int i,j;
   int infinity=1000;                     // Бесконечность
                                                                                  // Количество вершин в графе
   int VES[100][100];                                             // Матрица весов графа
 
   int x[100];                                                    //Массив, содержащий единицы и нули для каждой вершины,
                                                                                  // x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
                                                                                  // x[i]=1 - кратчайший путь в i-ю вершину уже найден
   
   int DlinaPuti[100];                                    //t[i] - длина кратчайшего пути от вершины s в i
 
   int PredVertex[100];                                   //h[i] - вершина, предшествующая i-й вершине
                                                                                  //на кратчайшем пути
   int VERTEX;
   int p;                         
cout<<RUS("Ввести количество вершин в графе ")<<endl;
cin>>VERTEX;p= VERTEX;                                    //Число вершин в графе
cout<<RUS("Заполните матрицу весов графа ")<<endl;      // Матрица весов графа
cout<<setw(4);
for (i=0;i<VERTEX;i++)
cout<<RUS("|x")<<i+1;
cout<<endl;
 
for(i=0;i<VERTEX;i++)
{cout<<RUS("X")<<i+1<<'|';
for(j=0;j<VERTEX;j++)
cin>>VES[i][j];}
 
                                                                                // Будем искать путь из вершины s в вершину g по циклу
   int start;                                           // Номер исходной вершины
   int end;                                             // Номер конечной вершины
N: cout<<RUS("Введите стартовую вершину: ");    // Номер может изменяться от 0 до p-1
   cin>>start;
   if (start>(p-1) && start<0) {cout<<RUS("Нет такой вершины повторите ввод...")<<endl; goto N; } // на случай неверных данных
   start=start-1;                                               //так как массив начинается с 0 отнимаем от вводимой цифры 1
   for (int prosto=0;prosto<VERTEX;prosto++)
   {end=prosto;                                                 //цикл прогоняет алгоритм Флойда p-ое количество раз преврашая его в алгоритм Дейкстры  
   if (end==start) continue;                    //исключаем просчет растояния между одной и той же точкой
   else
   {
 
                                                                                 // Инициализируем начальные значения массивов
   int u;                                                                // Счетчик вершин
   for (u=0;u<p;u++)
   {
       DlinaPuti[u]=infinity;                                    //Сначала все кратчайшие пути из s в i 
                                                                                 //равны бесконечности
      x[u]=0;                                                    // и нет кратчайшего пути ни для одной вершины
   }
   PredVertex[start]=0;                                         // s - начало пути, поэтому этой вершине ничего не предшествует
   DlinaPuti[start]=0;                                          // Кратчайший путь из s в s равен 0
   x[start]=1;                                                          // Для вершины s найден кратчайший путь
   v=start;                                                                     // Делаем s текущей вершиной
   
   while(1)
   {
                                                                                // Перебираем все вершины, смежные v, и ищем для них кратчайший путь
      for(u=0;u<p;u++)
      {
         if(VES[v][u]==0)continue;              // Вершины u и v несмежные
         if(x[u]==0 && DlinaPuti[u]>DlinaPuti[v]+VES[v][u]) //Если для вершины 'u' еще не 
                                                                                //найден кратчайший путь
                                                                // и новый путь в 'u' короче чем 
                                                                                //старый, то
         {
            DlinaPuti[u]=DlinaPuti[v]+VES[v][u];                        //запоминаем более короткую длину пути в
                                                                                //массив t[и]
           PredVertex[u]=v;                                             //запоминаем, что v->u часть кратчайшего 
                                                                                //пути из s->u
         }
      }
 
                                                                                 // Ищем из всех длин некратчайших путей самый короткий
      int w=infinity;                                   // Для поиска самого короткого пути
      v=-1;                                                             // В конце поиска v - вершина, в которую будет 
                                                                                // найден новый кратчайший путь. Она станет 
                                                                                // текущей вершиной
      for(u=0;u<p;u++)                                  // Перебираем все вершины.
      {
         if(x[u]==0 && DlinaPuti[u]<w)                   // Если для вершины не найден кратчайший 
                                                                                 // путь и если длина пути в вершину 'u' меньше
                                                                                 // уже найденной, то
         {
            v=u;                                                 // текущей вершиной становится 'u'-я вершина
            w= DlinaPuti[u];
         }
      }
      if(v==-1)
      {
         cout<<RUS("Нет пути из вершины ")<<start+1;cout<<RUS(" в вершину ")<<end+1<<"."<<endl;
         break;
      }
      if(v==end)                                                        // Найден кратчайший путь,
      {                                                             // выводим его
         cout<<RUS("Кратчайший путь из вершины ")<<start+1;cout<<RUS(" в вершину ")<<end+1<<":";
           u=end;
           while(u!=start)
         {
            cout<<" "<<u+1;
            u=PredVertex[u];
         }
         cout<<" "<<start+1<<RUS(". Длина пути - ")<< DlinaPuti[end];cout<<endl;
           break;
      }
      x[v]=1;
   }}}
   
return 0;}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.12.2011, 22:20     Алгоритм и представления матрицы смежности
Посмотрите здесь:

Генерация матрицы смежности C++
C++ Определение матрицы смежности графа по заданной матрице инцидентности
Как из матрицы смежности получить матрицу инцидентности? C++
C++ Матрицы инцидентнности и смежности
C++ Построение матрицы смежности
C++ Граф в виде матрицы смежности и количества вершин
C++ Алгоритм Дейкстры для матрицы смежности А размером NxN, нарисовать блок-схему по коду
C++ Из матрицы смежности сделать ориентированный граф

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

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

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