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

Как найти все вершины, достижимые из заднной??? - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.77
Galinka
0 / 0 / 0
Регистрация: 29.04.2010
Сообщений: 3
29.04.2010, 12:14     Как найти все вершины, достижимые из заднной??? #1
Доброго всем дня. прошу помощи или советов в реализации задачи типа:

задан орграф:
1) найти все вершины, недостижимые из заданной,
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 <vector>
#include <stdio.h>
#include <iostream>
#include <conio.h>
#include <stdlib.h>
 
 
using namespace std;
 
void Graph(vector<vector<int>>&c,int n)
{
    
    // матрица смежности для ориентированного графа. Заполнение массива 0 и 1
    for (int i=0;i<n;i++)
    {
        vector<int> d;
        for (int j=0;j<n;j++) 
        {
            d.push_back(rand()%2);  //заполняю одномкрный вектор
        }
            c.push_back(d);         //заполняю одномкрными векторами двымерный вектор
    }
    for(int i=0; i<n;i++)
        c[i][i] = 0;
}
 
 
void Print(vector<vector<int>>c,int n)      //печать графа
{
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<n;j++)
        printf ("%d ", c[i][j]);
        printf ("\n");
    }
}
 
int main(int argc, char* argv[])
{
    vector<vector<int>> c;                // наш конетейнер Vector (двумерный)
    int n;                                         // количество вершин
    cout<<"Vvedite chislo vershin: ";   // Номер может изменяться от 0 до p-1
    cin>>n;
 
    Graph(c,n);     
 
    Print(c,n);
 
    int s; // Начальная вершина
    cout<<"Vvedite nachal'nyuy vershiny: ";     // Номер может изменяться от 0 до p-1
    cin>>s;
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.04.2010, 12:14     Как найти все вершины, достижимые из заднной???
Посмотрите здесь:

C++ Найти все вершины орграфа, от которых существует путь заданной длины к выделенной вершине
Найти вершины наибольшего прямоугольника C++
Найти все вершины графа, к которым существует путь заданной длины от вершины, номер которой вводится с клавиатуры. C++
C++ Найти координаты 4 вершины
C++ Найти (в градусах, минутах и секундах) все угла треугольника, вершины которого заданы координатами (x1, y1), (x2, y2), (x3, y3)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
FireNovel
 Аватар для FireNovel
150 / 73 / 8
Регистрация: 09.04.2010
Сообщений: 297
29.04.2010, 14:08     Как найти все вершины, достижимые из заднной??? #2
Если я правильно понял, то в этой книге : Искуство программирования на С++ Г. Шилдт
в главе 7 "Решение задач методами исскуственного интеллекта"
решается подобная задача...

Может поможет
Galinka
0 / 0 / 0
Регистрация: 29.04.2010
Сообщений: 3
29.04.2010, 17:04  [ТС]     Как найти все вершины, достижимые из заднной??? #3
нет, не очень то что я ищу. Но все равно огромное спасибо)
мне бы реализацию алгоритма: поиск всех возможных путей из одной точки. а дальше я уж сама...
AntonZH
1 / 1 / 0
Регистрация: 09.11.2008
Сообщений: 61
29.04.2010, 21:21     Как найти все вершины, достижимые из заднной??? #4
Почти наверняка тебя интересует алгоритм, который называется "Поиск в ширину" или "Breadth-first search".

http://ru.wikipedia.org/wiki/Поиск_в_ширину
enari
 Аватар для enari
18 / 18 / 2
Регистрация: 26.04.2010
Сообщений: 35
30.04.2010, 11:22     Как найти все вершины, достижимые из заднной??? #5
Алгоритм Декстры
Galinka
0 / 0 / 0
Регистрация: 29.04.2010
Сообщений: 3
02.05.2010, 17:34  [ТС]     Как найти все вершины, достижимые из заднной??? #6
вот два дня пыталась организовать алгоритм поиска в Ширину под свою задачу( никак.

а Алгоритм Декстры действительно подходит для решения моей задачи, НО я не нашла не одну его реализацию.(
Yandex
Объявления
02.05.2010, 17:34     Как найти все вершины, достижимые из заднной???
Ответ Создать тему
Опции темы

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