#day47 - introduction to GRAPH DATA STRUCTURE (general overview) - real life application of graph DS - classification of graphs ( weight/direction of edges in graphs) - instances and real life applications of the 2 types of classification of graphs #100DaysOfCode #Java #DSA
- how to create a graph and store in memory (representation of graphs) - 3 representation of graphs(edgeList, adjacent matrix, adjacent list) - deeper dive into representation of graphs using edgelist #100DaysOfCode #Java #DSA
simple implementation of representation of graphs using edgeList - edge class. integers u, v, wt to represent names of a single edge object and constructor to instantiate them with params - and a toString method to return a string representation of object #100DaysOfCode #DSA
edgeList class - number of vertices, list of objects of type 'edge' - constructor to instantiate list and assign vertices to params - method to add edge object to list - toString method to print string representation of object - runner class cool #100DaysOfCode #Java #DSA
#day48 - representation of a graph using ADJACENT MATRIX (deep dive) - concept - advantages and drawbacks - implementation using java #100DaysOfCde #Java #DSA
- implementation of graph using ADJACENT MATRIX in java - V represents dimension of matrix table - 2d Boolean array to represent matrix. all element are false by default - addEdge method accepts int u, v and basically ticks true to denote connection #100DaysOfCode #Java #DSA
#day49 - representation of a graph using ADJACENT LIST (deep dive) - concept - advantages and drawbacks - implementation using java
implementation of graph using ADJACENT MATRIX - data field V and array of integers with identifier adjList - iterate over all element in array and instantiate as linkedlist objects - addEdge method to add connected node as neighbours on linkedlist #100daysOfCode #Java #DSA
#day50 of #100DaysOfCode, do I get balloons or what? - briefly covered implicit graph (another representation of graph ds) - continued with graph traversal techniques(searching a graph...) - 2 main ways of graph traversal(breadthFirst and depthFirst) #100DaysOfCode #Java #DSA
- deep dive on breadth first traversal/search(BFS) - applications of BFS - implementation of BFS (theory) - usage/application of concept of queue DS in the implementation of BFS #100DaysOfCode #Java #DSA
#day51 of #100DaysOfCode implementation of BFS in java - 2 data structures; boolean array with size of nodes and linkedlist(as queue) - start from source, add to queue, mark as visited - as long as queue isnt empty, take out frontMost node and #100DaysOfCode #Java #DSA
and print - check if current frontMost node has a 'next' element inside its adjacentList array, if yes, store reference, mark as true and push inside queue - repeat process all over again till all vertices has been visited and printed intuitive #day51 of #100DaysOfCode
BFS but code refactored to track distance of every node from source - added a distance array with size of Vertices - distance of source set to zero - distance of each node from source is basically distance of parent node from source plus 1. #100DaysOfCode #Java #DSA
#day52 of #100daysOfCode worked on an exercise - application of BFS to find the shortest path to destination (minimum number of moves to win the game) in a snake and ladder board game - problem statement analysis/determining if it is a graph problem #100daysOfCode #Java #DSA
- is graph weighted or directed, can a BFS run on it? - taking inputs ( no of Vertices/nodes, no of snakes, no of ladders, position of snakes, position of ladder, no of edges ) and constructing a graph from those inputs (adjacency list representation ) #100daysOfCode #Java #DSA
- enter inputs(Vertices, source, destination, boardArray) - snake (no of snake, head and tail positions of each snake, update boardPosition (deduction) - Ladder (no of ladders, top and bottom positions of each ladder, update boardPosition (addition) ) #100DaysOfCode #Java #DSA
