Pirmosios gylio paieškos (DFS) algoritmas

Turinys

Pirmojo paieškos gylio algoritmas
Pirmojo gylio paieškos pavyzdys
DFS pseudokodas (rekursinis įgyvendinimas)
DFS diegimas „Python“, „Java“ ir „C / C ++“
Pirmosios paieškos gylio sudėtingumas
DFS algoritmo taikymas

Šioje pamokoje sužinosite apie gylio pirmosios paieškos algoritmą su pavyzdžiais ir pseudokodu. Taip pat išmoksite įdiegti DFS C, Java, Python ir C ++.

Pirmoji gylio paieška arba pirmojo gylio peržiūra yra rekursinis algoritmas, skirtas ieškoti visose grafiko ar medžio duomenų struktūros viršūnėse. Perėjimas reiškia aplankyti visus grafiko mazgus.

Pirmojo paieškos gylio algoritmas

Standartinis DFS diegimas kiekvieną grafiko viršūnę priskiria vienai iš dviejų kategorijų:

Aplankyta
Nesilankė

Algoritmo tikslas yra pažymėti kiekvieną viršūnę kaip aplankytą, vengiant ciklų.

DFS algoritmas veikia taip:

Pradėkite uždėdami bet kurią iš grafiko viršūnių ant kamino.
Paimkite viršutinį kamino elementą ir įtraukite jį į aplankytą sąrašą.
Sukurkite tos viršūnės gretimų mazgų sąrašą. Pridėkite tuos, kurių nėra aplankytame sąraše, į kamino viršų.
Kartokite 2 ir 3 veiksmus, kol kaminas bus tuščias.

Pirmojo gylio paieškos pavyzdys

Pažiūrėkime, kaip veikia „Depth First Search“ algoritmas su pavyzdžiu. Mes naudojame nenukreiptą grafiką su 5 viršūnėmis.

Nenukreiptas grafikas su 5 viršūnėmis

Mes pradedame nuo 0 viršūnės, DFS algoritmas pradedamas įtraukiant jį į aplankytą sąrašą ir visas gretimas viršūnes dedant į kaminą.

Apsilankykite elemente ir įtraukite jį į aplankytą sąrašą

Tada aplankome elementą, esantį kamino viršuje, ty 1 ir einame į gretimus jo mazgus. Kadangi 0 jau aplankyta, vietoj to aplankome 2.

Apsilankykite elemento viršuje viršuje

2 viršūnėje yra neaplankyta gretima viršūnė 4, todėl mes pridedame tai prie kamino viršaus ir aplankome ją.

Po to, kai aplankėme paskutinį 3 elementą, jame nėra jokių neaplankytų gretimų mazgų, todėl mes baigėme pirmąjį grafiko perkėlimą.

DFS pseudokodas (rekursinis įgyvendinimas)

DFS pseudokodas parodytas žemiau. Funkcijoje init () atkreipkite dėmesį, kad kiekviename mazge vykdome DFS funkciją. Taip yra todėl, kad diagramoje gali būti dvi skirtingos atjungtos dalys, todėl, norėdami įsitikinti, kad mes aprėpiame kiekvieną viršūnę, mes taip pat galime paleisti DFS algoritmą kiekviename mazge.

 DFS (G, u) u.veited = true kiekvienam v ∈ G.Adj (u), jei v.visited == klaidingas DFS (G, v) init () (kiekvienam u ∈ G u.veited = false kiekvienam u ∈ G DFS (G, u))

DFS diegimas „Python“, „Java“ ir „C / C ++“

Pirmojo gylio pirmosios paieškos algoritmo kodas su pavyzdžiu parodytas žemiau. Kodas buvo supaprastintas, kad galėtume sutelkti dėmesį į algoritmą, o ne į kitas detales.

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