Поиск ширину (волновой алгоритм)
02.09.2015
Сетевые структуры
Элемент в сетевой структуре данных характеризуются набором связи с другими соседними элементами,в таких структурах данных не начальные, не корневой элементы явно не выделены.
Сетевые структуры в основном моделируются структурой графа.
Схема структуры графа: неориентированный (рис1) (вершины, ребра (без стрелок)); ориентированный (петля, дуга (со стрелками)); взвешенный (,весы (со цифркаим)).
Представления графов: мы рассмотрим 2 способа представления графа: 1) При помощи матрицы смежности; 2) При помощи списка смежности.
Матрица смежности: для графа представленного на (рис 1) матрица смежности будет иметь вид: для неориентированного графа матрица смежности симметрична; для ориентированного графа матрица смежности не симметрична.
Список смежности: если в графе мало ребер используется список смежности. Для (рис 1) список смежности будет иметь вид:
Основной задачей в алгоритмах на графа являются задачей поиска, например минимального пути, минимальной затраты и т.д.
Поиск ширину (волновой алгоритм)
Задача: пусть дан неориентированный граф G<V,E> например представленный на (рис 1).
Необходимо найти кротчайший путь от вершины START до вершины FINISH.
Задание матрицы смежности при помощи списка ребер. Для примера из (рис 1) будет выглядеть так: количество вершин; количество ребер (перечисление ребер; весы).
START=1; FINISH=5
|
|
|
Для реализации данного алгоритма необходимо иметь матрицу смежности и 3 одномерных массива: QUEUE; VISIT; WAY;
#include <iostream>
#include <string.h>
Using namespace std;
Int QUEUE[100],WAY[1000], VISIT[1000], a[1000][1000], n, m, k, start, finish;
Void Print(int v)
{
If(v>0)
{
Print(WAY[v]); cout<<v<<’ ’;
}
}
Void bfs (int st) //breads-first search.
{
Int i=1, j, k=1, u;
QUEUE[k]=st; VSIT[st]=1;
Do
{
u=QUEUE[i];
for(j=1;j<=n;j++)
if(a[u][j]>0 && VISIT[j]==0)
{
VISIT[j]=1; WAY[j]=u; QUEUE[++k]=j;
}
i++;
}
While(i<=k);
}
Void init()
{
Int i, j,k;
Cin>>n>>m; //n-кол-во вершин, m-количество ребер
Memset(a,0,sizeof(a));
Memset(visit,o,sizeof(visit));
For(k=1;k<=m;k++)
{
cin>>i>>j;
a[i][j]=1; a[j][i]=1;
}
cin>>start<<finish;
}
Void main()
{
init();
bfs(start);
Print(finish);
}
Временная сложность алгоритма O(n*n) так как мы используем для поиска двумерную матрицу смежности.
Поиск ширины с использованием списка смежности.
Та же задача. Рассмотрим программу.
#include <iostream>
#include <string.h>
Using namespace std;
Const int MAXN=100;
Vect<int>spis[MAXN];
Int visit[MAXN], way[MAXN], queue[MAXN];
Int n,m,start,finish;
Void init()
{
Int I,j,k;
Cin>>n>>m;
Memset(visit,0,sizeof(visit));
For(k=1;k<=m;k++)
{
Cin>>i>>j;
Spis[i].push.back(j);
Spis[j].push.back(i);
}
Cin>>start>>finish;
}
Void Print (int v)
{
If(v>0)
{
Print(way[v]); cout<<v<<i;
}
}
Void bfs (int v)
{
Int i=1, j,k=1,u;
Queue[k]=v; visit[v]=1;
Do
{
u=queue[i];
for(j=0;j<spis[u].size();j++)
if(visit[spis[u][j]]==0)
|
|
|
{
Visit[spis[u][j]]=1; way[spis[u][j]]=u;
Queue[++k]=spis[u][j];
}
I++;
}
While(i<=k);
}
Void main()
{
Init();
Bfs(start);
Print(finish);
}
Временная сложность с использованием списка смежности равна O(n+m). M=n(n-1)/2
Поиск глубину (рис)
Dfs-depth-first search/поиск первого глубину.
Алгоритм:
а) Поиск начинается с некоторой вершины v=start
б) Ищется ранее не посещенная вершина u смежная с вершиной v, если такая вершина есть, это вершина u запоминается и снова повторяется шаг б с вершиной v=u.
Иначе: с) Возвращается в предыдущей вершине для очередного выполнения шага б. В том случае, когда не посещенной смежной вершины нет, процесс заканчивается.
И так мы не рассматриваем все смежные вершины, а выбираем первую не посещенную и быстро продвигаемся вглубь, откладывая их посещения на потом.
Используемые структуры: Алгоритм использует кроме матрицы смежности 2 одномерных массива: VISIT[v] -отметка по посещенности: 0-вершина еще непосещена; 1-вершина уже посещена. WAY[u] -содержит номер вершины v с которой мы пришли в вершину u. Временная сложность также зависит от представления графа. О(n*n)-матрица смежности; О(n+m)-список смежности.
Рассмотрим порядок заполнения вспомогательных массивов на исходном примере:
Дан граф, напечатать все цепи.
|
|
|
Void dfs(int v)
{
Int u;
Visit[v]=1;
For(u=1;u<=n;u++)
If(a[v][u]>0&&visit[u]=0)
{
Way[u]=v; dfs(u);
}
Print(v); cout<<end;
Visit[v]=0;
}
16.09.2015.
Дата добавления: 2016-01-06; просмотров: 14; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!