[Leetcode Pattern] - Graph Introduction

Preface

Graph is the data structure used to connect the relation between the components(node). The graph topic would be focus on the discussion like how to traverse the graph, finding the shortest path from the single node to other node, grouping the related components.

Types of the Graph

• Directed Graph: The graph contains the direction which points from one node to other nodes.

• Directed Acyclic Graph (DAG): The directed graph which doesn’t contain the cyclic path

• Undirected Graph: The graph contains the bilateral direction between the two related nodes.

• Tree: Can be treated as the special case of the graph, which should meet following condition.

  • Subset of the DAG

  • The number of the edges equals to the number of the nodes - 1

  • Not a disjoint set

Traversing the Graph

Depth First Search (DFS)

• When:

  • Request the intuitive way to traverse the graph

  • The answer is at the end of the node and the answer could be returned while the first answer is found

• How:

  • Traversing the next unvisited node first and backtracking until reaching the end

  • The traversed node would be marked as visited

Breadth First Search (BFS)

• When:

  • The count of the layer of the path is requested while traversing the graph

• How:

  • Appending the next unvisited nodes into the queue which are the nodes of next layer

  • Pop out the nodes from the queue and start to traversing the nodes which are at the same layer

  • The traversed node would be marked as visited

Topological Sorting

Finding the Appearing Order of the Nodes

Constraint

• DAG

Single Source Node

• BFS: Record the order in which nodes appear

• DFS: Record the reversed order in which nodes appear

Multiple Source Node

• Kahn’s Algorithm

  • The start nodes which have the 0 of in-degree number

  • Traversing the start nodes and the adjacent of the start nodes should minus 1 in-degree

Find the Shortest Distance From the Single Source to Other Nodes

• Dijkstra’s Algorithm

  • When: When there’s no any negative edge in the graph

  • Why: Low time complexity O(V+E*log(V))

  • How: Actually, it is a BFS and parsing the node which has the lowest cost and dynamically modifying the node’s cost from the source until all the nodes are visited (Note: using the heap as the priority queue)

• SPFA

  • What: Leveraging the property of the shortest path in the graph that the passing number of the edges must be within the number of the nodes - 1. The time complexity is O(V*E)

  • When: When there’s a negative edge contained in the graph

  • Why: Comparing with Dijkstra’s, SPFA checks every adjacent node. Because the edge between the node may contain the negative
    edge.

  • How: Using the BFS method to parse the graph with the constraint that depth can’t exceed the number of nodes - 1. We check every adjacent node if it is lower than the cost currently we recorded.

Minimum Spanning Tree (MST)

Find the Shortest Edge to Connect 2 Disjoint Set

• Kruskal’s Algorithm

• Prim’s Algorithm

Grouping the Nodes to the Disjoint Set

• Quick Union:

  • When: Given the list of the node pairs, union the each of the pairs from distributed points to construct the disjoint set