This was my 4th week in my ongoing internship and now I was getting familiar with most of the concepts being covered and also my programming skills had started getting better by the days.

This week we had started graph theory and I was quite new to this and only knew graphs in discrete mathematics and just some theory regarding vertices and edges of a graph. I would like to give some clarity regarding the graph concepts that we learned in the week.

Credits Internet

A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges.

Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, connecting the pairs of vertices.

Graph as a data structure…

We can represent mathematical graphs in data structure. They can be represented using an array of vertices. Similarly we can also represent the edges using a two dimensional array of edges.

Let us understand some basic terms related to graphs.

  1. Vertex- Each node of a graph is being represented by a vertex. These can be represented using single dimensional arrays.
  2. Edge- Edge can be defined as the line joining two vertices of a graph or the path between two nodes of a graph. These are used to traverse the graph and hence are the most important elements of the graph.
  3. Adjacency- Two nodes if connected to each other by an edge can be said as adjacent nodes and hence there is an adjacency between two of them.
  4. Path- The sequence of nodes or vertices between two distinct nodes or vertices are known as the path between two vertices. This is used to traverses between two distinct nodes and there can be many paths two travel between two given nodes.

Lets see two major ways to traverse a graph —

Depth First Search- This algorithm traverses a graph in depth-ward motion and uses a stack to remember the next vertex to start a search whenever a dead end occurs in the search.

Credits-Tutorialspoint

Breadth First Search- Breadth First Search traverses a graph in breadth-ward motion and uses a queue to remember to get the new vertex to start a search whenever a dead end occurs in any of the iteration.

Credits — Tutorialspoint

So this was all about the basic understanding of graphs which I think would be absolutely helpful for a beginner.