{"draftJsState":{"blocks":[{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":" ","type":"unstyled","key":"43mho"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":5,"offset":0,"style":"BOLD"},{"length":39,"offset":43,"style":"BOLD"}],"text":"Обход означает посещение всех узлов графа. «Обход в глубину» или «Поиск в глубину» - это рекурсивный алгоритм поиска всех вершин графа или древовидной структуры данных. В этой статье, с помощью приведенных ниже примеров, вы узнаете: алгоритм DFS, псевдокод DFS и код алгоритма «поиска в глубину» с реализацией в программах на C ++, C, Java и Python.","type":"unstyled","key":"5fv58"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Алгоритм DFS","type":"header-two","key":"dp3uc"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Стандартная реализация DFS помещает каждую вершину графа в одну из двух категорий:","type":"unstyled","key":"73b3j"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Посещенные.","type":"unordered-list-item","key":"o11r"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Не посещенные.","type":"unordered-list-item","key":"cb7d9"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":14,"offset":0,"style":"ITALIC"}],"text":"Цель алгоритма - пометить каждую вершину, как посещенную, избегая циклов.","type":"unstyled","key":"4i4bt"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Алгоритм DFS работает следующим образом:","type":"unstyled","key":"8vnh0"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Начните с размещения любой вершины графа на вершине стека.","type":"unordered-list-item","key":"6krcj"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Возьмите верхний элемент стека и добавьте его в список посещенных.","type":"unordered-list-item","key":"13fab"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Создайте список смежных узлов этой вершины. Добавьте те, которых нет в списке посещенных, в начало стека.","type":"unordered-list-item","key":"78ihs"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Продолжайте повторять шаги 2 и 3, пока стек не станет пустым.","type":"unordered-list-item","key":"899ol"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Пример DFS","type":"header-two","key":"e7qoo"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Давайте посмотрим, как алгоритм «поиска в глубину» работает на примере. Мы используем неориентированный граф с 5 вершинами.","type":"unstyled","key":"2t8aq"},{"data":{"image":{"id":"5d569624c49f2900ad3605a3"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"ad134"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Мы начинаем с вершины 0, алгоритм DFS начинается с помещения его в список посещенных и размещения всех смежных вершин в стеке.","type":"unstyled","key":"63cd"},{"data":{"image":{"id":"5d5696248da1ce00aea5a859"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"9t29s"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Затем мы посещаем элемент в верхней части стека, то есть 1, и переходим к смежным узлам. Так как 0 мы уже посетили, вместо этого посещаем 2.","type":"unstyled","key":"29oq9"},{"data":{"image":{"id":"5d569624a2d6ed00ae0de298"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"euaju"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"У вершины 2 есть не посещенная смежная вершина 4, поэтому мы добавляем ее в верхнюю часть стека и посещаем.","type":"unstyled","key":"fbr7s"},{"data":{"image":{"id":"5d569624027a1500adaf0dac"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"766ia"},{"data":{"image":{"id":"5d569624d4f07a00add7ae2a"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"5can5"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"После того, как мы посетим последний элемент 3, у него нет не посещенных смежных узлов. На этом мы завершим первый «обход в глубину» графа.","type":"unstyled","key":"e682b"},{"data":{"image":{"id":"5d569624f2df2500ac866bf0"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"4rblv"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Псевдокод DFS (рекурсивная реализация)","type":"header-two","key":"6c403"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":6,"offset":65,"style":"BOLD"}],"text":"Псевдокод для DFS показан ниже. Обратите внимание, что в функции init() мы запускаем функцию DFS на каждом узле. Это связано с тем, что граф может иметь две разные несвязанные части, поэтому, чтобы убедиться, что мы покрываем каждую вершину, мы также можем запустить алгоритм DFS на каждом узле.","type":"unstyled","key":"fjmfb"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"DFS(G, u)\n u.visited = true\n for each v ∈ G.Adj[u]\n if v.visited == false\n DFS(G,v)\n \ninit() {\n For each u ∈ G\n u.visited = false\n For each u ∈ G\n DFS(G, u)\n}","type":"unstyled","key":"6bpc3"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Код DFS","type":"header-two","key":"7n9f5"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Код для алгоритма «поиска в глубину» с примером показан ниже. Код был упрощен, поэтому мы можем сосредоточиться на алгоритме, а не на других деталях.","type":"unstyled","key":"bejjj"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"DFS в C","type":"header-two","key":"dosom"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"#include \n#include \n \nstruct node\n{\n int vertex;\n struct node* next;\n};\n \nstruct node* createNode(int v);\n \nstruct Graph\n{\n int numVertices;\n int* visited;\n struct node** adjLists; // we need int** to store a two dimensional array. Similary, we need struct node** to store an array of Linked lists\n};\n \nstruct Graph* createGraph(int);\nvoid addEdge(struct Graph*, int, int);\nvoid printGraph(struct Graph*);\nvoid DFS(struct Graph*, int);\n \n \nint main()\n{\n \n struct Graph* graph = createGraph(4);\n addEdge(graph, 0, 1);\n addEdge(graph, 0, 2);\n addEdge(graph, 1, 2);\n addEdge(graph, 2, 3);\n \n printGraph(graph);\n \n DFS(graph, 2);\n \n return 0;\n}\n \nvoid DFS(struct Graph* graph, int vertex) {\n struct node* adjList = graph->adjLists[vertex];\n struct node* temp = adjList;\n \n graph->visited[vertex] = 1;\n printf(\"Visited %d \\n\", vertex);\n \n while(temp!=NULL) {\n int connectedVertex = temp->vertex;\n \n if(graph->visited[connectedVertex] == 0) {\n DFS(graph, connectedVertex);\n }\n temp = temp->next;\n } \n}\n \n \nstruct node* createNode(int v)\n{\n struct node* newNode = malloc(sizeof(struct node));\n newNode->vertex = v;\n newNode->next = NULL;\n return newNode;\n}\n \nstruct Graph* createGraph(int vertices)\n{\n struct Graph* graph = malloc(sizeof(struct Graph));\n graph->numVertices = vertices;\n \n graph->adjLists = malloc(vertices * sizeof(struct node*));\n \n graph->visited = malloc(vertices * sizeof(int));\n \n int i;\n for (i = 0; i < vertices; i++) {\n graph->adjLists[i] = NULL;\n graph->visited[i] = 0;\n }\n return graph;\n}\n \nvoid addEdge(struct Graph* graph, int src, int dest)\n{\n // Add edge from src to dest\n struct node* newNode = createNode(dest);\n newNode->next = graph->adjLists[src];\n graph->adjLists[src] = newNode;\n \n // Add edge from dest to src\n newNode = createNode(src);\n newNode->next = graph->adjLists[dest];\n graph->adjLists[dest] = newNode;\n}\n \nvoid printGraph(struct Graph* graph)\n{\n int v;\n for (v = 0; v < graph->numVertices; v++)\n {\n struct node* temp = graph->adjLists[v];\n printf(\"\\n Adjacency list of vertex %d\\n \", v);\n while (temp)\n {\n printf(\"%d -> \", temp->vertex);\n temp = temp->next;\n }\n printf(\"\\n\");\n }\n}","type":"unstyled","key":"6t1po"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Depth First Search (DFS) в C++","type":"header-two","key":"fdbic"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"#include \n#include \nusing namespace std;\n \nclass Graph\n{\n int numVertices;\n list *adjLists;\n bool *visited;\n \npublic:\n Graph(int V);\n void addEdge(int src, int dest);\n void DFS(int vertex);\n};\n \nGraph::Graph(int vertices)\n{\n numVertices = vertices;\n adjLists = new list[vertices];\n visited = new bool[vertices];\n}\n \nvoid Graph::addEdge(int src, int dest)\n{\n adjLists[src].push_front(dest);\n}\n \nvoid Graph::DFS(int vertex)\n{\n \n visited[vertex] = true;\n list adjList = adjLists[vertex];\n \n cout << vertex << \" \";\n \n list::iterator i;\n for(i = adjList.begin(); i != adjList.end(); ++i)\n if(!visited[*i])\n DFS(*i);\n}\n \nint main()\n{\n Graph g(4);\n g.addEdge(0, 1);\n g.addEdge(0, 2);\n g.addEdge(1, 2);\n g.addEdge(2, 3);\n \n g.DFS(2);\n \n return 0;\n}","type":"unstyled","key":"d4tk8"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"DFS Java код (Java code)","type":"header-two","key":"etjkt"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"import java.io.*;\nimport java.util.*;\n \n \nclass Graph\n{\n private int numVertices;\n private LinkedList adjLists[];\n private boolean visited[];\n \n Graph(int vertices)\n {\n numVertices = vertices;\n adjLists = new LinkedList[vertices];\n visited = new boolean[vertices];\n \n for (int i = 0; i < vertices; i++)\n adjLists[i] = new LinkedList();\n }\n \n void addEdge(int src, int dest)\n {\n adjLists[src].add(dest);\n }\n \n void DFS(int vertex)\n {\n visited[vertex] = true;\n System.out.print(vertex + \" \");\n \n Iterator ite = adjLists[vertex].listIterator();\n while (ite.hasNext())\n {\n int adj = ite.next();\n if (!visited[adj])\n DFS(adj);\n }\n }\n \n \n public static void main(String args[])\n {\n Graph g = new Graph(4);\n \n g.addEdge(0, 1);\n g.addEdge(0, 2);\n g.addEdge(1, 2);\n g.addEdge(2, 3);\n \n System.out.println(\"Following is Depth First Traversal\");\n \n g.DFS(2);\n }\n}","type":"unstyled","key":"4b67q"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"DFS в Python","type":"header-two","key":"clp90"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"def dfs(graph, start, visited=None):\n if visited is None:\n visited = set()\n visited.add(start)\n print(start)\n for next in graph[start] - visited:\n dfs(graph, next, visited)\n return visited\n \ngraph = {'0': set(['1', '2']),\n '1': set(['0', '3', '4']),\n '2': set(['0']),\n '3': set(['1']),\n '4': set(['2', '3'])}\n \ndfs(graph, '0')","type":"unstyled","key":"35ofl"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"marker","key":"A29eLyyoxKOaYwUD33my"}],"entityMap":{}},"mentions":[]}