# Depth First Search (DFS)

Depth First Search is executed utilizing a stack-based mechanism, commencing from a specified vertex. It systematically traverses through adjacent vertices, persisting until no further adjacent vertices remain unexplored. Here’s an example implementation of Depth First Search (DFS) algorithm:

Time Complexity: O(V + E)

Python

class Node:
def __init__(self, vertex):
self.vertex = vertex
self.next = None

class Graph:
def __init__(self, numVertices):
self.numVertices = numVertices
self.visited = [0] * numVertices

# Add edge from src to dest
newNode = Node(dest)

# Add edge from dest to src
newNode = Node(src)

def DFS(self, vertex):

self.visited[vertex] = 1
print("Visited", vertex)

while temp:
connectedVertex = temp.vertex

if self.visited[connectedVertex] == 0:
self.DFS(connectedVertex)
temp = temp.next

def printGraph(self):
for v in range(self.numVertices):
while temp:
print(temp.vertex, "->", end=" ")
temp = temp.next
print()

if __name__ == '__main__':
graph = Graph(4)

graph.printGraph()

graph.DFS(2)


C

#include <stdio.h>
#include <stdlib.h>

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

// DFS algo
void DFS(struct Graph* graph, int vertex) {

graph->visited[vertex] = 1;
printf("Visited %d \n", 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 < vertices; i++) {
graph->visited[i] = 0;
}
return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
// Add edge from src to dest
struct node* newNode = createNode(dest);

// Add edge from dest to src
newNode = createNode(src);
}

// Print the graph
void printGraph(struct Graph* graph) {
int v;
for (v = 0; v < graph->numVertices; v++) {
printf("\n Adjacency list of vertex %d\n ", v);
while (temp) {
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}

int main() {
struct Graph* graph = createGraph(4);

printGraph(graph);

DFS(graph, 2);

return 0;
}


Output

Adjacency list of vertex 0
2 -> 1 ->

2 -> 0 ->

3 -> 1 -> 0 ->

2 ->
Visited 2
Visited 3
Visited 1
Visited 0

Click to view another code.

Python

def dfs(graph, start, visited=None):
if visited is None:
visited = set()

print(start)

for next_node in graph[start] - visited:
dfs(graph, next_node, visited)
# print(start)  # Print the current node again after exploring neighbors

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


Previous
Next