Graph Theory — Graph Data Structures and Traversal Algorithms Made Easy
Originally published by Jed Record on March 26th 2019 Graph Theory Graph Data Structures and Traversal Algorithms Made Easy The graphs in computer software are a little different from the bar graphs in high school. Sure, they are still a mapping of relations just represented differently. Graphs can actually help solve a really large number of problems. They can be used to solve problems in social networking, eg. finding relations between friends or friends of friends or in GPS navigation, finding an optimal route from your house to the nearest shopping center. Graphs are used regularly in robotics and AI, for example, sometimes for maintaining all the possible states a robot is allowed to be in (so they don’t break stuff or move through walls). They’re great for scheduling problems, like when to schedule traffic flow (which can be solved with graph colouring). Ahhh the list goes on, they solve so many real-world problems. Graph representations It’s real important to understand the basic concepts of a graph, even if it might be boring, it pays you back ten-fold in the long run. So I’ll start from the top.. What is a graph? Well, it has those little points on it, right? Oh yeah.. and you connect those points together somehow…..voilà you have a graph! What are those points? They are called vertices or nodes. I will be using the nodes terminology for consistency. What are the lines called? They are called edges. Ok cool, so we get what a graph is.. just nodes and edges connected in some way! Maybe looking something like this: Some other properties that help define a graph: directed — the edges only point one-way, so an example of a directed graph might be a road map only consisting of one-way streets that can you travel down. undirected — the edges point both ways, you can go up and down the road. weighted — weighted graphs have some sort of cost travelling down a particular edge. Eg. 30 mins to travel down street Y. unweighted — no cost associated with the edges. acyclic — you will never encounter the same node twice. connected — all nodes in the graph are in some way connected. If the graph was a physical model you could just pick it up and since its a connected graph it won’t fall apart. disconnected — the graph is made up of sub-graphs or it is bipartite. How do we represent this in code? My answer — Many ways. It really depends on the problem as to how you should represent your graph. Here are my two go-to’s… Adjacency Matrix An adjacency matrix is used to represent a finite graph. It is important to note that if your problem is dealing with continuous space, then there are better choices to represent your graph. So what is an adjacency matrix? It is essentially just a matrix with 1’s and 0’s. It can be sparse (mostly filled with 0’s) and each row and associated column is a node of the graph, it might look something like this: This is an N*N or “N by N” matrix. As you can see for numbers 0…to 9 over the columns, » Read More
Like to keep reading?
This article first appeared on hackernoon.com. If you'd like to keep reading, follow the white rabbit.