Introduction –> A Graph is an abstract data structure that is used to implement the mathematical concept of Graphs. It is basically a collection of vertices/nodes and edges(that connects the vertices). A graph is said to be a generalized form of tree data structure, instead of having a parent-child relationship here any kind of complex relationship can exist.

Definition –> A graph G is defined as an ordered set of (V, E) where V(G) represents the set of vertices/nodes and E(G) represents the set of edges.

A graph can be directed and undirected it means in a graph between two vertices there will be a defined and undefined path.

  • Undirected Graph
  • Directed Graph

Some Basic Key Terminology of Graph –>

Adjacent nodes or neighbors –> For every edge e=(u , v) that connects the nodes u and v the nodes u and v are the endpoints and are said to be adjacent or neighbors.

Degree of a node –> Degree of a node u deg(u) is the total number of edges containing the node u.

Out-degree of a node –> Out-degree of a node u written as outdeg(u) is the number of edges that originate at u, it means a number of edges that go away from the node.

In-degree of a node –> In-degree of a node u written as indeg(u) is the number of edges that terminate at u, it means the number of edges that come in at the node.

Isolated vertex –> A vertex with degree zero.

Pendant vertex –> A vertex with degree one, is also called leaf vertex.

Cut vertex –> A vertex which when deleted would disconnect the remaining graph.

Source –> A vertex is said to source if it has a positive out-degree but a zero in-degree.

Sink –> A vertex is said to sink if it has a positive in-degree but a zero out-degree.

Reachability –> A node v is said to be reachable from node u if and only if there exists a defined directed path from node u to node v.

Representation of graph –> Representation of a graph means how to represent a graph in the computer memory, there are mainly three ways to represent the graph –

  1. Sequential representation using an adjacency matrix.
  2. Linked representation using an adjacency list that uses a linked list to store the neighbors.
  3. Multi list representation it is an extension of the linked representation.

Note –> In our next post we will discuss the graph representation part, so those who are interested please regularly visit here.

Other Posts-