GRAPH vs TREE:
Tree is hierarchical model is shape which have one and only path between vertices. It doesn't have loops, circuit or self loops.
GRAPH TRAVERSAL:
There are many graph traversal algorithms, Graph traversal means visiting every vertex and edge exactly once in a well-defined order.
Breadth First Search (BFS):
BFS is a traversing algorithm where we can start traversing from a selected node (also known as source or starting node) and traverse the graph layerwise thus exploring the neighbour nodes (nodes which are directly connected to source node). we must then move towards the next-level neighbour nodes.
## Tips to Remember: Traverse the Graph breadthwise
Step 1: First move horizontally and visit all the nodes of the current layer
Step 2: Move to the next layer
Depth First Search (DFS):
The DFS algorithm is a recursive algorithm that uses the idea of backtracking (backtrack means when we are moving forward and there are no more nodes along the current path, we move backwards on the same path to find nodes to traverse). All the nodes will be visited on the current path till all the unvisited nodes have been traversed after which the next path will be selected.
Dijkstra's Algorithm:
Dijkstra's Algorithm allows you to calculate the shortest path between one node (you pick which one) and every other node in the graph. In Dijkstra’s algorithm , we generate a SPT (shortest path tree) with given source as root. We maintain two sets, the first set contains vertices included in shortest path tree, other set includes vertices not yet included in shortest path tree. At every step of the algorithm, we find a vertex which is in the other set (set of not yet included) and has a minimum distance from the source.
Floyd-Warshall algorithm:
The Floyd-Warshall algorithm is a shortest path algorithm for graphs. Like the Bellman-Ford algorithm or the Dijkstra's algorithm, it computes the shortest path in a graph. The Floyd-Warshall algorithm is an example of dynamic programming which means it breaks the problem down into smaller sub-problems, then combines the answers to those sub-problems to solve the big, initial problem. The idea is this: either the quickest path from A to C is the quickest path found so far from A to C, or it's the quickest path from A to B plus the quickest path from B to C.
Prim's algorithm
Prim's algorithm is a minimum spanning tree algorithm that takes a graph as input and finds the subset of the edges of that graph which:
-> form a tree that includes every vertex
-> has the minimum sum of weights among all the trees that can be formed from the graph
Kruskal's algorithm:
Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).
Linked List:
A linked list is a set of dynamically allocated nodes, arranged in such a way that each node contains one value and one pointer. The pointer always points to the next member of the list. If the pointer is NULL, then it is the last node in the list. Linked lists are the dynamic data structure that uses pointers for its implementation.
Sorting:
Sorting is any process of arranging items systematically, and has two common, yet distinct meanings: ordering: arranging items in a sequence ordered by some criterion; categorizing: grouping items with similar properties
0 Comments