Graphs are extremely useful in todays world. They are used in social networks (modeling users), recommendation engines (Netflix), advertisements targeting you, well the list just goes on. So what are they? The most basic definition of a graph would be that they are a collection of nodes or values and connections between said nodes/values. Not all nodes have to be connected to one another. Some terminology in graphs that we need to know are:
- Vertex / Vertices - the node(s) that make up a graph
- Edges - the connection between vertices
- Undirected graph - no direction to the edges (2 way connection /edges, example would be facebook friends - each other see each others content)
- Directed graph - specific direction of edges / connections between vertices (usually represented by arrows, instagram - followers only being able to see the followed content but not vice versa if they are both not following)
- Weighted Graph - edges having a value
- Unweighted Graph - edges containing no values ***3/4 can be used with 5/6 and vice versa so you can have for example a weighted directed graph or an unweighted undirected graph and all the possible combinations.
- Connected g=Graph - all nodes are reachable somehow (100% of nodes can be traversed and values can be stored)
- Disconnected Graph - when at least one node is not connected to the Graph. this sounds confusing but it's something that i read about and I'm not really sure of a use case or when it would be encountered but I feel like it's worth mentioning.
- Cyclical graph - any 3+ nodes are interconnected so that they can be traversed infinitely. This is important to know when traversing because if it is cyclical and you do not account for it you could end up in an infinite loop.
- Acyclic Graph - 3 or more nodes are not interconnected in a way in a which an infinite traversal is possible.
So as far as creating a Graph what do we need? Well we need a way to store the Vertices (nodes) as well as their edges, and we must remember they can have multiple edges and these edges can be weighted, uni or bidirectional. I know that's a lot lol. Two of the most well known and most popular ways of storing graphs and their data are:
- Adjacency Matrix - A matrix is a 2 dimensional structure generally implemented with nested arrays and store information in rows and columns. Undirected graphs will show up in a matrix in a symmetrical pattern vs non symmetrical for directed
- Adjacency List - use an array or list to store the edges of a vertex. If the vertices values are not numbers we can use a hash table to store the relevant data. Pros and cons of the two are that an Adjacency list can take up less space and it is faster to iterate over all of the edges however it can be slower to look up a specific edge. Opposites are true of an adjacency list as it takes up more space and is slower to iterate over all edges however it is generally faster to look up a specific edge.
When talking about traversing a graph all it means is visiting every vertex in a graph. We do this by visiting two older methods that we created before and that is breadth first search (BFS) and depth first search (DFS). Just remember that every tree is a graph but not every graph is a tree. In a graph there is also no root so how do you start your traversal? We would just specify a starting point or our "root". In a DFS for graphs you'd pick a node and then determine how we want to traverse. I'd suggest by lowest value and go all the way down those nodes edges and then onto the siblings. And repeat. In a BFS for graphs you'd select the "root" to start with and then a child and then those child siblings before going "down" (and remember when I say down it doesn't necessarily mean in that direction). Graph, and here is my graph class which honestly I had a relatively easier time writing traversing functions than adding / removing. I don't know why but for me it was hard to visualize a graph without looking at vertices and edges. I'll have to continue on this one for sure.
Top comments (0)