Straight Traversal

Definition

Definition

The Straight Traversal Algorithm is a method used in graph theory to traverse a graph by moving along edges in a straight path from one vertex to another, without revisiting any vertices

Explanation

Select a starting vertex. Then explores adjacent vertices in a systematic manner, without revisiting any vertices already visited. The algorithm employs a data structure to keep track of visited vertices and the current path. It continues until all reachable vertices have been visited or until a specific condition is met. The choice of data structure (stack or queue) may affect the order in which vertices are visited

Guidance

• Select a vertex to start the traversal
• Initialize a data structure to keep track of visited vertices and the current path
  • Explore the neighbors of the current vertex
  • Select the next vertex to visit based on a specific criteria (e.g., alphabetical order, distance, etc.)
  • Update the data structures to mark the current vertex as visited and add it to the path
  • Repeat the process until all reachable vertices have been visited
• Terminate the algorithm when all vertices have been visited or when a specific condition is met

Tips

• consider different strategies for selecting the next vertex to visit, such as depth-first or breadth-first
• implement mechanisms to detect and handle cycles in the graph to prevent infinite loops
• ensure the graph is properly represented to facilitate efficient traversal

Practice

Practice

straightTraversal(graph, startVertex):
  stack = empty stack
  visited = set() // Set to keep track of visited vertices
  path = empty list

  stack.push(startVertex)

  while stack is not empty:
    currentVertex = stack.pop()

    if currentVertex is not in visited:
      add currentVertex to visited set
      add currentVertex to path list

      for each neighbor in graph.adjacent(currentVertex):
        if neighbor is not in visited:
          stack.push(neighbor)

  return path

Solution

package main

type Node struct {
    data int
    next *Node
}

func traverseList(head *Node) {
    current := head
    for current != nil {
        fmt.Print(current.data, " ")
        current = current.next
    }
}

class Node {

  int data;
  Node next;

  Node(int data) {
    this.data = data;
    next = null;
  }
}

class LinkedListTraversal {

  static void traverseList(Node head) {
    Node current = head;
    while (current != null) {
      System.out.print(current.data + " ");
      current = current.next;
    }
  }
}

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

function traverseList(head) {
  let current = head;
  while (current !== null) {
    console.log(current.data);
    current = current.next;
  }
}

class Node(var data: Int) {
    var next: Node? = null
}

fun traverseList(head: Node?) {
    var current = head
    while (current != null) {
        print("${current.data} ")
        current = current.next
    }
}

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

def traverse_list(head):
    current = head
    while current:
        print(current.data, end=' ')
        current = current.next

struct Node {
    data: i32,
    next: Option<Box<Node>>,
}

impl Node {
    fn new(data: i32) -> Self {
        Node { data, next: None }
    }
}

fn traverse_list(mut head: Option<Box<Node>>) {
    while let Some(node) = head {
        println!("{}", node.data);
        head = node.next;
    }
}

class Node {
  data: number;
  next: Node | null;

  constructor(data: number) {
    this.data = data;
    this.next = null;
  }
}

function traverseList(head: Node | null): void {
  let current: Node | null = head;
  while (current !== null) {
    console.log(current.data);
    current = current.next;
  }
}