Алгоритъм за дълбочина първо търсене (DFS)

Съдържание

Дълбочина Първи алгоритъм за търсене
Пример за дълбочина първо търсене
DFS псевдокод (рекурсивно изпълнение)
Внедряване на DFS в Python, Java и C / C ++
Сложност на дълбочина първо търсене
Приложение на DFS алгоритъм

В този урок ще научите за алгоритъма за първо търсене в дълбочина с примери и псевдокод. Също така ще се научите да прилагате DFS в C, Java, Python и C ++.

Дълбочина първо търсене или Дълбочина първо обръщане е рекурсивен алгоритъм за търсене във всички върхове на графика или дървовидна структура от данни. Обхождането означава посещение на всички възли на графика.

Дълбочина Първи алгоритъм за търсене

Стандартно внедряване на DFS поставя всеки връх на графиката в една от двете категории:

Посетен
Не е посетен

Целта на алгоритъма е да маркира всеки връх като посетен, като същевременно се избягват цикли.

Алгоритъмът DFS работи по следния начин:

Започнете, като поставите някой от върховете на графиката върху стека.
Вземете най-горния елемент от стека и го добавете към посетения списък.
Създайте списък със съседните възли на този връх. Добавете тези, които не са в списъка на посетените, в горната част на стека.
Продължавайте да повтаряте стъпки 2 и 3, докато стекът се изпразни.

Пример за дълбочина първо търсене

Нека да видим как работи алгоритъмът за дълбочина първо търсене с пример. Използваме неориентирана графика с 5 върха.

Ненасочена графика с 5 върха

Започваме от връх 0, алгоритъмът DFS започва, като го поставя в списъка Visited и поставя всички съседни върхове в стека.

Посетете елемента и го поставете в списъка на посетените

След това посещаваме елемента в горната част на стека, т.е. 1 и отиваме в съседните му възли. Тъй като 0 вече е посетен, вместо него посещаваме 2.

Посетете елемента в горната част на стека

Vertex 2 има непосетен съседен връх в 4, така че добавяме това в горната част на стека и го посещаваме.

След като посетим последния елемент 3, той няма никакви непосетени съседни възли, така че завършихме дълбочината първо обхождане на графиката.

DFS псевдокод (рекурсивно изпълнение)

Псевдокодът за DFS е показан по-долу. Във функцията init () забележете, че ние изпълняваме функцията DFS на всеки възел. Това е така, защото графиката може да има две различни несвързани части, така че за да сме сигурни, че покриваме всеки връх, можем също да стартираме алгоритъма DFS на всеки възел.

 DFS (G, u) u.visited = вярно за всеки v ∈ G.Adj (u), ако v.visited == false DFS (G, v) init () (За всеки u ∈ G u.visited = false За всеки u ∈ G DFS (G, u))

Внедряване на DFS в Python, Java и C / C ++

Кодът за алгоритъма за дълбочина първо търсене с пример е показан по-долу. Кодът е опростен, за да можем да се съсредоточим върху алгоритъма, а не върху други подробности.

Python Java C C +

 # 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; )