Whenever we have to make a program , the things will like
1) In which form input will come
2) What will be the data structure needed
3) What will be the algo
For graphs , we can have input like
4
5
1 2
1 3
1 4
2 3
2 4
We can read this as 4 nodes , 5 edges and then nodes of each node are given
For tress the above one can also be used and also the below one
(v1(v2(v3)(v4))) as shown in previous post.
Also for tress we can use
1 A
2 B C D
3 E
3 F
A is root node , B C D are children of A , E is children of C and F of D.
Then we have already seen how we can use struct for directed tress
For graphs I have seen we generally uses 2-d matrix , it wastes memory location but is easy to work with.
For trees also we can use 2-d matrix .
There will be a small theory about how to make a given tree into binary tree : I have to understand that one.
Now to just recap the things ( it may change depending on new things as I learn)
Graph :
Input Methods
1) 4
5
1 2 2 3 1 3 1 4 3 4
2) text file has data in 2-D matrix format
Storage in memory : In 2-D format
Operations : Searching a node , finding least distance , finding largest distance , finding total distance of a graph, addition of a node and its path , deletion of a node , Degree of a node ...etc ( will be updated )
Types : Directed / Undirected ; Cyclic / Acyclic ; Simple / Multi
Directed Tree
Input Methods
1 (v0(v1(v2)))
2
1 A
2 B
3 C D E
2 F
Strorage : Struct
Operations : Addition , Deletion , traversal , height of tree , Level of a node (distance from root) , Degree of a node
In next post I will try to have some programs written for them.
For directed tree, most of the operations will be limited to Binary tree . ( As for any directed tree, we can obtain a equivalent binary tree as per book) (Still to check this)
No comments:
Post a Comment