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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.77
Galinka
0 / 0 / 0
Регистрация: 29.04.2010
Сообщений: 3
#1

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

29.04.2010, 12:14. Просмотров 1837. Ответов 5
Метки нет (Все метки)

Доброго всем дня. прошу помощи или советов в реализации задачи типа:

задан орграф:
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++
Здравствуйте.Помогите пожалуйста решить задачу. Найти все вершины неориентированного графа, к которым существует путь заданной длины от...

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

Найти все вершины орграфа, от которых существует путь заданной длины к выделенной вершине - C++
Найти все вершины орграфа, от которых существует путь заданной длины к выделенной вершине.

Найти (в градусах, минутах и секундах) все угла треугольника, вершины которого заданы координатами (x1, y1), (x2, y2), (x3, y3) - C++
Найти (в градусах, минутах и секундах) все угла треугольника, вершины которого заданы координатами (x1, y1), (x2, y2), (x3, y3).

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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
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
вот два дня пыталась организовать алгоритм поиска в Ширину под свою задачу( никак.

а Алгоритм Декстры действительно подходит для решения моей задачи, НО я не нашла не одну его реализацию.(
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.05.2010, 17:34
Привет! Вот еще темы с ответами:

Вывести все вершины двоичного дерева - C++
Двоичное дерево задано в виде: m,g],s,y]] Как с помощью стека вывести это на экран? Набросайте, кому не трудно алгоритм) просто...

Определить, какие вершины достижимы из заданной вершины S - C++
Подскажите алгоритм для этой задачи, пожалуйста. Достижимые вершины Имя входного файла: graph.in Имя выходного файла: graph.out...

Найти все вершины графа, достижимые из заданной - Prolog
помогите пожалуйста с графами((:help: Найти все вершины графа, достижимые из заданной g(a,b,3). g(b,c,3). g(c,e,5). g(e,d,10). ...

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
02.05.2010, 17:34
Ответ Создать тему
Опции темы

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