Hi friends.....
Today I am going to one of interesting topic of DSAL "GRAPH".
graph have been used in a wide variety of applications. Some of applications are computer network,the analysis of electrical circuits, finding shortest routes, project planning,identification
of chemical compounds, statistical mechanics, genetics,cybernetics, linguistics, and so on. WWW is good example of directed graph.
:> Graph can be defined as : A graph G consists of two sets V and E. The set v is finite,non-empty set of vertices. The set E is a set of pairs of vertices, these pairs are called edges. the notation we generally used for graph is G=(V,E).
The advantage of graph over other data structure is that it can represent different types of relationships, whereas tree can represent hierarchical types of relationship only. So, we can say that tree is a special case of graph.
:> Directed graph :
In directed graph each edge is represented by a directed pair(e1,r2) where e1 is tail and e2 is head. In directed graph (e1,e2) and (e2,e1) represents two different edges.
:> Undirected graph :
In undirected graph each edge is represented by same way as directed graph except here (e1,e2) and (e2,e1) represent same edge.
:> Path in a graph :
A path from any vertex U to vertex V is set of edges and vertices.
:> Cycle in a graph :
A cycle is a simple path in which source node and destination node are same.
:> Weighted graph :
In weighted graph each edge is assigned a value w(e) called weight or length of V. the weight of a path is sum of the weight of the edges in the path.
:> Graph representation :
Although several representation for graph are possible according
to nature of graph. But I am discussing only two representation
here.
1> Adjacency matrix.
2> Adjacency List.
> Adjacency matrix : In adjacency matrix we represent graph by
nxn matrix. Say i and j are vertices then if there is edge between
i and j, put 1 in matrix at position (i,j) otherwise 0.
eg.:
1 2 3 4
----------
1| 0 1 1 1
2| 1 0 1 1
3| 1 1 0 1
4| 1 1 1 0
Important note : For undirected graph the degree of any vertex i is sum of row. For directed graph the row sum is the out degree and column sum is the in-degree.
> Adjacency List : In this representation of graph, the n rows
of the adjacency matrix are represented as n linked lists.there
is one list for each vertex in G. Each node of the list, may store
a reference to the vertex corresponding to the end point of the edge.
>Graph Traversal :
There are two methods are available for graph traversal :
i)DFS (depth first search).
ii) BFS (Breadth first search ).
In DFS we visit child node first.
In BFS we visit same lavel node first then child node.
Today I am going to one of interesting topic of DSAL "GRAPH".
graph have been used in a wide variety of applications. Some of applications are computer network,the analysis of electrical circuits, finding shortest routes, project planning,identification
of chemical compounds, statistical mechanics, genetics,cybernetics, linguistics, and so on. WWW is good example of directed graph.
:> Graph can be defined as : A graph G consists of two sets V and E. The set v is finite,non-empty set of vertices. The set E is a set of pairs of vertices, these pairs are called edges. the notation we generally used for graph is G=(V,E).
The advantage of graph over other data structure is that it can represent different types of relationships, whereas tree can represent hierarchical types of relationship only. So, we can say that tree is a special case of graph.
:> Directed graph :
In directed graph each edge is represented by a directed pair(e1,r2) where e1 is tail and e2 is head. In directed graph (e1,e2) and (e2,e1) represents two different edges.
:> Undirected graph :
In undirected graph each edge is represented by same way as directed graph except here (e1,e2) and (e2,e1) represent same edge.
:> Path in a graph :
A path from any vertex U to vertex V is set of edges and vertices.
:> Cycle in a graph :
A cycle is a simple path in which source node and destination node are same.
:> Weighted graph :
In weighted graph each edge is assigned a value w(e) called weight or length of V. the weight of a path is sum of the weight of the edges in the path.
:> Graph representation :
Although several representation for graph are possible according
to nature of graph. But I am discussing only two representation
here.
1> Adjacency matrix.
2> Adjacency List.
> Adjacency matrix : In adjacency matrix we represent graph by
nxn matrix. Say i and j are vertices then if there is edge between
i and j, put 1 in matrix at position (i,j) otherwise 0.
eg.:
1 2 3 4
----------
1| 0 1 1 1
2| 1 0 1 1
3| 1 1 0 1
4| 1 1 1 0
Important note : For undirected graph the degree of any vertex i is sum of row. For directed graph the row sum is the out degree and column sum is the in-degree.
> Adjacency List : In this representation of graph, the n rows
of the adjacency matrix are represented as n linked lists.there
is one list for each vertex in G. Each node of the list, may store
a reference to the vertex corresponding to the end point of the edge.
>Graph Traversal :
There are two methods are available for graph traversal :
i)DFS (depth first search).
ii) BFS (Breadth first search ).
In DFS we visit child node first.
In BFS we visit same lavel node first then child node.
No comments:
Post a Comment