Graph problems look similar to tree problems, but there are a few differences.
Trees have a series of nodes. Each node may have zero, one, or multiple child nodes, but it can only be referenced from parent to child, or child to parent.
In a graph, each node is called a vertex. Each Vertex can link with other vertices. The big difference is that vertices can be linked to and from multiple other vertices, not just those immediately above or below it on the tree structure. So it loses the parent-child type relationship nomenclature of a tree. And thus we have a graph.
Additionally, some graphs allow for you to move one direction from V1 to V2, however you cannot travel from V2 to V1. Think of this like a one-way street. The link between two vertices is known as an edge, and there may be an associated distance, or other form of value, associated with that edge.
Any point, or destination, can be considered a vertex, which makes graphs a very common and popular type of problem in the real world.
If we think of each city, or destination as a vertex, and there is a distance between the two, we can start to determine what path we need to take to get from Vertex A to Vertex B. This is often how graphs are used, and why they become very important to a developer.Most graph problems can be classified as a divide and conquer as we eliminate a lot of potential opportunities since we only look at a single node at a time ignoring other child nodes. We use a similar technique to the Depth First Search, using heuristics to determine the next best vertex for us to pick. Unfortunately we are not always guaranteed a connection, or the best connection – so in a worst case scenario this becomes a brute force methodology.
Solving Graph Problems was originally found on Access 2 Learn
