Hi 🙂 Hope all is well ? Today we will look at another exiting Data Structures called Graphs which seems to be at the core of if not all most social media systems. because of it’s efficiency and it’s complexity doesn’t really matter so far as it gets the job done in a much more in demand way. actually they’re are not complex as I mentioned earlier. so what is a graph then ?

Graphs in DSA are collection and connections of nodes, remember nodes from linked-list ? well in graphs we also use nodes to represent the points that are connected to each other and the technical word for those points or nodes in a graph is called Vertices,  a complex Tree Data structure that defies the laws of binary trees can be a map instead, probably this tree may have multiple roots or parent linking to each other, so in this case we will not refer to it as a root or parent but just nodes or vertices that are communicating to each other, in a graph not all nodes link back to each other but every node have at least one connection through what we call an Edge the edge links or connects one node to the other. There are many types of graphs out there but we can speak of the most talked about which are often two Directed and Undirected Graphs.

Undirected Graphs: in an undirected graph there are no direction pointing to any node but rather the nodes or vertices are connected to each other though the edge on to way path Paths are the route on each the edges connect to the vertices. a typical application here is how we have a social media friendship say I send a friendship request to someone to follow him, the fellow may grant my friendship request which automatically makes him my virtual friend because I have his concern on my request so in this case I link to him and he links to me. But take the case of twitter where I decide to follow someone I am fun of, this fellow may decide to ignore me and not forced to follow me back so then this becomes one way connection and that brings us to the second type of Graph Directed Graphs

Directed Graphs : in a directed graph a straight path is seen linking to vertices at least one vertex in the network is linked or links by/to another, usually in a representation Arrows (x——–>y) are used to demonstrate a directed graph where as a straight line (x———y) is used for the underacted type.

In a graph we often talk about adjacent which is how the vertices are related if a node or vertices is linked anyhow to one another the we say they are adjacent to each other. let’s think of it this way. we three users in twitter platform. ie. Me, You & your girlfriend/boyfriend everyone has one I guess 🙂 . so I followed you on your account and it happens that you don’t know who the hell I am and that’s fine, so you didn’t follow me back but your girlfriend follows you and follow her back, I do understand why though. regardless I never knew your girlfriend and she may probably never know me until I die so in this scenario you and I are adjacent and you’re equally adjacent to your GF. So in this theory your partner and I are not adjacent because we don’t relate in any way, Case Close i hope my point was clear before even I was done typing… :).

Graphs are usually represented in two ways using either

1. Adjacency Matrix where 2D (vertice1 x vertice2) are used to trace the edge paths of the graph in a matrix table. if two vertices are adjacent then it’s denoted to be 1 which means the 2D array has both the two vertices having a connection ie. a[i][j] where a is the array and i and j are the vertices of the array.

2. Adjacency List  In a list representation we reduce the graph down to a linked list where the index of the array represents a vertex and each element in its linked list represents the other vertices that form an edge with the vertex.

We also often Talk about a spanning tree in graphs

Spanning tree: A spanning tree is a sub-graph of an undirected connected graph, which includes all the vertices of the graph with a minimum possible number of edges. If a vertex is missed, then it is not a spanning tree.

What is important is know in the graph system is how a vertex is created and an edge is formed and how to remove both in a graph. let’s have a look at those in the codes below.

class Graph {
  constructor() {
    this.adjacencyList = {};
  }
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }
  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }
  removeEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
      (v) => v !== vertex2
    );
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
      (v) => v !== vertex1
    );
  }
  removeVertex(vertex) {
    while (this.adjacencyList[vertex].length) {
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
    }
    delete this.adjacencyList[vertex];
  }
}

let g = new Graph();
g.addVertex('Accra');
g.addVertex('London');
g.addVertex('Abuja');
g.addVertex('Cape Town');
g.addVertex('Hong Kong');
g.addEdge('Accra', 'London');
g.addEdge('Accra', 'Abuja');
g.addEdge('Hong Kong', 'London');
g.addEdge('Hong Kong', 'Accra');
g.addEdge('Cape Town', 'Hong Kong');
g.addEdge('Cape Town', 'Abuja');

console.log(`Graph`, g);

a graph needs only one constructor element, remember we said it can be achieved through a matrix or linked list ? here a linked list is used to push the vertex of the graph into a linked list called adjacentList. To create an edge two vertices are needed to create a path so therefore pushing the two vertices into the list will determine one edge created to link two vertices, removing a vertex is completely deleting from the list and removing the edge of the connection will mean to filter down where the is only a connection between two vertices which will eliminate those lines which do not form an edge.

There you go my friend I have shared my little though on the graph topic, please read more to supplement and enforce your understanding, this is definitely not enough to be a pro at the Topic. Until the next post Stay Safe.