Dziļās pirmās meklēšanas (DFS) algoritms

Satura rādītājs

Pirmās meklēšanas dziļuma algoritms
Pirmās meklēšanas dziļuma piemērs
DFS pseidokods (rekursīva ieviešana)
DFS ieviešana Python, Java un C / C ++
Dziļuma pirmās meklēšanas sarežģītība
DFS algoritma pielietošana

Šajā apmācībā jūs uzzināsit par dziļuma pirmās meklēšanas algoritmu ar piemēriem un pseidokodu. Jūs arī iemācīsities ieviest DFS C, Java, Python un C ++.

Pirmais dziļums Meklēšana vai Pirmais dziļums ir rekursīvs algoritms, lai meklētu visas diagrammas vai koka datu struktūras virsotnes. Traversāls nozīmē visu grafa mezglu apmeklēšanu.

Pirmās meklēšanas dziļuma algoritms

Standarta DFS ieviešana katru diagrammas virsotni iedala vienā no divām kategorijām:

Apmeklēja
Nav apmeklēts

Algoritma mērķis ir atzīmēt katru virsotni kā apmeklētu, izvairoties no cikliem.

DFS algoritms darbojas šādi:

Sāciet, uzliekot jebkuru no diagrammas virsotnēm kaudzes augšpusē.
Paņemiet kaudzes augšējo vienumu un pievienojiet to apmeklēto sarakstam.
Izveidojiet šīs virsotnes blakus esošo mezglu sarakstu. Pievienojiet tos, kas nav apmeklēto sarakstā, kaudzes augšdaļā.
Atkārtojiet 2. un 3. darbību, līdz kaudze ir tukša.

Pirmās meklēšanas dziļuma piemērs

Apskatīsim, kā darbojas dziļuma pirmās meklēšanas algoritms, ar piemēru. Mēs izmantojam nenovirzītu grafiku ar 5 virsotnēm.

Nevirzīts grafiks ar 5 virsotnēm

Mēs sākam no 0 virsotnes, DFS algoritms sākas, ievietojot to sarakstā Visited un visas blakus esošās virsotnes ievietojot kaudzē.

Apmeklējiet elementu un ievietojiet to apmeklēto sarakstā

Pēc tam mēs apmeklējam elementu kaudzes augšdaļā, ti, 1, un dodamies uz blakus esošajiem mezgliem. Tā kā 0 jau ir apmeklēts, tā vietā mēs apmeklējam 2.

Apmeklējiet elementu kaudzes augšdaļā

2. virsotnei ir neapmeklēta blakus esošā virsotne 4, tāpēc mēs to pievienojam kaudzes augšpusē un apmeklējiet to.

2. virsotnei ir neapmeklēta blakus esošā virsotne 4, tāpēc mēs to pievienojam kaudzes augšpusē un apmeklējam to.

Pēc pēdējā elementa 3 apmeklēšanas tajā nav neviena neapmeklēta blakus esošā mezgla, tāpēc mēs esam pabeiguši diagrammas pirmo dziļumu.

Pēc tam, kad esam apmeklējuši pēdējo 3. elementu, tam nav neviena neapmeklēta blakus esoša mezgla, tāpēc mēs esam pabeiguši diagrammas pirmo dziļumu.

DFS pseidokods (rekursīva ieviešana)

DFS pseidokods ir parādīts zemāk. Funkcijā init () ievērojiet, ka mēs katrā mezglā izpildām DFS funkciju. Tas ir tāpēc, ka diagrammā varētu būt divas atšķirīgas atvienotas daļas, tāpēc, lai pārliecinātos, ka mēs aptveram katru virsotni, mēs varam arī palaist DFS algoritmu katrā mezglā.

 DFS (G, u) u.visited = taisnība katram v ∈ G.Adj (u), ja v.visited == nepatiesa DFS (G, v) init () (katram u u ∈ G DFS (G, u))

DFS ieviešana Python, Java un C / C ++

Tālāk ir parādīts dziļuma pirmās meklēšanas algoritma kods ar piemēru. Kods ir vienkāršots, lai mēs varētu koncentrēties uz algoritmu, nevis citām detaļām.

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