DEV Community 👩‍💻👨‍💻

Cover image for What are Graphs in Computer Science?
KodeBae
KodeBae

Posted on • Updated on

What are Graphs in Computer Science?

Today let's talk about the "BASIC" structure of graphs as they are used in computer science. I'm going to explain this concept in simple terms but understand that graphs are a very advanced subject. This is just enough information to get you up to speed with what a graph consists of in general. Don't fault me for the simplicity of this post.

What is a Graph?

A graph is an abstract data type that is a representation of Nodes and the connections between those Nodes. So yes, a Binary Search Tree would (technically) be considered a type of graph. Today we'll touch on three types of graphs, Directed, Undirected, Cyclic graphs. These graphs actually function exactly how they sound. Directed graphs have clear directions laid out along the edges, undirected graphs do not have a clearly defined route, and cyclic graphs represent one or more different cycles. Let's take a look at the main components of graphs and how they represent data, so we can get a better grasp of how everything fits together. Take a look at the example below to see how the structure of trees differ from other graphs.

trees and graphs comparison

Vertices

A vert, or vertices, or vertexes are what we would call each individual Node in our graph. So if you see a Node, think, "this is a vert". Great! So how are the vertices connected? The vertices are connected by the edges. Every single connection between the Nodes is an edge and they can go in different directions or in no particular direction at all. Sometimes our data isn't so "structured" and sometimes it is. We can use graphs to represent our data no matter how it fits together. Let's explore this concept with a directed graph.

Directed Graphs

With directed graphs, we represent data that moves in a specified direction, but they can be bidirectional between the Nodes and move in both directions. Check out the graph below. *Note that this graph is also cyclic. ⬇️

directed graph




Now look at this graph. 'A' is a bi-directional graph, or a graph that can move in both directions. 'B' is only moving in one direction between the Nodes. ⬇️

bidirectional graph

As we can see from the image above bidirectional graphs have the ability to move in both directions.

We can use these connections to represent all different kinds of data. And this example shows us how our data flows to each of the Nodes. Time for a more imaginative example. Think about how we can use maps to direct us to buried treasure. Each Node could be a specific landmark, and each edge would be the direction we'd need to take to get to the buried treasure. There may even be multiple routes that we can take to get to the same treasure, though some routes may be faster than others. A bad analogy I know, but basically, we use the edges to guide us along the path that the Nodes have laid out via their connection to one another.

Undirected Graphs

What about the undirected graphs I mentioned before? Well, with undirected graphs, we could represent more unstructured yet measurable data. They are less structured and more abstract because the data isn't representative of a specific direction or destination like a map. The Nodes and data are still related to each other, but the specific order isn't necessarily one-dimensional. For instance the representation of LinkedIn connections. We don't need directions to represent this data. We just need to know that the Nodes are related to each other in some way.

directed and undirected graph comparison

Cyclic Graphs

With cyclic graphs, we could paint out a system of data connections. Maybe we want to represent the weather patterns throughout the year. We could use a cyclic graph to represent the temperature data of the seasons: Spring, Summer, Fall, and Winter, and then back to Spring. A graph is cyclic when you can start at one Node, move along a path, and return to the Node you started at. The first and last nodes are always the same. With cyclic graphs the edges connect in an abstract circular shape? You move through the graph via adjacent edges (or vertices). This is what represents the "cycle". The length of our cycle must always be greater than or equal to 3, or else it's not a cycle. See the picture below? This is a good example of the difference between cyclic and acyclic graphs.

cyclic graph

Conclusions:

Now you know the difference between some of the most common graphs that you will see in data structures. Is the concept more clear now? I hope so. :)

Top comments (0)

🌚 Browsing with dark mode makes you a better developer.

It's a scientific fact.