How does graph theory work and how is related to computer science?
In: Engineering
You can think of a graph as a bunch of dots on a piece of paper, with some of the dots connected by lines. Graph theory deals with describing how the dots are connected and how get between one dot and another. It deals a lot with finding paths between places. In graph theory the dots are called “nodes” and the lines are called “vertices”.
There are a lot of things in computer science that you can think of as a graph, which allows you to apply graph theory techniques to them. For example, the Internet is made up of a web of computers and router all connected to each other. So if you wanted to connect your computer to Reddit to see a silly cat picture, you’re likely to want to have the fastest or shortest route from Reddit to you. All the machines are the dots on paper, and the lines are all the cables and wires connecting those machines.
Another example is Facebook. When it suggests friends, it is basically making a graph where you are the starting node. Then your friends are nodes directly connected to you. Then their friends are nodes connected to them, and so on. So to find suggestions, Facebook starts at you and searches for every node connected to you, then connected to them, and so forth moving outwards, with the assumption that people close to you on the graph are more likely to want to friend each other.
Latest Answers