Algorithm: Graph related Problems
What is Graph?
A graph data structure is a collection of nodes that have data and are connected to other nodes. In another word, graph can be interpreted as a collection of nodes and edges.
How to represent a Graph?
Actually there are several ways to represent graph, I would like to use my own defined graph structure.
public class MyGraph {
Set<Node> nodes;
Set<Edge> edges;
}
public class Node {
int value;
int inDegree;
int outDegree;
Set<Edge> nextEdges;
Set<Node> nextNodes;
}
public class Edge {
Node from;
Node to;
int weight;
}
Classic Graph Problems
Traversal
Traversing a graph should be the most common problems relating to graph.
There are two ways to traverse Graph, Depth First Search(DFS) or Breadth First Search(BFS).
DFS
DFS is always going to next level of node, so DFS is born to match with recursive function and stack
public class GraphDFSDemo {
Set<Node> seen = new HashSet<>();
public void dfs1(MyGraph graph) {
for(Node node: graph.nodes) {
process(node);
}
}
private void process(Node node) {
if (seen.contains(node)) {
return;
} else {
seen.add(node);
System.out.println(node.val);
}
for(Node n: node.nextNodes) {
process(n);
}
}
public void dfs2(MyGraph graph) {
Stack<Node> path = new Stack<>();
Node cur = null;
for(Node node: graph.nodes) {
if(seen.contains(node)) {
continue;
} else {
seen.add(node);
path.push(node);
}
while(!path.isEmpty()) {
cur = path.pop();
for(Node n: cur.nextNodes) {
if(seen.contains(n)) {
continue;
}
path.push(cur);
path.push(n);
seen.add(n);
}
}
}
}
}
BFS
It starts at the root of graph and visits all nodes at the current depth level before moving on to the nodes at the next depth level.
so BSF is born to match with Queue.
public class GraphBFS {
public static void bfs(MyGraph graph) {
Set<Node> seen = new HashSet<>();
Queue<Node> queue = new LinkedList<>();
Node cur;
for(Node node: graph.nodes) {
if (seen.contains(node)) {
continue;
}
seen.add(node);
queue.add(node);
while(!queue.isEmpty()) {
cur = queue.poll();
for(Node next: cur.nextNodes) {
if(!seen.contains(next)) {
queue.add(next);
seen.add(next);
}
}
}
}
}
}
Minimum Spinning Tree(MST)
MST is a subset of the edges of a connected, edge-weighted graph that connects all the nodes together without any cycles and with the minimum possible total edge weight.
There are two ways to build a MST from graph: Kruskal & Prim
Kruskal
In Kruskal algorithm, sort all edges of the given graph. Then it keeps new edges and nodes into MST if the newly added edge doesn’t form a circle.
So in implementation, we will make use of Union Find set.
public interface IUnionFind {
boolean isSameSet(Node a, Node b);
void merge(Node a, Node b);
}
public class KruskalImpl {
public static Set<Edge> buildMST(MyGraph graph) {
IUnionFind uf = new UnionFind(graph.nodes);
Set<Edge> res = new HashSet<>();
Arrays.sort(graph.edges, new Comparator<Edge>() {
@Override
public int compare(Edge e1, Edge e2) {
return e1.weight - e2.weight;
}
});
Node from, to;
for(Edge edge: graph.edges) {
from = edge.from;
to = edge.to;
if (!uf.isSameSet(from, to)) {
uf.merge(from, to);
res.add(edge);
}
}
return res;
}
}
Prim
this algorithm always starts with a single node and move through several adjacent nodes, in order to explore all of the connected edges along the way.
in prim, we also need to make use of Union Find set
public class PrimImpl {
public static Set<Edge> buildMST(MyGraph graph) {
Set<Edge> res = new HashSet<>();
Set<Edge> seenEdge = new HashSet<>();
PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {
@Override
public int compare(Edge e1, Edge e2) {
return e1.weight - e2.weight;
}
});
IUnionFind<Node> uf = new UnionFind(graph.nodes);
for(Edge edge: graph.nodes[0].nextEdges) {
pq.add(edge);
seenEdge.add(edge);
}
Edge cur;
while(!pq.isEmpty()) {
cur = pq.poll();
if(!uf.isSameSet(cur.from, cur.to)) {
uf.merge(cur.from, cur.to);
res.add(cur);
for(Edge e: cur.to.nextEdges) {
if(!seenEdge.contains(e)) {
pq.add(e);
seenEdge.add(e);
}
}
}
}
}
}
Topo Sort
this is a totally new sort way we’ve discussed so far
Topo Sort of a directed graph is a linear ordering of nodes such that for every directed edge u-v, node u comes before v in the ordering. i.e. the topo sort respect the dependency relationship in original graph
So topo sort is related to in-degree & out-degree.
there are several ways to implement this logic, I will use Map to record each node and its in-degree.
public class TopoSort {
public static List<Node> topoSort(MyGraph graph) {
Map<Node, Integer> inMap = new HashMap<>();
for(Node node: graph.nodes) {
inMap.put(node, 0);
}
for(Node node: graph.nodes) {
for(Node next: node.nextNodes) {
inMap.put(next, inMap.get(next) + 1);
}
}
Queue<Node> queue = new LinkedList<>();
for(Entry<Node, Integer> entry: inMap.getEntries()) {
if (entry.getValue() == 0) {
queue.add(entry.getKey());
}
}
List<Node> res = new ArrayList<>();
Node cur;
while(!queue.isEmpty()) {
cur = queue.poll();
res.add(cur);
inMap.removeKey(cur);
for(Node next: cur.nextNodes) {
int inDegree = inMap.get(next);
inDegree--;
if (inDegree == 0) {
queue.add(next);
} else {
inMap.put(next, inDegree);
}
}
}
return res;
}
}
Dijkstra Algorithm
Dijkstra is an algorithm for finding the shortest path between nodes in a weighted graph.
the overall logic is build & maintain a map storing all nodes and its closest distance to start node.
public class DijkstraImpl {
public static int shortestDistance(MyGraph graph, Node a, Node b) {
Map<Node, Integer> distMap = new HashMap<>();
Set<Node> seen = new HashSet<>();
disMap.put(a, 0);
Node nextNode;
int curDist = distMap.get(nextNode);
int nextDist;
while((nextNode = findNextNode(distMap, seen)) != null) {
seen.add(nextNode);
for(Edge edge: nextNode.edges) {
if (!distMap.containsKey(edge.to)) {
distMap.put(edge.to, Integer.MAX_VALUE);
}
nextDist = distMap.get(edge.to);
if (curDist + edge.weight < nextDist) {
distMap.put(edge.to, curDist + edge.weight);
}
}
}
}
private static Node findNextNode(Map<Node, Integer> distMap, Set<Node> seen) {
int minDist = Integer.MAX_VALUE;
Node res = null;
for(Entry<Node, Integer> entry: distMap.getEntries()) {
if (seen.contains(entry.getKey())) {
continue;
}
if (entry.getValue() < minDist) {
minDist = entry.getValue();
res = entry.getKey();
}
}
return res;
}
}