ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

Graph Traversal: Depth-First Search with Stack

Go

Goal -- WPM

Ready
Exercise Algorithm Area
1package main

2

3import (

4	"fmt"

5)

6

7// Graph represents an adjacency list graph.

8type Graph struct {

9	Nodes map[string][]string

10}

11

12// NewGraph creates a new graph.

13func NewGraph() *Graph {

14	return &Graph{Nodes: make(map[string][]string)}

15}

16

17// AddEdge adds a directed edge from src to dest.

18func (g *Graph) AddEdge(src, dest string) {

19	g.Nodes[src] = append(g.Nodes[src], dest)

20}

21

22// DFS performs a Depth-First Search using an explicit stack.

23// It returns a slice of visited nodes in DFS order.

24func (g *Graph) DFS(startNode string) []string {

25	visited := make(map[string]bool)

26	stack := []string{}

27	result := []string{}

28

29	// Handle case where startNode is not in the graph.

30	if _, exists := g.Nodes[startNode]; !exists {

31		return result

32	}

33

34	stack = append(stack, startNode)

35

36	for len(stack) > 0 {

37		// Pop a node from the stack

38		currentNode := stack[len(stack)-1]

39		stack = stack[:len(stack)-1]

40

41		// If already visited, skip.

42		if visited[currentNode] {

43			continue

44		}

45

46		// Mark as visited and add to result

47		visited[currentNode] = true

48		result = append(result, currentNode)

49

50		// Push neighbors onto the stack (in reverse order to visit them in natural order)

51		neighbors := g.Nodes[currentNode]

52		for i := len(neighbors) - 1; i >= 0; i-- {

53			neighbor := neighbors[i]

54			if !visited[neighbor] {

55				stack = append(stack, neighbor)

56			}

57		}

58	}

59

60	return result

61}

62

63func main() {

64	g := NewGraph()

65	g.AddEdge("A", "B")

66	g.AddEdge("A", "C")

67	g.AddEdge("B", "D")

68	g.AddEdge("C", "E")

69	g.AddEdge("D", "F")

70	g.AddEdge("E", "F") // Added edge to test cycles

71

72	fmt.Println("DFS starting from A:")

73	visitedNodes := g.DFS("A")

74	fmt.Println(visitedNodes)

75

76	fmt.Println("DFS starting from C:")

77	visitedNodes = g.DFS("C")

78	fmt.Println(visitedNodes)

79

80	fmt.Println("DFS starting from non-existent node Z:")

81	visitedNodes = g.DFS("Z")

82	fmt.Println(visitedNodes)

83}
Algorithm description viewbox

Graph Traversal: Depth-First Search with Stack

Algorithm description:

This Go program implements Depth-First Search (DFS) using an explicit stack. DFS explores as far as possible along each branch before backtracking. It's used for topological sorting, finding connected components, and cycle detection in graphs.

Algorithm explanation:

The `DFS` function simulates DFS using a slice as a stack. It starts by pushing the `startNode` onto the stack. In a loop, it pops a node, checks if it's already visited. If not, it marks it as visited, adds it to the result, and then pushes all its unvisited neighbors onto the stack. Pushing neighbors in reverse order ensures that they are processed in the order they appear in the adjacency list. The `visited` map prevents infinite loops in graphs with cycles. An edge case for a non-existent `startNode` is handled. The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, as each vertex and edge is visited at most once. The space complexity is O(V) in the worst case for the stack and visited map.

Pseudocode:

function DFS(graph, startNode):
  initialize visited set
  initialize stack
  initialize result list

  if startNode is not in graph:
    return empty result list

  push startNode onto stack

  while stack is not empty:
    currentNode = pop from stack

    if currentNode is visited:
      continue

    mark currentNode as visited
    add currentNode to result list

    get neighbors of currentNode
    for each neighbor in reverse order:
      if neighbor is not visited:
        push neighbor onto stack

  return result list
end function