Graphs

Identification

Graph Basics

• Graphs consist of nodes and edges where a path leads from node a to node b and its length is n edges
• A path is a cycle, if the first and last nodes are the same
• A graph is connected if there is a path between any two nodes
• A tree is a graph that has n nodes and n-1 edges
• Edges can be directed or weighted
• Two nodes are neighbours if there is an edge between them

Solving Steps

1. Choose graph representation
   1. Adjacency List
   2. Adjacency Matrix
2. Choose traversal technique
   1. Breadth First Search
   2. Depth First Search
   3. Dijkstras Algorithm
   4. Bellman-Ford Algorithm
   5. A* Algorithm
3. Implement a flavour on top of our technique
   1. Backtracking (if DFS)?
   2. Topological Sort