#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
- instantiate graph object and add edge by - iterate over all vertices from source(1) to destination, for every dice throw, update node position plus value of position of board ( snake/subtraction or ladder/addition ) #100DaysOfCode #Java #DSA
BFS tweaked for snake and ladder board game - takes source and destination as arguments - added parents array to keep track of path to destination #100DaysOfCode #Java #DSA
backtracking function to print path to destination - as long as the parent of destination isnt -1,keep reassigning temp to prev parent and print - BFS returns integer of number of distance to destination. #100DaysOfCode #Java #DSA
#day53 of #100DaysOfCode - started with intro to depth first traversal(DFS) on graphs - its recursive, similar to preOrder tree traversal technique - different application of DFS - implementation of DFS (theoretical) #100DaysOfCode #Java #DSA
implementation of DFS (assuming one component in graph) - accepts source as entry point, mark visited - iterate over adjcencyList of source, store ref of nextNode, if nextNode not visited, make recursive call and pass nextNode as current - repeat #100DaysOfCode #Java #DSA
#day54 of #100DaysOfCode still on graph ds - cycle detection on graphs (general overview) - conditions to determine a circle in graph - back edge - white board explanation of an example of a cycle detection algorithm in graphs #100DaysOfCode #DSA #Java
implementation of cycle detection algorithm in an undirected graph -mark src, store ref of nextEl, if nextEl is not visited, recursively call function and store response - if nexEl is visited, check for backedge(true for cycle detection else, false) #100DaysOfCode #DSA #Java
#day59 of #100DaysOfCode, finally back on graph DSA treated; - cycle detection on a directed graph - problems with using the previous undirected cycle detection algorithm on a directed graph - detecting a back edge in a directed graph #100DaysOfCode #DSA #Java