Mastering Graphs and Trees: Essential Concepts and Traversal Techniques
preorder = root left right
DFS use stack = inorder= left root right
postorder = left right root
BFS use queue = print each level
Graph
Used to represent various real-world scenarios such as social networks, transportation systems, and computer networks.
A collection of nodes or vertices connected by edges.
Edges represent relationships or connections between nodes.
Edges can be directed or undirected.
Cycles (paths with the same starting and ending points) may be present.
Graph Terminology
Node: A single vertex in a graph or tree. Nodes can contain data or objects and are connected to other nodes through edges.
Edge: A line representing a connection between nodes in a graph or tree. Edges can be directed or undirected.
Depth: The length of the path from a node to the root node. The depth of a specific node is the number of edges connecting it to the root node. In a tree, the root node has a depth of 0, and the depth increases by 1 for each subsequent level.
Breadth: Although not typically used in the context of trees, breadth is a term used in breadth-first search (BFS). Nodes at the same level (depth) in the tree are visited "all at once" in BFS, which is why the term "breadth" is used. Therefore, in BFS, "breadth" refers to the level (depth) of a node in the tree, not the order of traversal.
Example
Traversal Methods
Graph traversal is generally tailored to recursive functions.
DFS Depth-First Search
Push the starting node 1 into the stack.
The stack currently contains [1].
Pop node 1 from the stack and print it.
The stack currently contains [].
Following edges a, b, and c connected to node 1, push nodes 2, 3, and 5 into the stack.
The stack currently contains [5, 3, 2].
Pop node 2 from the stack and print it.
The stack currently contains [5, 3].
Following edge d connected to node 2, push node 3 into the stack.
The stack currently contains [5, 3, 3].
Pop node 3 from the stack and print it.
The stack currently contains [5, 3].
Following edges e and f connected to node 3, push nodes 4 and 5 into the stack.
The stack currently contains [5, 4, 5].
Pop node 5 from the stack and print it.
The stack currently contains [4].
Following edge g connected to node 5, push node 4 into the stack.
The stack currently contains [4, 4].
Pop node 4 from the stack and print it.
The stack currently contains [].
As there are no more nodes to pop from the stack, the DFS traversal ends.
BFS (Breadth-First Search)
Insert the starting node 1 into the queue.
The queue now contains [1].
Remove node 1 from the queue and print it.
The queue now contains [].
Traverse the edges a, b, and c connected to node 1 and insert nodes 2, 3, and 5 into the queue, respectively.
The queue now contains [2, 3, 5].
Remove node 2 from the queue and print it.
The queue now contains [3, 5].
Traverse the edge d connected to node 2 and insert node 3 into the queue.
The queue now contains [3, 5, 3].
Remove node 3 from the queue and print it.
The queue now contains [5, 3].
Traverse the edges e and f connected to node 3 and insert nodes 4 and 5 into the queue, respectively.
The queue now contains [5, 3, 4, 5].
Remove node 5 from the queue and print it.
The queue now contains [3, 4, 5].
Traverse the edge g connected to node 5 and insert node 4 into the queue.
The queue now contains [3, 4, 3].
Remove node 3 from the queue and print it.
The queue now contains [4, 3].
Node 5 connected to node 3 has already been inserted into the queue, so it is ignored.
Remove node 4 from the queue and print it.
The queue now contains [3].
Remove node 3 from the queue and print it.
The queue now contains [].
Since there are no more nodes to be removed from the queue, the BFS search is complete.
Tree
Used to represent hierarchical structures such as file systems, organization charts, and family trees.
A type of graph.
There is only one path between any two nodes.
There are no cycles (paths that start and end at the same node).
Tree Terminology
Branch: An edge that connects a node in a tree to a root or another node. There can be multiple branches between a root and another node.
Root: The topmost node in a tree. Every other node is either a branch starting from the root or a leaf node.
Leaf: The final node in a tree that has no children. It is the last node that does not extend to any other node.
Parent: A node in a tree that has one or more child nodes. It is the node located above the current node when following the edges of the tree towards the root.
Child: A node in a tree that has a parent node. It is the node located below the current node when following the edges of the tree towards the leaves.
Example
Tree Traversal Methods
Preorder (Preorder Traversal)
Preorder traversal is a method where the root node is visited first. That is, after printing the root node, traverse the left subtree, and then the right subtree. Preorder traversal visits nodes in the following order:
Root node
Left subtree
Right subtree
- Example: Preorder: 1 2 4 5 8 9 3 6 7
Inorder (Inorder Traversal)
Inorder traversal is a method where the root node is visited in the middle. That is, after traversing the left subtree, print the root node, and then traverse the right subtree. Inorder traversal visits nodes in the following order:
Left subtree
Root node
Right subtree
- Example: Inorder: 4 2 8 5 9 1 6 3 7
Postorder (Postorder Traversal)
Postorder traversal is a method where the root node is visited last. That is, after traversing the left subtree and the right subtree, print the root node. Postorder traversal visits nodes in the following order:
Left subtree
Right subtree
Root node
- Example: Postorder: 4 8 9 5 2 6 7 3 1
Understanding these traversal methods is essential for solving various tree-related problems in computer science. Each traversal method has its unique use-cases and can be applied according to the requirements of a specific problem.