A graph consists of two sets V and E.
- V is finite and non empty set of vertices
- E is a set of edges connecting two vertices.
Graphs can be directed or undirected
Directed Graph: If all the edges of a graph have specific direction then this type of graph is called directed graph.For Example: V = {1,2,3,4} and E={(1,2), (2,3), (2,4), (3,1), (4,1), (4,3)}Then Directed Graph G={V,E} represented as
Representation of Graph
Adjacency Matrix: It is the two dimensional array or matrix representation of graph. In the matrix, the element a(i,j)= 0 if there is no edge between vertex i and j; the element a(i,j)=1 if there is an edge between vertex i and j. It is also known as Static Representation of graph.
For Example : Consider the following Directed Graph. The Adjacent Matrix is
1 0 1 0 0
2 0 0 0 1
3 0 0 0 0
4 1 0 1 0Consider the following Undirected Graph. The Adjacent Matrix is
1 0 1 0 1
2 1 0 0 1
3 0 0 0 0
4 1 1 1 0
Adjacency List: It is the list representation of graphs. In this representation, if there are n vertices then there are n linked list for each vertex of graph. It is also known as Dynamic Representation of graph.
Traversing a Graphs
Exploring each vertex of the graph is known as traversing a graph. The order in which we explored the vertices depend upon what kind of data structure is used. The two common graph traversal method are
Spanning Tree
A tree T is a spanning tree of a graph G={V,E} if every vertex of G belongs to an edge in T and theedges in T form a tree. Details... 
No comments:
Post a Comment