Syvyyden ensimmäisen haun (DFS) algoritmi

Tässä opetusohjelmassa opit syvyyden ensimmäisen haun algoritmista esimerkkien ja näennäiskoodin avulla. Opit myös toteuttamaan DFS: n C, Java, Python ja C ++.

Syvyys ensin -haku tai Syvyys ensimmäinen -liikenne on rekursiivinen algoritmi kaavion tai puun tietorakenteen kaikkien huippujen etsimiseen. Liikkuminen tarkoittaa käyntiä kaavion kaikissa solmuissa.

Syvyyden ensimmäisen haun algoritmi

Tavallinen DFS-toteutus asettaa kaavion jokaisen kärjen kahteen luokkaan:

Vieraillut
Ei käynyt

Algoritmin tarkoituksena on merkitä kukin kärkipiste vierailuksi välttäen syklejä.

DFS-algoritmi toimii seuraavasti:

Aloita asettamalla mikä tahansa kaavion pisteistä pinon päälle.
Ota pinon ylin kohde ja lisää se vierailtuun luetteloon.
Luo luettelo kyseisen kärjen vierekkäisistä solmuista. Lisää pinon yläosaan ne, jotka eivät ole vierailuluettelossa.
Toista vaiheita 2 ja 3, kunnes pino on tyhjä.

Esimerkki syvyyden ensimmäisestä hausta

Katsotaanpa, kuinka syvyyden ensimmäinen haku -algoritmi toimii esimerkin kanssa. Käytämme suuntaamatonta kuvaajaa, jossa on 5 kärkeä.

Ohjaamaton kaavio, jossa 5 kärkeä

Aloitetaan huipusta 0, DFS-algoritmi aloitetaan asettamalla se Visited-luetteloon ja asettamalla kaikki sen vierekkäiset pisteet pinoon.

Käy elementissä ja laita se vierailukohteiden luetteloon

Seuraavaksi vierailemme pinon yläosassa olevalla elementillä eli 1 ja menemme sen vierekkäisiin solmuihin. Koska 0 on jo käynyt, käymme sen sijaan 2: ssa.

Käy pinon yläosan elementissä

Vertex 2: lla on vierailematon vierekkäinen kärki 4: ssä, joten lisäämme sen pinon yläosaan ja vierailemme siinä.

Kun olemme käyneet viimeisessä elementissä 3, siinä ei ole vierailemattomia vierekkäisiä solmuja, joten olemme suorittaneet kaavion syvyyden ensimmäisen läpikulun.

DFS-näennäiskoodi (rekursiivinen toteutus)

DFS: n pseudokoodi on esitetty alla. Huomaa init () -funktiossa, että suoritamme DFS-toiminnon jokaisessa solmussa. Tämä johtuu siitä, että kaaviossa voi olla kaksi erilaista irrotettua osaa, joten varmistaaksemme, että peitämme jokaisen kärjen, voimme myös suorittaa DFS-algoritmin jokaisessa solmussa.

 DFS (G, u) u.visited = tosi jokaiselle v ∈ G.Adj (u) jos v.visited == väärä DFS (G, v) init () (jokaiselle u ∈ G u.visited = false jokaiselle u ∈ G DFS (G, u))

DFS-toteutus Pythonissa, Javassa ja C / C ++: ssa

Syvyyden ensimmäisen haun algoritmin koodi ja esimerkki on esitetty alla. Koodia on yksinkertaistettu, jotta voimme keskittyä algoritmiin muiden yksityiskohtien sijaan.

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