Esimese otsingu (DFS) sügavusalgoritm

Lang L: none (table-of-contents)

Esimese otsingu algoritmi sügavus
Esimese otsingu sügavusnäide
DFS-i pseudokood (rekursiivne rakendamine)
DFS-i juurutamine Pythonis, Java-s ja C / C ++ -s
Sügavuse esimene otsing keerukus
DFS-i algoritmi rakendamine

Selles õpetuses saate tutvuda esimeste otsingualgoritmide näidete ja pseudokoodiga. Samuti õpid DFS-i juurutama C-s, Java-s, Pythonis ja C ++.

Sügavus esimene otsing või Sügavus esimene läbimine on rekursiivne algoritm graafiku või puu andmestruktuuri kõigi tippude otsimiseks. Läbimine tähendab graafiku kõigi sõlmede külastamist.

Esimese otsingu algoritmi sügavus

DFSi standardne juurutamine paigutab graafiku iga tipu ühte kahest kategooriast:

Külastatud
Pole külastatud

Algoritmi eesmärk on märkida iga tipp külastatuna, vältides tsükleid.

DFS-i algoritm töötab järgmiselt:

Alustuseks pange ükskõik milline graafi tipp virna otsa.
Võtke virna ülemine element ja lisage see külastatud loendisse.
Looge selle tipu külgnevate sõlmede loend. Lisage virna ülaossa need, mida pole külastatud loendis.
Korrake samme 2 ja 3, kuni virn on tühi.

Esimese otsingu sügavusnäide

Vaatame näite abil, kuidas töötab alguse Sügavus esimese otsingu algoritm. Kasutame 5 tipuga suunamata graafi.

5 tipuga suunamata graaf

Alustame tipust 0, DFS-i algoritm algab selle lisamisega loendisse Visited ja kõigi selle kõrvuti asetsevate tippude virna panemisega.

Külastage elementi ja pange see külastatud loendisse

Järgmisena külastame virna ülaosas olevat elementi 1 ja läheme selle külgnevatesse sõlmedesse. Kuna 0 on juba külastatud, siis külastame hoopis 2.

Külastage virna ülaosas asuvat elementi

Tipul 2 on külastamata külgnev tipp neljas, nii et lisame selle virna ülaossa ja külastame seda.

Pärast viimase elemendi 3 külastamist pole sellel ühtegi külastamata külgnevat sõlme, seega oleme graafiku esimese läbimise sügavus lõpule viinud.

DFS-i pseudokood (rekursiivne rakendamine)

DFS-i pseudokood on näidatud allpool. Funktsioonis init () pange tähele, et käivitame DFS-i funktsiooni igas sõlmes. Selle põhjuseks on see, et graafikul võib olla kaks erinevat lahti ühendatud osa, nii et veendumaks, et me katame iga tipu, saame DFS-i algoritmi käivitada ka igas sõlmes.

 DFS (G, u) u.visited = true iga v ∈ G.Adj (u) puhul, kui v.visited == vale DFS (G, v) init () (iga u ∈ G u.visited = false igaühele u ∈ G DFS (G, u))

DFS-i juurutamine Pythonis, Java-s ja C / C ++ -s

Allpool on näidatud sügava esimese otsingu algoritmi kood koos näitega. Koodi on lihtsustatud, et saaksime keskenduda algoritmile, mitte muudele üksikasjadele.

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