graph

Graph

• Graph can be represnted by 2 ways - 2D matrix, and array of linked lists(index representing the vertex)
• weighted graph can also be represented by above
• maintain a visited array for the nodes already visited
• imp. Toplogical sort, e.g task scheduling (represent a DAG (directed acyclic graph) in a hash map with a list of connected nodes)
• imp. To find the shortest path in a weighted graph, always use BFS(polynomial time) and NOT DFS(exponential time).
• imp. for BFS, use a queue to push and pop