What is a graph? Graph traversal algorithms?

A graph is a data structure consisting of a set of nodes (vertices) and connections between them (edges). Graphs are used to model networks, routes, dependencies, and other relationships.

Main graph traversal algorithms:

• Depth-First Search (DFS): starts from a selected vertex, then recursively visits neighboring vertices, going as deep as possible along each branch before backtracking.

• Breadth-First Search (BFS): starts from a selected vertex and visits all neighboring vertices at the current level, then moves to the next level.

Example of depth-first traversal in Python:

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

visited = set()

def dfs(node):
    if node not in visited:
        print(node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(neighbour)

dfs('A')

This code will output the vertices in depth-first order starting from 'A'.