**Directed Graphs in Data Structure**

*A directed Graph G, is also known as a digraph in which each edge has a direction associated with it. An edge of a digraph is given as an ordered pair (u,v) of nodes in G. For an edge (u,v) in the given graph have some rules given below:*

*1. In the edge (u,v), edge begin from one point like u and end at another point like v. For example in the graph given below edge (A, B), edge start from node A and end at node B.*

*2. In the given edge (u,v), u is the predecessor of v and v is the successor of u. For example in the graph given below, for edge (A,B), A is the predecessor of B and B is the successor of A.*

*3. In the given edge (u,v), u and v are adjacent to each other in the graph. For example in the graph given below, for edge (A,B), A and B are adjacent to each other. similarly in the edge (B,C), B and C are adjacent to each other.*

**Basic terminology of a Directed Graph:**

**Out-degree of a node in the graph:**It means the number of edges that originate from a given node. In the above graph the out-degree of node A is 1, out-degree of B is 2,*out-degree of C is 1,*

*out-degree of D is 1,*

*out-degree of E is 1. It is denoted with outdeg(u).*

**In-degree of a node in the graph:**It means the number of edges that terminate at the given node. In the above graph the in-degree of node A is 0, in-degree of B is 1, in*-degree of C is 2, in*

*-degree of D is 2, in*

*-degree of E is 1.*

*It is denoted with indeg(u).*

**Degree of a Node :**deg(u) =*outdeg(u) + in*

*deg(u). For example in the above graph-*

*deg(A) =*

*outdeg(A) + in*

*deg(A) = 1 + 0 = 1*

*deg(B) =*

*outdeg(B) + in*

*deg(B) = 2 + 1 = 3*

**Isolated Vertex :**A vertex with degree zero is known as isolated vertex. For example, deg(u) = o, means u is an isolated vertex in the graph.

**Pendant Vertex :**A vertex with degree one is known as pendant vertex. In the above graph, A is a pendant vertex as A has degree one.

**Cut Vertex :**A vertex in a graph which when deleted remain disconnected the remaining graph. In the above graph if the edge between A and B are deleted then vertex A remain disconnected from the graph. So we can say that A is a cut vertex in the graph.

**Source Vertex :**A vertex u is known as source vertex if it has a positive out-degree but a zero in-degree. In the above graph A has*positive out-degree but a zero in-degree.*

**Sink Vertex :***A vertex u is known as sink vertex if it has a positive in-degree but a zero out-degree.*

**Thanks**

**Mukesh Rajput**
## No comments:

## Post a Comment

Thanks

Mukesh Rajput