Алгоритам дубинске претраге (ДФС)

Преглед садржаја

Дубина алгоритма прве претраге
Пример дубинске претраге
ДФС псеудо код (рекурзивна имплементација)
Имплементација ДФС-а у Питхон, Јава и Ц / Ц ++
Сложеност дубинског претраживања
Примена ДФС алгоритма

У овом упутству ћете научити алгоритам претраживања дубине са примерима и псеудокодом. Такође, научићете да примените ДФС на Ц, Јава, Питхон и Ц ++.

Дубинско прво претраживање или Дубинско прво превртање је рекурзивни алгоритам за претрагу свих врхова графикона или структуре података стабла. Прелазак значи посећивање свих чворова графа.

Дубина алгоритма прве претраге

Стандардна ДФС имплементација ставља сваки врх графикона у једну од две категорије:

Посетили
Није посећено

Сврха алгоритма је да означи сваки врх као посећени, избегавајући циклусе.

ДФС алгоритам ради на следећи начин:

Почните стављањем било ког од врхова графа на врх стека.
Узмите горњу ставку гомиле и додајте је на посећену листу.
Направите листу суседних чворова тог темена. На врх стека додајте оне који нису на посећеној листи.
Понављајте кораке 2 и 3 док се стек не испразни.

Пример дубинске претраге

Погледајмо како алгоритам дубинске претраге прво функционише на примеру. Користимо неусмерени граф са 5 темена.

Неусмерени граф са 5 темена

Полазимо од врха 0, ДФС алгоритам започиње стављањем на листу Посећено и стављањем свих суседних врхова у стек.

Посетите елемент и ставите га на листу посећених

Даље, посећујемо елемент на врху стека, тј. 1 и идемо до његових суседних чворова. С обзиром да је 0 већ посећено, уместо тога посетимо 2.

Посетите елемент на врху стека

Вертек 2 има непосећени суседни темен у 4, па га додајемо на врх стека и посећујемо га.

Након што посетимо последњи елемент 3, он нема ниједан непосећени суседни чвор, па смо довршили дубинско прелажење графикона.

ДФС псеудо код (рекурзивна имплементација)

Псеудокод за ДФС је приказан испод. У функцији инит (), приметите да покрећемо функцију ДФС на сваком чвору. То је зато што графикон може имати два различита неповезана дела, па да бисмо били сигурни да покривамо сваки врх, такође можемо покренути ДФС алгоритам на сваком чвору.

 ДФС (Г, у) у.виситед = тачно за сваки в ∈ Г.Адј (у) ако је в.виситед == фалсе ДФС (Г, в) инит () (За сваки у ∈ Г у.виситед = фалсе За сваки у ∈ Г ДФС (Г, у))

Имплементација ДФС-а у Питхон, Јава и Ц / Ц ++

Шифра алгоритма за дубинску претрагу са примером је приказана испод. Код је поједностављен тако да се можемо усредсредити на алгоритам, а не на друге детаље.

Питхон Јава Ц Ц +

 # DFS algorithm in Python # DFS algorithm def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start) for next in graph(start) - visited: dfs(graph, next, visited) return visited graph = ('0': set(('1', '2')), '1': set(('0', '3', '4')), '2': set(('0')), '3': set(('1')), '4': set(('2', '3'))) dfs(graph, '0')

 // DFS algorithm in Java import java.util.*; class Graph ( private LinkedList adjLists(); private boolean visited(); // Graph creation Graph(int vertices) ( adjLists = new LinkedList(vertices); visited = new boolean(vertices); for (int i = 0; i < vertices; i++) adjLists(i) = new LinkedList(); ) // Add edges void addEdge(int src, int dest) ( adjLists(src).add(dest); ) // DFS algorithm void DFS(int vertex) ( visited(vertex) = true; System.out.print(vertex + " "); Iterator ite = adjLists(vertex).listIterator(); while (ite.hasNext()) ( int adj = ite.next(); if (!visited(adj)) DFS(adj); ) ) public static void main(String args()) ( Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); System.out.println("Following is Depth First Traversal"); g.DFS(2); ) )

 // DFS algorithm in C #include #include struct node ( int vertex; struct node* next; ); struct node* createNode(int v); struct Graph ( int numVertices; int* visited; // We need int** to store a two dimensional array. // Similary, we need struct node** to store an array of Linked lists struct node** adjLists; ); // DFS algo void DFS(struct Graph* graph, int vertex) ( struct node* adjList = graph->adjLists(vertex); struct node* temp = adjList; graph->visited(vertex) = 1; printf("Visited %d ", vertex); while (temp != NULL) ( int connectedVertex = temp->vertex; if (graph->visited(connectedVertex) == 0) ( DFS(graph, connectedVertex); ) temp = temp->next; ) ) // Create a node struct node* createNode(int v) ( struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; ) // Create graph struct Graph* createGraph(int vertices) ( struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); graph->visited = malloc(vertices * sizeof(int)); int i; for (i = 0; i adjLists(i) = NULL; graph->visited(i) = 0; ) return graph; ) // Add edge void addEdge(struct Graph* graph, int src, int dest) ( // Add edge from src to dest struct node* newNode = createNode(dest); newNode->next = graph->adjLists(src); graph->adjLists(src) = newNode; // Add edge from dest to src newNode = createNode(src); newNode->next = graph->adjLists(dest); graph->adjLists(dest) = newNode; ) // Print the graph void printGraph(struct Graph* graph) ( int v; for (v = 0; v numVertices; v++) ( struct node* temp = graph->adjLists(v); printf(" Adjacency list of vertex %d ", v); while (temp) ( printf("%d -> ", temp->vertex); temp = temp->next; ) printf(""); ) ) int main() ( struct Graph* graph = createGraph(4); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 2); addEdge(graph, 2, 3); printGraph(graph); DFS(graph, 2); return 0; )

 // DFS algorithm in C++ #include #include using namespace std; class Graph ( int numVertices; list *adjLists; bool *visited; public: Graph(int V); void addEdge(int src, int dest); void DFS(int vertex); ); // Initialize graph Graph::Graph(int vertices) ( numVertices = vertices; adjLists = new list(vertices); visited = new bool(vertices); ) // Add edges void Graph::addEdge(int src, int dest) ( adjLists(src).push_front(dest); ) // DFS algorithm void Graph::DFS(int vertex) ( visited(vertex) = true; list adjList = adjLists(vertex); cout << vertex << " "; list::iterator i; for (i = adjList.begin(); i != adjList.end(); ++i) if (!visited(*i)) DFS(*i); ) int main() ( Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); g.DFS(2); return 0; )