Depth First Search(DFS)

Here's a concise implementation of Depth First Search (DFS) in a high-level language like Python:

python
def dfs(graph, start):
    visited = set()
    stack = [start]
    while stack:
        vertex = stack.pop()

        if vertex not in visited:
            visited.add(vertex)
            print(vertex) # Process the vertex (or perform desired operations)

            # Explore the adjacent unvisited vertices
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    stack.append(neighbor)

# Example usage
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

dfs(graph, 'A')

In this implementation, the `dfs` function takes a graph and a starting vertex as input. It maintains a set `visited` to keep track of visited vertices and a stack to store the vertices to be explored. The algorithm repeatedly pops a vertex from the stack, marks it as visited, and processes it (you can replace the `print` statement with any desired operations on the vertex). Then, it explores the adjacent unvisited vertices by adding them to the stack. The process continues until the stack becomes empty.

Note: This implementation assumes that the graph is represented using an adjacency list, where each vertex is associated with a list of its adjacent vertices.

Algorithm

Certainly! Here's the algorithm for Depth First Search (DFS) in DAA (Design and Analysis of Algorithms):

DFS(Graph, start_vertex):
    Initialize an empty stack
    Initialize a set to store visited vertices

    Push start_vertex onto the stack

    while the stack is not empty:
        current_vertex = Pop the top vertex from the stack

        if current_vertex is not visited:
            Mark current_vertex as visited
            Process current_vertex (e.g., print, store, etc.)

            for each neighbor_vertex of current_vertex:
                if neighbor_vertex is not visited:
                    Push neighbor_vertex onto the stack

The DFS algorithm explores the vertices of a graph in a depthward motion, visiting as far as possible along each branch before backtracking. It uses a stack to keep track of the vertices to visit.

The algorithm starts by initializing an empty stack and a set to store the visited vertices. It pushes the start_vertex onto the stack.

Then, in a loop, the algorithm pops the top vertex from the stack and checks if it has been visited. If the current_vertex has not been visited, it marks it as visited, processes it (e.g., prints or stores its value), and then pushes its unvisited neighbors onto the stack.

The algorithm repeats this process until the stack becomes empty, indicating that all reachable vertices have been visited.

Note that the algorithm assumes a graph represented using an adjacency list or adjacency matrix, and it can be modified accordingly to suit different graph representations or specific requirements.

Remember to implement necessary data structures (e.g., stack) and handle graph traversal logic according to the programming language you are using to implement the algorithm.

Program

Certainly! Here's an example of a Depth First Search (DFS) program in DAA. This program performs a DFS traversal on a graph represented using an adjacency list.

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

    def dfs(self, start_vertex):
        visited = [False] * self.num_vertices
        self._dfs_recursive(start_vertex, visited)

    def _dfs_recursive(self, vertex, visited):
        visited[vertex] = True
        print(vertex, end=" ")

        for neighbor in self.adj_list[vertex]:
            if not visited[neighbor]:
                self._dfs_recursive(neighbor, visited)

# Example usage
graph = Graph(6)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
graph.add_edge(2, 5)

print("Depth First Traversal (starting from vertex 0):")
graph.dfs(0)

In this program, the `Graph` class represents an undirected graph using an adjacency list. The `num_vertices` attribute stores the number of vertices in the graph, and the `adj_list` attribute is a list of lists representing the adjacency list.

The `add_edge` method is used to add edges between vertices in the graph. It takes two vertex indices, `u` and `v`, and adds each vertex to the other's adjacency list.

The `dfs` method performs the DFS traversal. It initializes a `visited` list to keep track of visited vertices and calls the private `_dfs_recursive` method to perform the recursive traversal from the starting vertex.

The `_dfs_recursive` method is the actual implementation of the DFS traversal. It marks the current vertex as visited, prints it (or performs any desired action), and then recursively visits its unvisited neighbors.

The example usage creates a graph with 6 vertices and adds edges between them. It then performs a DFS traversal starting from vertex 0 and prints the traversal path.

Note: The program assumes that the vertices are numbered from 0 to (num_vertices - 1), and the graph is undirected. Modifying the program to suit specific graph representations or requirements is possible.

Time Complexity

The time complexity of Depth First Search (DFS) in DAA depends on the representation of the graph and the specific implementation of the algorithm.

In general, the time complexity of DFS is O(V + E), where V represents the number of vertices in the graph and E represents the number of edges.

DFS visits each vertex in the graph once and explores its adjacent vertices recursively. The time complexity is proportional to the total number of vertices and edges encountered during the traversal.

For an adjacency list representation, the time complexity is determined by the number of vertices and the sum of the sizes of all adjacency lists. In this case, the time complexity is O(V + E), as each vertex and each edge is processed once.

For an adjacency matrix representation, the time complexity is determined by the number of vertices and the size of the matrix. In this case, the time complexity is O(V^2), as each vertex is visited, and for each vertex, all other vertices are checked for adjacency.

It's important to note that the time complexity assumes that the graph is represented efficiently and that the adjacency lists or matrix can be accessed in constant time.

Additionally, the time complexity can be influenced by factors such as the presence of cycles in the graph and the specific traversal logic within the DFS implementation.

Space Complexity

The space complexity of Depth First Search (DFS) in DAA depends on the representation of the graph and the specific implementation of the algorithm.

In general, the space complexity of DFS is determined by the maximum depth of the recursion stack and the data structures used to store visited vertices and track the traversal.

For an adjacency list representation, the space complexity is typically O(V), where V represents the number of vertices in the graph. This is because the recursion stack depth in DFS is limited to the maximum depth of the graph. Additionally, a separate data structure, such as an array or set, is used to keep track of visited vertices. The space required for this data structure is proportional to the number of vertices.

For an adjacency matrix representation, the space complexity is typically O(V^2), where V represents the number of vertices. This is because an adjacency matrix requires a 2D array of size V x V to represent the connections between vertices. As a result, the space required is proportional to the square of the number of vertices.

It's important to note that the space complexity assumes that the graph is represented efficiently and that the data structures used for tracking visited vertices and the recursion stack do not consume additional space proportional to the number of edges.

Additionally, the space complexity can be influenced by factors such as the presence of cycles in the graph and the specific traversal logic within the DFS implementation.

About the Author

Silan Software

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc