# Graph Algorithms ## Graph Traversal Methods ### Mapping All Nodes #### Depth-First Search (DFS) **Depth-first search (DFS)** explores a graph by going *as deep as possible along each branch* before backtracking. It explores in a depthward motion. > **Procedure:** > 1. Start from a chosen vertex and mark it as `visited`. > 2. Explore all adjacent vertices that have not been `visited` recursively. > 3. Repeat the process until all vertices are visited. This algorithm will yield the shortest path in an unweighted graph. #### Breadth-First Search (BFS) **Breadth-first search (BFS)** explores a graph by *visiting all the vertices of one depth level* before moving to the next level. It explores in a breadthward motion. This is often achieved through a *queue* structure, allowing the adjacent vertices at the current level to maintain priority over newly discovered ones. > **Procedure:** > 1. Start from a chosen vertex and mark it as `visited`. > 2. Explore all adjacent vertices of the current vertex and `enqueue` them. > 3. `Dequeue` a vertex and repeat the process for its adjacent vertices until the queue is empty. ### Topological Sorting ### Minimum Spanning Trees (MST) Both Prim’s & Kruskal’s algorithms result in a **minimum spanning tree (MST)**, or - Specifically, an MST is a subset of the edges of - If the graph weighted, the MST will contain the minimum possible total edge weight #### Kruskal’s Algorithm > **Procedure:** > 1. Initialize a list to store collected `edges`. > 2. Pick the smallest edge and add it to the list. > 3. Pick the next smallest edge that does not create a cycle > - Note that the edges do not need to be connected A *disjoint set* data structure can be utilized to prevent cycle formation over the course of the algorithm #### Prim’s Algorithm > **Procedure:** > 1. Initialize a list called `visited` to store traversed nodes. > 2. Pick an arbitrary node as the starting point and place it in `visited`. > 3. Choose the smallest weighted edge that connected to an unvisited node and add that node to `visited`. > 4. Repeat steps 2-3 until all nodes have been traversed. disjoint set This is a textbook example of a greedy algorithm, where it picks the best option available at that moment, even if a most optimal route may exist in the bigger picture. ### Finding The Shortest Path #### Dijkstra’s Algorithm Dijkstra’s Algorithm tells you the shortest distance from one node to every other node in a graph. It is a [[Greedy Algorithms|greedy algorithm]] which makes the most optimal **Procedure:** 1. aaa #### Bellman-Ford #### Floyd-Warshall - Distance matrix - Triple iteration (k, i, j) where k is the number of nodes traveled and (i, j) is the source → destination node being compared (? no idea of this is true :smile:) ## Union Find & Disjoint Sets ## Finding Shortest Path ### Bellman-Ford ### Floyd-Warshall