Graph Adventures & Comparisons

This week I worked on two C++ programs for graph algorithms in our assignment. The first used Depth-First Search (DFS) with a stack and a mark array to show the order each vertex is visited. This helped understand how DFS explores connected vertices and why sorting each adjacency list keeps the visit order consistent. In the second part, I solved the Traveling Salesman Problem by checking all possible vertex paths to find the lowest-cost cycle. These projects were good exercises in using vectors and stacks.

Aside from programming, we covered some core algorithm topics. One of them was brute-force string matching and how best- and worst-case inputs affect its runtime. As mentioned above, depth-first search was also covered along with breadth-first graph traversals. We also covered the knapsack optimization problem and its focus on maximizing value within a capacity limit.

I wanted to go into more depth on DFS vs BFS. Depth-First Search is a fundamental graph-traversal algorithm that explores as far as possible along each branch of a graph before it backtracks. It starts from a chose source vertex and then visits a neighbor. Then it visits a neighbor of that neighbor, and so on. Breadth-First Search (BFS) is another important graph-traversal algorithm, but it explores a graph level by level instead of going in deep into any one branch. This is probably best visualized with video illustration. I'll be sharing some with the class.