Обхід графа методом пошуку в глибину

     Мета : здійснити обхід графа методом пошуку в глибину  

     Теоретичні  відомості

     Існує багато алгоритмів на графах які ґрунтуються на переборах їх вершин або обходів вершин під час якого кожна вершина має свій унікальний порядковий номер.

     Алгоритм  обходу графа називається методом пошуку графа.

     Пошук в глиб

     Нехай простий зв’язний граф усі вершини якого позначені попарно різними символами у процесі пошуку у глиб вершину графа надають номер ) та певним способом позначають ребра.

     У вході роботи алгоритму  використовують структуру даних збереження вершин яку називають стеком. Зі стеку можна вилучити тільки той елемент котрий було додано останнім.

     Додавання і вилучення елементів у стеку  відбувається з одного кінця який називається верхівкою стеку.

     Виконання роботи

     Дано  простий зв’язний граф 

           

Пошук в глиб

 
 

     

Приклад програми:

     

#include <stdio.h>

     

#include <memory.h>

     

#define MAX 100

     

int m[MAX][MAX], used[MAX];

     

int i, n, a, b, ptr;

     

void dfs(int v){

     

  int i;  used[v] = 1; 

     

printf("Vertex %d is visited\n",v);

     

  for(i = 0; i < n; i++)

     

    if (m[v][i] && !used[i]) dfs(i);

     

  printf("Returned to %d",v); }

     

int main(void){

     

  memset(m,0,sizeof(m)); memset(used,0,sizeof(used));

     

  scanf("%d",&n); for(i = 0; i < n; i++)  {

           

printf("input a, b:");

           

scanf("%d %d",&a,&b);

           

m[a][b] = m[b][a] = 1;  }

     

  dfs(0);

     

  return 0;

     

}

     

   

     

Результат програми:

     

 

     

Висновок: під час виконання роботи

здійснила обхід графа методом пошуку в глибину