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 –
- Sequential representation using an adjacency matrix.
- Linked representation using an adjacency list that uses a linked list to store the neighbors.
- 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.
September 10, 2021 at 9:21 pm
Nice one