Теория графов

Теория графов


Стеки  и очереди

http://brestprog.by/topics/datastructures/


На Фоксфорд




Поиск в глубину
На Фоксфорд
Рекурсивный На Харбр
Еще 1
http://haru-atari.com/ru/blog/17/algorithms-on-graphs-deep-first-search-dfs-dls-iddfs

Друзья

Друзья

(Время: 1 сек. Память: 16 Мб Сложность: 41%)

В клубе N человек. Многие из них - друзья. Так же известно, что друзья друзей так же являются друзьями. Требуется выяснить, сколько всего друзей у конкретного человека в клубе.

Входные данные

В первой строке входного файла INPUT.TXT заданы два числа: N и S (1 ≤ N ≤ 100; 1 ≤ S ≤ N), где N - количество человек в клубе, а S – номер конкретного человека. В следующих N строках записано по N чисел - матрица смежности, состоящая из единиц и нулей. Причем единица, стоящая в i-й строке и j-м столбце гарантирует, что люди с номерами i и j – друзья, а 0 – выражает неопределенность.

Выходные данные

В выходной файл OUTPUT.TXT выведите количество гарантированных друзей у человека с номером S, помня о транзитивности дружбы.

Пример

№	INPUT.TXT	OUTPUT.TXT
1	3 1 0 1 0 1 0 1 0 1 0	2

https://acmp.ru/asp/do/index.asp?main=task&id_course=2&id_section=21&id_topic=50&id_problem=637

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main(){
int N, S; cin>>N>>S;
vector<int> a[N];
int x;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++)
{ cin>>x;
if (x==1) a[i].push_back(j);}}
vector <int> v(N,0); stack <int> T;
T.push(S-1);v[S-1]=1;int kol=0;
while(!T.empty()){
 x=T.top();
 int i=0;
 while(i<a[x].size() && v[a[x][i]]==1 ) i++;
 if(i==a[x].size()) T.pop();
 else { T.push(a[x][i]); v[a[x][i]]=1; kol++; }}
 cout<<kol;
 return 0;
}



Поиск в ширину
На Фоксфорд

Путь

(Время: 1 сек. Память: 16 Мб Сложность: 40%)

В неориентированном графе требуется найти длину кратчайшего пути между двумя вершинами.

Входные данные

Во входном файле INPUT.TXT записано сначала число N - количество вершин в графе (1 ≤ N ≤ 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). Затем записаны номера двух вершин - начальной и конечной.

Выходные данные

В выходной файл OUTPUT.TXT выведите длину кратчайшего пути. Если пути не существует, выведите одно число -1.

Пример

№	INPUT.TXT	OUTPUT.TXT
1	5 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 3 5	3

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int main(){
int N; cin>>N;
vector<int> a[N];
int x;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++)
{ cin>>x;
if (x==1) a[i].push_back(j);}}

int N1, N2; cin>>N1>>N2;
vector <int> v(N,-1); queue <int> Q;
Q.push(N1-1);v[N1-1]=0;
while(!Q.empty()){
 x=Q.front();  Q.pop();
 for(int i=0; i<a[x].size();i++)
  if(v[a[x][i]]==-1){ Q.push(a[x][i]); v[a[x][i]]=v[x]+1; }
}
 cout<<v[N2-1];
 return 0;
}


Интуит.РУ
https://www.intuit.ru/studies/courses/648/504/lecture/11474?page=2

Поиск в глубину и ширину

Алгоритм Дейкстра
На Фоксфорд

Онлайн-компилятор