I've been reading about the data structures a lot lately and came across this article on the website http://datastructures.itgo.com, So I though this is worth sharing on my blog. The person has neatly explained about the data structures and I am going to share some of the information available. So lets start with Graph.
Sorry! I can't give that mathematical definition, involving all those Vs and Es, for the Graphs. Rather, take it this way - a graph is a collection of some finite VERTICES and some finite EDGES which happen to connect these vertices. If I consider a given list of cities as my list of VERTICES then you can, probably, call the air routes between them as to be the EDGES for them.'
Based on this analogy, we can say that a Directed Graph is a one in which you have one way air routes and that you can not come back through that same route; means, you can fly from Delhi to Mumbai but can not come back through that same route. Similarly, if you have two way air routes between the cities then I call it, an Undirected Graph. Finally, if its not a sponsored journey then certainly you will have to bear the ticket fare, which means every route (EDGE) has some cost of journey attached and that makes it a Weighted Graph. No fare, no weight!
Directed Graph:-
Vertices(cities): A, B, C and D
Edges(routes): AB, AC, CD
Undirected Graph:-
Vertices: A, B, C, D
Edges: AB, AC, BA, CD, DC
Weighted Graph:-
Vertices: A, B, C, D
Weighted Edges: AC-10, AB-17, CD-13
You might be thinking by now, what these Graphs have to do with computers! Well, to name a few I'll give you some applications of it - in the study of information routing on computer networks (helps in finding the shortest routes); electronic circuit designing (helps to find out the electrical loops and overlaps); ticketing software uses it to find out the shortest route... Got the idea!
Note:- When I said route here, I meant the direct path between the adjacent vertices and that no other vertex is there in that path except the two adjacent vertices forming the path.
Sorry! I can't give that mathematical definition, involving all those Vs and Es, for the Graphs. Rather, take it this way - a graph is a collection of some finite VERTICES and some finite EDGES which happen to connect these vertices. If I consider a given list of cities as my list of VERTICES then you can, probably, call the air routes between them as to be the EDGES for them.'
Based on this analogy, we can say that a Directed Graph is a one in which you have one way air routes and that you can not come back through that same route; means, you can fly from Delhi to Mumbai but can not come back through that same route. Similarly, if you have two way air routes between the cities then I call it, an Undirected Graph. Finally, if its not a sponsored journey then certainly you will have to bear the ticket fare, which means every route (EDGE) has some cost of journey attached and that makes it a Weighted Graph. No fare, no weight!
 |
| Directed Graph |
 |
| Undirected Graph |
 |
| Weighted Graph |
Vertices(cities): A, B, C and D
Edges(routes): AB, AC, CD
Undirected Graph:-
Vertices: A, B, C, D
Edges: AB, AC, BA, CD, DC
Weighted Graph:-
Vertices: A, B, C, D
Weighted Edges: AC-10, AB-17, CD-13
You might be thinking by now, what these Graphs have to do with computers! Well, to name a few I'll give you some applications of it - in the study of information routing on computer networks (helps in finding the shortest routes); electronic circuit designing (helps to find out the electrical loops and overlaps); ticketing software uses it to find out the shortest route... Got the idea!
Note:- When I said route here, I meant the direct path between the adjacent vertices and that no other vertex is there in that path except the two adjacent vertices forming the path.
0 comments:
Post a Comment