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

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

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

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

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

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

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

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

С++ и графы - C++
Доброго времени суток. Хотел бы попросить помощи в написании программы. Нужно создать программу которая будет проводить расчет сетевого...

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
22.03.2011, 19:29     [C++] графы #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;
}
волновой алгоритм
Kill100
401 / 267 / 37
Регистрация: 11.12.2010
Сообщений: 1,134
Завершенные тесты: 1
22.03.2011, 19:42  [ТС]     [C++] графы #3
Цитата Сообщение от Mayonez Посмотреть сообщение
C++
1
2
3
4
    cout << "Введите начальную вершину" << endl;
    cin  >> start;
    cout << "Введите конечную вершину" << endl;
    cin  >> finish;
волновой алгоритм
как вершина может быть задана 1 цифрой??
или я что то не до понмаю???
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
22.03.2011, 19:56     [C++] графы #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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.03.2011, 19:58     [C++] графы
Еще ссылки по теме:

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

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

Графы - C++
Суть задачи: дан ориентированный граф, у которого каждая вершина (не ребро) имеет вес. Нужно найти путь из любой точки в любую, но чтобы он...

графы - C++
помогите пожалуйста написать программу! Составить программу печати всех циклов ориентированного графа Добавлено через 2 часа 21...

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

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


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

Или воспользуйтесь поиском по форуму:
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
22.03.2011, 19:58     [C++] графы #5
Цитата Сообщение от Kill100 Посмотреть сообщение
как вершина может быть задана 1 цифрой??
так как в кружочках одна цифра, а кружочки - это вершины, значит вершину графа можно задать одной цифрой, К.О.
Yandex
Объявления
22.03.2011, 19:58     [C++] графы
Ответ Создать тему
Опции темы

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