Implement the Special Graphs and basic algorithms for them

[yashrsharma44]

Implement all types of traversal for -

• [ ] Trees

Implement an algorithm to detect if a graph is -

• [ ] Eulerian
• [ ] Directly Acyclic Graph

[130sayan]

@yashrsharma44 @Biswajitghosh98 Can i work on the traversal in Trees and the Eulerian part?

[anishsofat]

@yashrsharma44 @Biswajitghosh98 Can I work on the algorithms to implement Bipartite and Directly Acyclic Graph?

[Biswajitghosh98]

@130sayan @anishsofat Assigned. All the best !

[130sayan]

@Biswajitghosh98 bfs and dfs have already been done for graphs. Should I do separately for Trees?

[Biswajitghosh98]

@130sayan look up Morris Traversal and implement it on Binary Trees (directed)

[yashrsharma44]

@130sayan you need to add inorder/preorder/postorder/levelorder for trees. You can use the existing dfs/bfs for your reference

[130sayan]

@Biswajitghosh98 I have to check Eulerian for directed or undirected?

[Biswajitghosh98]

@130sayan An Eulerian circuit can be made on both directed and undirected graphs. Considering the graph directed would cover both the cases.

[anishsofat]

@Biswajitghosh98 I have submitted a pull request for Bipartite Graph. In "Directly Acyclic Graph", is directly same as directed?

[Biswajitghosh98]

@anishsofat yes. Let me have a look

[130sayan]

@yashrsharma44 @Biswajitghosh98 is it necessary to use morris traversal for various traversals or can I use Stack or recursion?

[yashrsharma44]

I would suggest you to implement a Morris traversal separately, and for tree traversals, use stack.

[Biswajitghosh98]

@130sayan Morris Traversal is special in a sense that it takes O(1) space while stack or recursion call stack takes up O(logn)

[Biswajitghosh98]

@yashrsharma44 I think using Morris for inorder and pre-order would be nice instead of a separate implementation. What do you think ?

[yashrsharma44]

Let's move ahead with @Biswajitghosh98 idea

[130sayan]

Ok. Thank you