**Directed Graph :**Hold directed edges between vertices**Undirected Graph :**Hold undirected edges between vertices.
So formally we can say that, A graph G = ( V , E ) consists of two things:- A
**set 'V'**of elements called**vertices(nodes)**. - A
**set 'E'**of edges such that each**edge**'e' in 'E' is identified with a unique unordered pair [u,v] of nodes in 'V', denoted as 'e'=[u,v]
ExamplesNow above figure shows a graph consisting of 5 round object. Therefore if we define it as per above mentioned definition it will be written as: G= ( V , E ) V = { 1,2,3,4,5} (as there are 5 numbered objects in this graph) E = {[1,2] , [1,3] ,[2,1] , [2,4] , [3,1] , [3,4] , [3,5] , [4,2] , [4,3] ,[4,5] , [5,3] , [5,4] } Now if you notice carefully the figure shows only 6 edges, where as set 'E' consists of 12 edges. This is because this graph is undirected graph, so each vertices connected to other vertices will also allows opposite relation to like [u,v] <-> [v,u]. Now lets consider another example with a few changes in same graph G= ( V , E ) V = { 1,2,3,4,5} (as there are 5 numbered objects in this graph) E = {[1,2] , [2,4] , [3,1] , [3,4] , [4,5] , [5,3] } Here set 'E' will now only contain those edges which directs to certain node, this is because it is a directed graph. for eg. there is a directed edge from node 1 to node 2, but reverse is not available there fore only one entry will be allowed in 'E' set. Next important point about graphs is how they are stored in computer? this is a little tricky work. There are two standard ways to represent a graph G= (V,E) :**A Collection of Adjacency List**: Used when 'E' is much less than '|V|^{2}'.**An Adjacency Matrix :**used when 'E' is close to '|V|^{2}'.
In above figures adjacency list of undirected and directed graphs are shown. If you are aware about data structures this adjacency list actually make used of Linked list data structure. In this we make an array of pointers and then point each index corresponding to each vertices(node) to a linked list containing all end node numbers of the edge.
In above figures adjacency matrix of undirected and directed graphs are shown. This List is basically an array of 'v' by 'v' size and fill value one on the intersection box of start node and end node. For example if we have and edge [1,2] and [2,1] in undirected graph(Left figure) then if you notice the intersection box of 'row 1' and 'column 2' is assigned value '1'. Similarly the intersection of 'row 2' and 'column 1' is also assigned value '1' and so on. Similar setup is used in directed graph.Degree of VertexThis is the most important term in graphs and is denoted differently for Directed and Undirected Graph. In case of Undirected graph the degree of vertex is the number of edges inclined to it. In case of Directed graphs the degree of vertex is categorized as: OutDegree(number of out going edges) and InDegree(number of incoming edges) |