Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
-14 / 4 / 4
Регистрация: 19.01.2017
Сообщений: 560
1

Графы. Поиск в глубину

07.09.2019, 14:45. Показов 1002. Ответов 2
Метки нет (Все метки)

Создать программу, которая реализует поиск пути между двумя произвольными вершинами графа согласно варианту. Номера вершин для поиска пути между ними пользователь должен ввести самостоятельно. Для получения оценки «отлично» реализовать граф с помощью списков смежности.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Миниатюры
Графы. Поиск в глубину  
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.09.2019, 14:45
Ответы с готовыми решениями:

Поиск в глубину. Графы. С++
Задана ,допустим, такая матрица смежности 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1...

графы. поиск в глубину
Здраствуйте. Вот такая задача N шестеpенок пpонумеpованы от 1 до N (N ≤ 10). Заданы M (0...

графы,поиск в глубину
очень нужна помощь!нужно в неориентированном графе найти компоненты связности поиском в глубину....

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

2
-14 / 4 / 4
Регистрация: 19.01.2017
Сообщений: 560
07.09.2019, 19:16  [ТС] 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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <iostream>
#include <cstdlib>
 
using namespace std;
 
const int n1 = 5;
int Graph_metodichka[n1][n1] = {
{0,0,0,0,0},
{0,0,1,1,0},
{0,0,0,1,1},
{0,1,0,0,1},
{0,0,1,0,0}
};
 
const int n2 = 6;
int Graph_my_variant[n2][n2]={{0,0,0,0,0,0,0},//0
                 {0,0,1,1,0,1,0},//1
                 {0,1,0,1,0,0,0},//2
                 {0,1,1,0,0,1,1},//3
                 {0,0,0,0,0,1,1},//4
                 {0,1,0,1,1,0,1},//5
                 {0,0,0,0,1,1,0}};//6*/
const int n = n2;
int Graph[n][n];
void insertG(){
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        Graph[i][j] = Graph_my_variant[i][j];
}
 
int mark[n]={0};
int cf = 0; //cf1=0;
int all_path[n];
int d[n];
int q[n];
int last=0;
int last_p=0;
int start = 0;
int finish = 6;
//int finish = 4;
void push(int x){
    if(last!=finish){
        last++;
        q[last] = x;
    }
    else cout<<"Error!\n";
}
int pop(){
    if(last>-1){
        return q[last--];
    }
    else {return -1;}
}
bool empty(){
    if(last == -1) { return true;}
    else {return false;}
}
void BFS(){
    push(start);
    d[start] = 0;
    mark[start]=1;
    while(!empty()){
        int v = pop();
        for(int i=0;i<n;i++){
            if(Graph[v][i] != 0){
                if(mark[i] == 0){
                        cf++;
                    d[i] = d[v]+1;
                    all_path[cf] = i;
                    cout<<"["<<d[i]<<"] ";
                    mark[i] = 1;
                    push(i);
                }
            }
        }
    }
}
void printGraph(){
    for(int i=0;i<n;i++){ cout<<"\t";
        for(int j=0;j<n;j++){
            cout<<"["<<Graph[i][j]<<"] ";
        }
        cout<<endl;
    }
}
void printImgGraph(){
    cout<<"\t\t         (2)            (4)\n";
    cout<<"\t\t        / |              | \\\n";
    cout<<"\t\t      /   |              |   \\\n";
    cout<<"\t\t    /     |              |     \\\n";
    cout<<"\t\t(1) ======|======\\       |     (6)\n";
    cout<<"\t\t    \\     |        \\     |     /\n";
    cout<<"\t\t      \\   |          \\   |   /\n";
    cout<<"\t\t        \\ |            \\ | /\n";
    cout<<"\t\t          (3)-----------(5)\n";
    cout<<"\n\n";
     for(int i=1;i<n;i++){
                    for(int j=1;j<n;j++){ cout<<'\t';
                        cout<<"["<<Graph[i][j]<<"] ";
                    }
                    cout<<endl;
                }
}
int main(){
    setlocale(LC_ALL, "Rus");
    insertG();
    printImgGraph();
 //   printGraph();
    cout<<"Полный путь всего графа:\n\n";
    start = 1;
    finish = n;
     for(int i=0;i<n;i++) {d[i]=-1;all_path[i]=-1;}
    cout<<"\t       "; BFS();
    cout<<"\nПолный путь: "<<start;
    for(int i=0;i<n;i++) if(all_path[i]!=-1) cout<<" ["<<all_path[i]<<"]";
 
while(true){
        cout<<"\n---------------------------------------\n";
        cout<<"Введите начало пути: "; cin>>start;
        cout<<"Введите конец пути: "; cin>>finish;
 
        if(start > finish) {
            int buf_start = start;
            start = finish;
            finish = buf_start;
        }
        if(start<1 || start>n || finish<1 || finish>n) {
            cout<<"\nНеверно заданные координаты!\n\n";
            continue;
        }
        else {
                last=0;
                last_p=0;
                cf = 0;
                cout<<"\nИтерация на которой была найдена: ";
                for(int i=0;i<n;i++) {d[i]=-1;all_path[i]=-1; mark[i]=0;}
                BFS();
                cout<<"\nПуть по заданным координатам:  "<<start;
                for(int i=0;i<n;i++) if(all_path[i]!=-1) cout<<" ["<<all_path[i]<<"]";
                //cout<<" "<<finish;
                cout<<"\n\nСтандартный порядок итераций по координатам графа: ";
                for(int i=1;i<n;i++) cout<<" ["<<d[i]<<"]";
                 cout<<"\nСтандартный путь графа по заданным координатам: ";
                for(int i=1;i<n;i++)  cout<<" ["<<q[i]<<"]";
        }
        cout<<"\n\n\n\n";
        cout<<"Полное количество прохождения циклов = "<<cf<<endl;
        int count_head = 0;
        for(int i=0;i<n;i++) count_head+=mark[i];
        cout<<"\n\nОбщее количество всех вершин графа = "<<count_head<<endl;
    //    cout<<"\n\ncf1 = "<<cf1<<endl;
}
    return 0;
}
Добавлено через 2 часа 5 минут
Up!
0
-14 / 4 / 4
Регистрация: 19.01.2017
Сообщений: 560
08.09.2019, 18:59  [ТС] 3
Правильно, можете исправить?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.09.2019, 18:59

Поиск в глубину
Объясните плз поиск в глубину с примером. Сам много реалихаций нашел, но до конца не могу...

Поиск в глубину
Здравствуйте. Как реализовать поиск кратчайшего пути в невзвешенном графе через поиск в глубину? ...

Поиск в глубину
&quot;В рождественскую ночь Санта-Клаус спускается по каминной трубе и раскладывает детям подарки....

поиск в глубину
Дали задание реализовать поиск в глубину.Пробую релизовать по e-maxx http://e-maxx.ru/algo/dfsно не...


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

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

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