- 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

keyboard_arrow_left Previous keyboard_arrow_right Next

#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

keyboard_arrow_left Previous keyboard_arrow_right Next

#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

keyboard_arrow_left Previous keyboard_arrow_right Next

#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

keyboard_arrow_left Previous keyboard_arrow_right Next

- 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

#day60 covered; - Introduction to FLOOD FILL ALGORITHM - understanding it's usage as paint bucket tool in design tools like photoshop - understanding the problem statement of the algorithm - implementation of algorithm using the concept of graph #100DaysOfCode #Java #DSA

implementation of flood fill algorithm using DFS(recursively) - if outside image grid, or not currentColor(to be changed) or already the color(visited), return. - change to newColor from position passed in - recursively call function on cell neigbors and change colors too

runner class - 2d array passed into dfs function as image - int x,y passed in as position of cell where color change start from - current color( to be changed) - new color(to change to) - for loop to print transformed array(with new color) cool #100DaysOfCode #Java #DSA

#day61 of #100DaysOfCodechallenge implementation of flood fill algorithm using BFS(iterative approach) - Pair class to create pair object to denote position/coordinates in 2d image array - object to be inserted into queue to implement floodfill BFS #100DaysOfCode #Java #DSA

actual floodfill bfs function - push pair obj into queue, mark visited - go inside queue, remove frontmost pair and paint new color - iterate over neigbors of removed pair, if they meet conditions, push inside queue, mark visited, paint - till queue becomes empty #Java #DSA

runner class floodFill BFS - image array - postions/coordinates to start painting - current color, new color to paint to - floodFillBFS method call with required arguments - for loop to print transformed array/result sweet #100DaysOfCode #Java #DSA

#day62 of #100DaysOfCodechallenge - Topological Sorting(TP) in Graphs - understanding Directed Acyclic Graphs(DAG) - need for TP - main application and other numerous applications of TP - algorithmic approaches to TP (DFS & BFS/khan's approach) #100DaysOfCode #Java #DSA

#day63 of #100DaysOfCodechallenge covered; implementation of topological sort using DFS approach in java - iterate over all vertices, if not visited, call topologicalSort helper/recursive function, pass node as argument - helper function marks #100DaysOfCode #DSA #Java

keyboard_arrow_left Previous keyboard_arrow_right Next

node as visited, iterate over node's neighbours recursively till last neighbour, then exit the loop, add last neighbour to output list. - repeat till all element visited and added to output list - reverse list and print fairly easy #100DaysOfCode #DS #Java

#day64 of #100DaysOfCodechallenge implementation of Topological Sort using Khan/BFS approach - create indegree array - push element with 0 indegree (resolved/zero dependencies) into queue - perform BFS (track output) yea basically the 3 main steps #100DaysOfCode #DSA #Java

#day65 of #100DaysOfCodechallenge still on graph dsa, got introduced to - The Traveling Salesman Problem in graphs - understanding the problem statement of TSP - Hamiltonian Cycle and Hamiltonian Path (illustrations and difference between the two) #100DaysOfCode #Java #DSA

- relations between TSP and Hamilton Cycle - introduction to the 'concept' of Brute force Algorithm and its relation to TSP #100DaysOfCode #Java #DSA

#day66 of #100dayofcodechallenge Implementation of Traveling Salesman Problem using the Brute Force(recursive) approach in java - recursively calculate the cost of distance/journey of each node to source, compare each cost and return minimum tricky #100DaysOfCode #Java #DSA

runner class - takes 2d adjacency matrix array(best suited representation of a complete graph), visited Boolean array, currentNode, currentCount, numberOfNodes(visited cities) #100DaysOfCode #Java #DSA