#stack1 | Explore Tumblr posts and blogs

viswatechynology · 3 years ago

Text

DFS

Depth-First Search Algorithm

The depth-first search or DFS algorithm traverses or explores data structures, such as trees and graphs. The algorithm starts at the root node (in the case of a graph, you can use any random node as the root node) and examines each branch as far as possible before backtracking.

When a dead-end occurs in any iteration, the Depth First Search (DFS) method traverses a network in a deathward motion and uses a stack data structure to remember to acquire the next vertex to start a search.

Following the definition of the dfs algorithm, you will look at an example of a depth-first search method for a better understanding.

Example of Depth-First Search Algorithm

The outcome of a DFS traversal of a graph is a spanning tree. A spanning tree is a graph that is devoid of loops. To implement DFS traversal, you need to utilize a stack data structure with a maximum size equal to the total number of vertices in the graph.

To implement DFS traversal, you need to take the following stages.

Step 1: Create a stack with the total number of vertices in the graph as the size.

Step 2: Choose any vertex as the traversal’s beginning point. Push a visit to that vertex and add it to the stack.

Step 3 — Push any non-visited adjacent vertices of a vertex at the top of the stack to the top of the stack.

Step 4 — Repeat steps 3 and 4 until there are no more vertices to visit from the vertex at the top of the stack.

Step 5 — If there are no new vertices to visit, go back and pop one from the stack using backtracking.

Step 6 — Continue using steps 3, 4, and 5 until the stack is empty.

Step 7 — When the stack is entirely unoccupied, create the final spanning tree by deleting the graph’s unused edges.

Consider the following graph as an example of how to use the dfs algorithm.

Step 1: Mark vertex A as a visited source node by selecting it as a source node.

· You should push vertex A to the top of the stack.

Step 2: Any nearby unvisited vertex of vertex A, say B, should be visited.

· You should push vertex B to the top of the stack.

Step 3: From vertex C and D, visit any adjacent unvisited vertices of vertex B. Imagine you have chosen vertex C, and you want to make C a visited vertex.

· Vertex C is pushed to the top of the stack.

Step 4: You can visit any nearby unvisited vertices of vertex C, you need to select vertex D and designate it as a visited vertex.

· Vertex D is pushed to the top of the stack.

Step 5: Vertex E is the lone unvisited adjacent vertex of vertex D, thus marking it as visited.

· Vertex E should be pushed to the top of the stack.

Step 6: Vertex E’s nearby vertices, namely vertex C and D have been visited, pop vertex E from the stack.

Step 7: Now that all of vertex D’s nearby vertices, namely vertex B and C, have been visited, pop vertex D from the stack.

Step 8: Similarly, vertex C’s adjacent vertices have already been visited; therefore, pop it from the stack.

Step 9: There is no more unvisited adjacent vertex of b, thus pop it from the stack.

Step 10: All of the nearby vertices of Vertex A, B, and C, have already been visited, so pop vertex A from the stack as well.

Now, examine the pseudocode for the depth-first search algorithm in this.

Pseudocode of Depth-First Search Algorithm

Pseudocode of recursive depth-First search algorithm.

Depth_First_Search(matrix[ ][ ] ,source_node, visited, value)

{

If ( sourcce_node == value)

return true // we found the value

visited[source_node] = True

for node in matrix[source_node]:

If visited [ node ] == false

Depth_first_search ( matrix, node, visited)

end if

end for

return false //If it gets to this point, it means that all nodes have been explored.

//And we haven’t located the value yet.

}

Pseudocode of iterative depth-first search algorithm

Depth_first_Search( G, a, value): // G is graph, s is source node)

stack1 = new Stack( )

stack1.push( a ) //source node a pushed to stack

Mark a as visited

while(stack 1 is not empty): //Remove a node from the stack and begin visiting its children.

B = stack.pop( )

If ( b == value)

Return true // we found the value

Push all the uninvited adjacent nodes of node b to the Stack

For all adjacent node c of node b in graph G; //unvisited adjacent

If c is not visited :

stack.push(c)

Mark c as visited

Return false // If it gets to this point, it means that all nodes have been explored.

//And we haven’t located the value yet.

Complexity Of Depth-First Search Algorithm

The time complexity of depth-first search algorithm

If the entire graph is traversed, the temporal complexity of DFS is O(V), where V is the number of vertices.

· If the graph data structure is represented as an adjacency list, the following rules apply:

· Each vertex keeps track of all of its neighboring edges. Let’s pretend there are V vertices and E edges in the graph.

· You find all of a node’s neighbors by traversing its adjacency list only once in linear time.

· The sum of the sizes of the adjacency lists of all vertices in a directed graph is E. In this example, the temporal complexity is O(V) + O(E) = O(V + E).

· Each edge in an undirected graph appears twice. Once at either end of the edge’s adjacency list. This case’s temporal complexity will be O(V) + O (2E) O(V + E).

· If the graph is represented as adjacency matrix V x V array:

· To find all of a vertex’s outgoing edges, you will have to traverse a whole row of length V in the matrix.

· Each row in an adjacency matrix corresponds to a node in the graph; each row stores information about the edges that emerge from that vertex. As a result, DFS’s temporal complexity in this scenario is O(V * V) = O. (V2).

The space complexity of depth-first search algorithm

Because you are keeping track of the last visited vertex in a stack, the stack could grow to the size of the graph’s vertices in the worst-case scenario. As a result, the complexity of space is O. (V).

After going through the complexity of the dfs algorithm, you will now look at some of its applications.

Application Of Depth-First Search Algorithm

The minor spanning tree is produced by the DFS traversal of an unweighted graph.

1. Detecting a graph’s cycle: A graph has a cycle if and only if a back edge is visible during DFS. As a result, you may run DFS on the graph to look for rear edges.

2. Topological Sorting: Topological Sorting is mainly used to schedule jobs based on the dependencies between them. In computer science, sorting arises in instruction scheduling, ordering formula cell evaluation when recomputing formula values in spreadsheets, logic synthesis, determining the order of compilation tasks to perform in makefiles, data serialization, and resolving symbols dependencies linkers.

3. To determine if a graph is bipartite: You can use either BFS or DFS to color a new vertex opposite its parents when you first discover it. And check that each other edge does not connect two vertices of the same color. A connected component’s first vertex can be either red or black.

4. Finding Strongly Connected Components in a Graph: A directed graph is strongly connected if each vertex in the graph has a path to every other vertex.

5. Solving mazes and other puzzles with only one solution:By only including nodes the current path in the visited set, DFS is used to locate all keys to a maze.

6. Path Finding: The DFS algorithm can be customized to discover a path between two specified vertices, a and b.

· Use s as the start vertex in DFS(G, s).

· Keep track of the path between the start vertex and the current vertex using a stack S.

· Return the path as the contents of the stack as soon as destination vertex c is encountered.

Finally, in this tutorial, you will look at the code implementation of the depth-first search algorithm.

Code Implementation Of Depth-First Search Algorithm

#include <stdio.h>

#include <stdlib.h>

int source_node,Vertex,Edge,time,visited[10],Graph[10][10];

void DepthFirstSearch(int i)

{

int j;

visited[i]=1;

printf(“ %d->”,i+1);

for(j=0;j<Vertex;j++)

{

if(Graph[i][j]==1&&visited[j]==0)

DepthFirstSearch(j);

}

int main()

{

int i,j,v1,v2;

printf(“\t\t\tDepth_First_Search\n”);

printf(“Enter the number of edges:”);

scanf(“%d”,&Edge);

printf(“Enter the number of vertices:”);

scanf(“%d”,&Vertex);

for(i=0;i<Vertex;i++)

{

for(j=0;j<Vertex;j++)

Graph[i][j]=0;

}

for(i=0;i<Edge;i++)

{

printf(“Enter the edges (V1 V2) : “);

scanf(“%d%d”,&v1,&v2);

Graph[v1–1][v2–1]=1;

}

for(i=0;i<Vertex;i++)

{

for(j=0;j<Vertex;j++)

printf(“ %d “,Graph[i][j]);

printf(“\n”);

}

printf(“Enter the source: “);

scanf(“%d”,&source_node);

DepthFirstSearch(source_node-1);

return 0;

}

#DFS #explain DFS #what is DFS #benifits of DFS #DFS algorithm

1 note · View note

viswatech · 3 years ago

Text

DFS Algorithm

Depth-First Search Algorithm

Following the definition of the dfs algorithm, you will look at an example of a depth-first search method for a better understanding.

Example of Depth-First Search Algorithm

To implement DFS traversal, you need to take the following stages.

Step 1: Create a stack with the total number of vertices in the graph as the size.

Step 2: Choose any vertex as the traversal's beginning point. Push a visit to that vertex and add it to the stack.

Step 3 - Push any non-visited adjacent vertices of a vertex at the top of the stack to the top of the stack.

Step 4 - Repeat steps 3 and 4 until there are no more vertices to visit from the vertex at the top of the stack.

Step 5 - If there are no new vertices to visit, go back and pop one from the stack using backtracking.

Step 6 - Continue using steps 3, 4, and 5 until the stack is empty.

Step 7 - When the stack is entirely unoccupied, create the final spanning tree by deleting the graph's unused edges.

Consider the following graph as an example of how to use the dfs algorithm.

Step 1: Mark vertex A as a visited source node by selecting it as a source node.

· You should push vertex A to the top of the stack.

Step 2: Any nearby unvisited vertex of vertex A, say B, should be visited.

· You should push vertex B to the top of the stack.

Step 3: From vertex C and D, visit any adjacent unvisited vertices of vertex B. Imagine you have chosen vertex C, and you want to make C a visited vertex.

· Vertex C is pushed to the top of the stack.

Step 4: You can visit any nearby unvisited vertices of vertex C, you need to select vertex D and designate it as a visited vertex.

· Vertex D is pushed to the top of the stack.

Step 5: Vertex E is the lone unvisited adjacent vertex of vertex D, thus marking it as visited.

· Vertex E should be pushed to the top of the stack.

Step 6: Vertex E's nearby vertices, namely vertex C and D have been visited, pop vertex E from the stack.

Step 7: Now that all of vertex D's nearby vertices, namely vertex B and C, have been visited, pop vertex D from the stack.

Step 8: Similarly, vertex C's adjacent vertices have already been visited; therefore, pop it from the stack.

Step 9: There is no more unvisited adjacent vertex of b, thus pop it from the stack.

Step 10: All of the nearby vertices of Vertex A, B, and C, have already been visited, so pop vertex A from the stack as well.

Now, examine the pseudocode for the depth-first search algorithm in this.

Pseudocode of Depth-First Search Algorithm

Pseudocode of recursive depth-First search algorithm.

Depth_First_Search(matrix[ ][ ] ,source_node, visited, value)

{

If ( sourcce_node == value)

return true // we found the value

visited[source_node] = True

for node in matrix[source_node]:

If visited [ node ] == false

Depth_first_search ( matrix, node, visited)

end if

end for

return false //If it gets to this point, it means that all nodes have been explored.

//And we haven't located the value yet.

}

Pseudocode of iterative depth-first search algorithm

Depth_first_Search( G, a, value): // G is graph, s is source node)

stack1 = new Stack( )

stack1.push( a ) //source node a pushed to stack

Mark a as visited

while(stack 1 is not empty): //Remove a node from the stack and begin visiting its children.

B = stack.pop( )

If ( b == value)

Return true // we found the value

Push all the uninvited adjacent nodes of node b to the Stack

For all adjacent node c of node b in graph G; //unvisited adjacent

If c is not visited :

stack.push(c)

Mark c as visited

Return false // If it gets to this point, it means that all nodes have been explored.

//And we haven't located the value yet.

Complexity Of Depth-First Search Algorithm

The time complexity of depth-first search algorithm

If the entire graph is traversed, the temporal complexity of DFS is O(V), where V is the number of vertices.

· If the graph data structure is represented as an adjacency list, the following rules apply:

· Each vertex keeps track of all of its neighboring edges. Let's pretend there are V vertices and E edges in the graph.

· You find all of a node's neighbors by traversing its adjacency list only once in linear time.

· The sum of the sizes of the adjacency lists of all vertices in a directed graph is E. In this example, the temporal complexity is O(V) + O(E) = O(V + E).

· Each edge in an undirected graph appears twice. Once at either end of the edge's adjacency list. This case's temporal complexity will be O(V) + O (2E) O(V + E).

· If the graph is represented as adjacency matrix V x V array:

· To find all of a vertex's outgoing edges, you will have to traverse a whole row of length V in the matrix.

· Each row in an adjacency matrix corresponds to a node in the graph; each row stores information about the edges that emerge from that vertex. As a result, DFS's temporal complexity in this scenario is O(V * V) = O. (V2).

The space complexity of depth-first search algorithm

Because you are keeping track of the last visited vertex in a stack, the stack could grow to the size of the graph's vertices in the worst-case scenario. As a result, the complexity of space is O. (V).

After going through the complexity of the dfs algorithm, you will now look at some of its applications.

Application Of Depth-First Search Algorithm

The minor spanning tree is produced by the DFS traversal of an unweighted graph.

1. Detecting a graph's cycle: A graph has a cycle if and only if a back edge is visible during DFS. As a result, you may run DFS on the graph to look for rear edges.

4. Finding Strongly Connected Components in a Graph: A directed graph is strongly connected if each vertex in the graph has a path to every other vertex.

5. Solving mazes and other puzzles with only one solution:By only including nodes the current path in the visited set, DFS is used to locate all keys to a maze.

6. Path Finding: The DFS algorithm can be customized to discover a path between two specified vertices, a and b.

· Use s as the start vertex in DFS(G, s).

· Keep track of the path between the start vertex and the current vertex using a stack S.

· Return the path as the contents of the stack as soon as destination vertex c is encountered.

Finally, in this tutorial, you will look at the code implementation of the depth-first search algorithm.

Code Implementation Of Depth-First Search Algorithm

#include <stdio.h>

#include <stdlib.h>

int source_node,Vertex,Edge,time,visited[10],Graph[10][10];

void DepthFirstSearch(int i)

{

int j;

visited[i]=1;

printf(" %d->",i+1);

for(j=0;j<Vertex;j++)

{

if(Graph[i][j]==1&&visited[j]==0)

DepthFirstSearch(j);

}

int main()

{

int i,j,v1,v2;

printf("\t\t\tDepth_First_Search\n");

printf("Enter the number of edges:");

scanf("%d",&Edge);

printf("Enter the number of vertices:");

scanf("%d",&Vertex);

for(i=0;i<Vertex;i++)

{

for(j=0;j<Vertex;j++)

Graph[i][j]=0;

}

for(i=0;i<Edge;i++)

{

printf("Enter the edges (V1 V2) : ");

scanf("%d%d",&v1,&v2);

Graph[v1-1][v2-1]=1;

}

for(i=0;i<Vertex;i++)

{

for(j=0;j<Vertex;j++)

printf(" %d ",Graph[i][j]);

printf("\n");

}

printf("Enter the source: ");

scanf("%d",&source_node);

DepthFirstSearch(source_node-1);

return 0;

}

#explain DFS #what is DFS #examples of DFS #DFS #DFS algotithm #explain DFS algorithm #benifits of DFS

1 note · View note

coolerice2-blog · 6 years ago

Text

Immutable стек и очередь, динамический максимум стека и очереди.

Задание:

1. Создайте версии стека и очереди с динамической поддержкой максимального значения.

2. Реализуйте иммутабельный стек.

3. Реализуйте иммутабельную очередь.

1 - необходимо реализовать стек(stack1) и очередь(queue1), для которых будут вспомогательные стек(stack2) и очередь(queue2).

stack2 и queue2, в свою очередь, будут хранить текущий максимум(или минимум, если захотим) в stack1 и queue1 соответственно.

2 и 3 - необходимо реализовать стек(stack1) и очередь(queue1), которые будут immutable(readonly).

Для работы и каких-либо модификаций с такими объектами мы будем создавать копию объекта stack1 и queue1, т.е. создавать новое состояние.

Соответсвтенно, текущее состояние объектов stack1 и queue1 изменяться не будет.

Сложность задания, наверное, лежит на поверхности в виду понимания смысла и представления решения в голове почти сразу после прочтения - осталось описать алгоритм и реализовать его.

Попробую декомпозировать решение:

1 - создаем класс SimpleStack(приведу словесное описание для стека, для очереди - все аналогично и по тому же шаблону),

через List<int>(в очереди используем LinkedList<int> - по ассимптотике получаем выигрыш) реализуем в нашем классе сам стек(stack1), для этого понадобятся методы:-

- Push(int value)

- Pop() - при вызове этого метода элемент будет удаляться из обоих стеков в нашем классе

- Peek()

Далее в нашем классе нам понадобится 2-й стек(stack2), в котором мы будем хранить наибольшее значение на каждом "уровне" stack1,

для этого реализуем private-метод PushMax(int value), который будет при операции Push(int value) сравнивать значение stack1.Peek() и value, большее из них подавать в PushMax(int value)

Для удобства можем завести в нашем классе метод CurrMax(чтобы понимать, какое значение в данном стеке на данный момент наибольшее),

которое будет всегда возвращать значение stack2.Peek(), если кол-во элементов в стеке более нуля.

2(задание 3 выполняется аналогично, единственное различие в методах, которые сами по себе определяют структуру - стек или очередь)

- создаем класс ImmStack<T>, в нем для простоты реализации методов Push, Pop и Peek воспользуемся встроенным в IDE Stack<T>.

Итак, реализация будет выглядеть следующим образом:

Push(T value) будет добавлять value в неизменяемый стек и вернет новый стек

Pop() удалит верхний элемент из неизменяемого стека и вернет новый стек

Peek() просто возвращает верхний элемент стека (аналогом этого метода в очереди будет First)

Такая реализация позволяет выполнять цепочку вызовов в духе:

stack.Push(1).Push(2).Push(3); (аналогично с Pop(), но тут уже стоит учесть момент, что стек может быть уже пуст��м)

0 notes