Minimum Spinning Tree

Summary A spanning tree of some graph G is a subgraph that is a tree which includes all of the vertices of G, with a minimum possible number of edges. A Minimum Spanning Tree (MST) is a spanning tree whose sum of edge weights is as small as possible. Kruskal’s Algorithm Please refer to this page for its concepts and pseudo codes. The following code…

Eulerian Path

Summary An Eulerian path is a path in a finite graph that visits every edge exactly once (allowing for revisiting vertices). An Eulerian cycle is a Eulerian path that starts and ends on the same vertex. We give the following properties without proof. An undirected graph has an Eulerian trail iif exactly 0 or 2 vertices have odd degree, its…

Lowest Common Ancestor

Summary Lowest Common Ancestor (LCA) is a typical rooted tree related problem. A simple solution is use dfs to traverse the graph from root to leaves. If at some point it is first time we find out two nodes are in the same subtree, the current node is the LCA. The solution costs O(n) time….

Shortest Path

Summary A common problem in undirected or directed graph is to calculate the shortest path between two nodes. There are several typical technologies that we could use. Floyd-Warshall Shortest paths (multiple sources) in such graphs that: Edges are undirected or directed; Edges have positive or negative weights; No circles have negative weights; It is actually…