Graph

From now on, things become really fascinating. Until now, we’ve been dealing with Linear Data Structures, but Graphs are something different. In this case we deal with Data, which is stored in hierarchical manner. Every Graph is finite set of Nodes (also called Vertices) and Edges called Links. This set is mutable, meaning its Nodes and Edges can be inserted, updated and removed.

What Makes Graph

Elements that make building blocks of every Graph are:

• Node (Vertex) - represents fundamental unit of something. It can be one person, car, city or primitive value like String or Number.

• Edge (Link) - connects one or more Nodes together. This is not required, because minimal Graph contains nothing more than single Node.

As you probably have noticed, there are only two building elements for Graphs. First, it may look like a quite small number, however when you realize what you can do with this Data Structure, it turns out to be not so tiny at all. In its minimum form, the Graph can be just a single Node. It’s not very useful I know, but maybe you can think of an example for Trivial graph?

Node

Node is really simple element. It is represented as a circle and on the drawing it may contain value it holds.

Edge

Edge is about relations between Nodes and how they are connected. Let’s start with communication direction which shows which Nodes are connected one or both ways. It is not mandatory for Graph to connect all Nodes in the set but this is still valid.

Directed Graph

Within Directed Graph (DG), Nodes communicate only in one direction. We can say, that this is a unidirectional connection between them. It is similar to chain of command in the army where orders go only one way, from commander to soldiers with lower ranks. It never happens that private gives orders to the major. More examples are shown on the figures below.

See how Edges look like when used in Directed Graph. They are ended with arrows which points the direction of the relation or communication. When we deal with a radio transmission, one Node is a station which propagates the signal. Then there are millions of receivers - tuners kept in homes, cars or in our pockets. Another good example are social networks build on the idea of followers. Person A can “follow” Person B, but B is not obliged to follow A back. Are you a part of such network?

Undirected Graph

For Nodes being elements in Undirected Graph (UG), a bidirectional relation and communication are default. Edges contain no arrows since showing two of them would be redundant and require unnecessary, additional marks. Good example of UG would be a map. Yes, this big sheet of paper containing representation of some area, like a country for that matter.

Map shows us five towns which have direct and indirect connections between them. From Dover, you can travel directly to Jersey and Bradford but if your destination is London or Bristol you need to take longer way through Jersey. Second example is a friends-based social media. If you are a member of such you know that if Person A sends you a friend request, when accepted, it makes an equal relation between you and this individual.

Weighted Graph

Edges in the Graph may have Weights attached to them. Weight can represent anything like quantity, distance or time. I think that best example which presents Weights best is the map again.

On the left-most map there are Weights on the Edges which represent distance between cities. What you can learn from this is that if you live in a Dover and want to travel Bristol, it is wise to take a road via Jersey. The distance is 103km comparing to 309km needed when riding through Bradford. After quick look at the time weights on a second map, you will agree that this is the most time and cost-efficient way to reach your destination.

Unweighted Graph

Every Graph will be called unweighted if there are no Weights defined on the Edges. This is the default form when it comes to this Data Structure.

Adjacent Nodes

Adjacent looks like a difficult word, but it’s not. When you are on the camp, and you set up a tent next to your friend’s, your tent will be adjacent to his. When it comes to Graphs we say that Nodes which are connected with an Edge are adjacent. When it comes to graphical representation of the Graph it’s quite easy to say which Node is adjacent to which, but unfortunately machines called computers will not understand our work-of-art drawings. Instead we have to feed them with something they will understand. There are two ways to achieve this.

Adjacency Matrix

First option we have, is a two-dimensional (2D) array holding information about adjacent Nodes. It is called matrix. On the picture below there is a Graph and its representation suitable for machine processing.

When you take a look at the Adjacency Matrix you will notice that cells with letters A-D represent Nodes and these with zeros and ones indicate if there is connection between them. It shows that:

• A is adjacent to C
• B lays next to C and D
• C has connection with every other Node
• D is adjacent to B and C

Adjacency List

List of adjacent Nodes consists two one-dimensional arrays. One of them stores Nodes and second holds Edges. I will use Graph from previous example for consistency’s sake.

I’m pretty sure it requires some clarification. Let’s take the A Node, it holds Index of cell which contains Node adjacent to it. Next one is B which is connected with two Nodes: C and D, therefore Node Array stores Index equal to 1 which is the beginning of the sequence containing Nodes laying next to Node B. The next one is C which is adjacent to three Nodes: A, B and D therefore it occupies three cells of the Edge Array. The last one, D, has reference to Index = 6 and lays next to Nodes B and C.

Summary

Graphs are very important Data Structures which give foundation to even more important DS which is Tree. Make sure you know Graphs by heart, so you can easily continue your journey to the last chapter of this tutorial.