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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 52, средняя оценка - 4.88
Kill100
410 / 276 / 37
Регистрация: 11.12.2010
Сообщений: 1,168
Завершенные тесты: 1
#1

[C++] графы - C++

22.03.2011, 18:51. Просмотров 7726. Ответов 4
Метки нет (Все метки)

[C++]Алгоритм фронт фолны в графе
Помогите..
Дана матрица Ag (Матрица смежности графа)
И координаты начальной вершины i,j
и кординаты конечной i1,j1
Найти кротчайший путь из i,j в i1,j1 и вывести его на экран..
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.03.2011, 18:51
Здравствуйте! Я подобрал для вас темы с ответами на вопрос [C++] графы (C++):

Графы - C++
помогите с реализацией алгоритма Дейкстры для нахождения расстояния от узла 1 в каждый узел. матрица весов такая...

Графы - C++
Написать программу, реализующую алгоритм Беллмана-Форда.

Графы - C++
Прочитал про обход графа в глубину, посмотрел реализацию, и тут вопрос а как можно использовать этот обход в глубину?

Графы - C++
1) Построить граф, используя язык С++ (или Си), согласно данной схеме на рис.1. 2) По запросу пользователя должны удаляться: • все...

Графы - C++
Помогите написать программу: Модель работы некоторой системы представлена ориентированным графом, где вершины – это состояния системы,...

Графы - C++
Граф задан своей матрицей смежностей. Вывести на экран все связные вершины...очень скоро нужно...извините за срочность

4
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
22.03.2011, 19:29 #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
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
 
using namespace std;
 
const int infinity = numeric_limits <int>::max();
 
typedef vector <int> vi;
typedef vector <vector <int> > vvi;
 
int main()
{
    locale::global(locale(""));
    cout << "Введите количество вершин" << endl;
    int n;
    cin >> n;
    vvi v (n, vi(n, 0)); //матрица смежности
    cout << "Введите матрицу" << endl;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> v[i][j];
    
    int start;
    int finish;
    cout << "Введите начальную вершину" << endl;
    cin  >> start;
    cout << "Введите конечную вершину" << endl;
    cin  >> finish;
 
    vi d(n, infinity);   //массив длин
    d[start-1] = 0;
 
    queue <int> q;
    q.push(start-1);
 
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (int i = 0; i < n; i++)
            if (v[now][i] != 0 && d[now] + v[now][i] < d[i])
            {
                d[i] = d[now] + v[now][i];
                q.push(i);
            }
    }
 
    cout << "Длинна кротчайшого пути равна "
         << d[finish-1] << endl;
    return 0;
}
волновой алгоритм
0
Kill100
410 / 276 / 37
Регистрация: 11.12.2010
Сообщений: 1,168
Завершенные тесты: 1
22.03.2011, 19:42  [ТС] #3
Цитата Сообщение от Mayonez Посмотреть сообщение
C++
1
2
3
4
    cout << "Введите начальную вершину" << endl;
    cin  >> start;
    cout << "Введите конечную вершину" << endl;
    cin  >> finish;
волновой алгоритм
как вершина может быть задана 1 цифрой??
или я что то не до понмаю???
0
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
22.03.2011, 19:56 #4
в моем понимании граф - это
[C++] графы
вершины - кружочки с номерами

матрица смежности для него
0 1 8 6 3
1 0 7 5 2
8 7 0 11 7
6 5 11 0 5
3 2 7 5 0
0
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
22.03.2011, 19:58 #5
Цитата Сообщение от Kill100 Посмотреть сообщение
как вершина может быть задана 1 цифрой??
так как в кружочках одна цифра, а кружочки - это вершины, значит вершину графа можно задать одной цифрой, К.О.
0
22.03.2011, 19:58
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.03.2011, 19:58
Привет! Вот еще темы с ответами:

Графы - C++
Имеется сеть автомобильных дорог. Известны расстояния всех участков дорог. Некоторые участки аварийноопасны. Требуется найти путь из пункта...

Графы - C++
Люди скиньте пожалуйста какую нибудь программку на С++ по графам, или дайте ссылку на темку на форему...

Графы - C++
Помогите пожалуйста решить одну задачку. Буду очень благодарен! Спасибо заранее, огромное! Задана строка s. За один ход можно поменять...

Графы - C++
Дано прямоугольное клеточное поле; как создать матрицу смежности для графа ферзей?


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

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

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