3.1 Graphs

Congratulations for making it this far and into the Optional section!

NOTE: For the Indian High Schooler who views CS as an integral part of his life, this Artifice (Art.3) could be viewed as a means to prepare for the Indian Computing Olympiad (ZCO-INOI-IOITC-IOI) which happens to be the Indian Selection process to the International Olympiad of Informatics, which in turn happens to be the most prestigious stage in CS for high-Schoolers across the Globe!

Here, We’d mostly be talking about some of the more complex constructs in the World of Algorithms and Data Structures, Starting with a Graph.

A Graph in the traditional sense may mean to you as a bar graph, A Chart or a Diagram but in CS, a graph is something different.

Graphs in CS are defined as structures of the following type:

       

Here, All we want to represent is how you may reach from a node to another, It may confuse you like that, so instead consider this example:

Suppose that there’s a guy named Anubhav, and he has friends named Ritik, Himanushu and Sanskriti, and he connects with them on any form of Social Network (maybe Facebook!) and each one of those friends in turn connect to their friends with arbitrary names on the Network, forming a structure like the one below:

As you notice, This List of friends may go on and on, And thus. We may relate Anubhav with Saloni or Mia because they are the friends of his friends’ .

Now, Lets say we had to represent this structure shown above in a Computer.

We could go about doing in that in multiple ways, but one of the way, which also happens to be the most accepted one is the following:

We’ll store it as Graph denoted by ‘G’, The graph could be declared as a type, the graph would further have two other components namely its Vertices and its Edges.

Vertices are the nodes, for Example in the above graph Anubhav, Himanshu, Rizwan, Farhan etc. are to be called vertices.

Edges are like a way we could move from or relate two vertices, in the following graph the line between anyone of the two nodes, could be called an edge. We may even happen other properties related with an edge stored along with it, for eg. We may want to store in the above example the connection between Anubhav and Himanushu(if they are friends from work or Family Friends or School Friends), this could be done by further associating every edge with other attributes.

We denote the set of all the edges in a Graph by ‘E’, the set of all the Vertices by ‘V’ and the Graph itself by ‘G’.

Thus, It is not wrong to write that:

G = (V,E)

Keeping the following definition in mind is helpful!

Now, How do we represent such structures actually in code?

If you search online you’ll find many links on how do we store edges in Linked Lists(which are another complex data Structure defined with the help of Pointers and are similar to spirit with an array/vector ), but a rather easy and more efficient way would be to use vectors in C++ alongwith certain type definitions, which we’ll see in the next section as we see how to implement a very important algorithm on Graphs!