Відмінності між версіями «Пошук графа вглибину»!!!
Матеріал з wiki
Onpage keywords chain search with * wildcard.
Example: sear* my nam* will find Searh my names and search my Name
111 (обговорення • внесок) м (111 перейменував сторінку з Глибинний пошук в графах на Пошук графа вглибину) |
111 (обговорення • внесок) (→Допоміжний АРІ) |
||
| (не показані 3 проміжні версії цього учасника) | |||
| Рядок 61: | Рядок 61: | ||
init_graph( g_p ); | init_graph( g_p ); | ||
dfs( g_p, 0, 5 ); | dfs( g_p, 0, 5 ); | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
destroyGraph( g_p ); | destroyGraph( g_p ); | ||
return 0; | return 0; | ||
| Рядок 251: | Рядок 93: | ||
int isEmptyPQueue (pqueue_t *q_p ); | int isEmptyPQueue (pqueue_t *q_p ); | ||
int isFullPQueue (pqueue_t *q_p );</nowiki> | int isFullPQueue (pqueue_t *q_p );</nowiki> | ||
| + | |||
| + | '''Виконав [[Романів Роман]]''' | ||
Поточна версія на 01:04, 19 лютого 2018
Пошук вглибину
Поняття
Алгоритм пошуку вглибину (Depth-First Search, DFS) - це метод пошуку графа, який починається з кореневого вузла, і оглядає кожну гілку на найглибшому рівні, перш ніж відслідковувати попередньо нерозвідані гілки. Знайдені, але ще не перевірені вузли зберігаються в черзі LIFO (стек).
Складність простору для DFS - це O (bd), де складність часу геометрична (O (b^d)). Це може бути великою проблемою для глибоких розгалужених графів, оскільки алгоритм буде продовжувати до максимальної глибини графа. Якщо в графі присутні цикли, DFS буде слідувати цим циклам безкінечно. З цієї причини алгоритм DFS не є повним, оскільки цикли можуть не дати алгоритму виявити ціль. Якщо на графі немає циклів, то алгоритм повний (завжди знайде цільовий вузол). Алгоритм DFS не є оптимальним, але може ним стати, за допомогою перевірки шляху (щоб забезпечити найкоротший шлях до мети).
Реалізація
Алгоритми графів можуть бути реалізовані як рекурсивно, так і за допомогою стеків для підтримки списку вузлів, які необхідно перерахувати. У нижче наведеному прикладі алгоритм DFS реалізується за допомогою стека LIFO. Також наведено необхідний допоміжний АРІ.
#include <stdio.h>
#include “graph.h”
#include “stack.h”
#define A 0
#define B 1
#define C 2
#define D 3
#define E 4
#define F 5
#define G 6
#define H 7
int init_graph( graph_t *g_p )
{
addEdge( g_p, A, B, 1 );
addEdge( g_p, A, C, 1 );
addEdge( g_p, B, D, 1 );
addEdge( g_p, C, E, 1 );
addEdge( g_p, C, F, 1 );
addEdge( g_p, D, G, 1 );
addEdge( g_p, D, H, 1 );
return 0;
}
void dfs( graph_t *g_p, int root, int goal )
{
int node;
int to;
stack_t *s_p;
s_p = createStack( 10 );
pushStack( s_p, root );
while ( !isEmptyStack(s_p) )
{
node = popStack( s_p );
printf(“%d\n”, node);
if (node == goal) break;
for (to = g_p->nodes-1 ; to > 0 ; to--)
{
if (getEdge( g_p, node, to ) )
{
pushStack( s_p, to );
}
}
}
destroyStack( s_p );
return;
}
int main()
{
graph_t *g_p;
g_p = createGraph( 8 );
init_graph( g_p );
dfs( g_p, 0, 5 );
destroyGraph( g_p );
return 0;
}
Допоміжний АРІ
Для демонстрації алгоритмів пошуку необхідний допоміжний АРІ, що включає перелічені функції:
/* Graph API */ graph_t *createGraph (int nodes ); void destroyGraph (graph_t *g_p ); void addEdge (graph_t *g_p, int from, int to, int value ); int getEdge (graph_t *g_p, int from, int to ); /* Stack API */ stack_t *createStack (int depth ); void destroyStack (stack_t *s_p ); void pushStack (stack_t *s_p, int value ); int popStack (stack_t *s_p ); int isEmptyStack (stack_t *s_p ); /* Queue API */ queue_t *createQueue (int depth ); void destroyQueue (queue_t *q_p ); void enQueue (queue_t *q_p, int value ); int deQueue (queue_t *q_p ); int isEmptyQueue (queue_t *q_p ); /* Priority Queue API */ pqueue_t *createPQueue (int depth ); void destroyPQueue (pqueue_t *q_p ); void enPQueue (pqueue_t *q_p, int value, int cost ); void dePQueue (pqueue_t *q_p, int *value, int *cost ); int isEmptyPQueue (pqueue_t *q_p ); int isFullPQueue (pqueue_t *q_p );
Виконав Романів Роман
Developed by Інститут Програмних Систем
