Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.58/19: Рейтинг темы: голосов - 19, средняя оценка - 4.58
0 / 0 / 0
Регистрация: 29.04.2010
Сообщений: 3
1

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

29.04.2010, 12:14. Просмотров 3871. Ответов 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;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.04.2010, 12:14
Ответы с готовыми решениями:

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

Достижимые вершины в графе
В графе дано n вершин, m ребер, s - начальная вершина. Найти и вывести в порядке возрастания все...

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

Как найти координаты третьей вершины треугольника, зная все стороны и две вершины?
Добрый день, подскажите как найти координаты третьей вершины треугольника? Известны координаты...

5
150 / 73 / 27
Регистрация: 09.04.2010
Сообщений: 297
29.04.2010, 14:08 2
Если я правильно понял, то в этой книге : Искуство программирования на С++ Г. Шилдт
в главе 7 "Решение задач методами исскуственного интеллекта"
решается подобная задача...

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

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

а Алгоритм Декстры действительно подходит для решения моей задачи, НО я не нашла не одну его реализацию.(
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.05.2010, 17:34

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Найти все вершины заданного графа, недостижимые от заданной его вершины
Прошу помощи в написании программы с использованием обхода в глубину. Условие задачи: Найти все...

Найти все вершины заданного графа, недостижимые от заданной его вершины
Помогите написать программу. Условие: Найти все вершины заданного графа, недостижимые от заданной...

Графы. Найти все вершины заданного графа, недостижимые от заданной его вершины
Найти все вершины заданного графа, недостижимые от заданной его вершины. Помогите решить...

Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А
Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А....


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

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

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