Graph problems

kumaya · kumaya · commit 6b4bd209be39 · 2019-04-05T20:22:37.000+05:30
- Kruskals algorithm
- Cycle in a graph
diff --git a/graph/cycle.py b/graph/cycle.py
@@ -0,0 +1,49 @@
+# detect cycle in an undirected graph
+from collections import defaultdict
+
+
+class Graph(object):
+    def __init__(self, v):
+        self.vertices = v
+        self.graph = defaultdict(list)
+
+    def addEdge(self, u, v):
+        self.graph[u].append(v)
+
+    def get_parent(self, parent, i):
+        if parent[i] == -1:
+            return i
+        # else fetch top level parent
+        return self.get_parent(parent, parent[i])
+
+    # establish a parent child relationship between u,v if there does not
+    # exists any
+    def union(self, parent, x, y):
+        x_p = self.get_parent(parent, x)
+        y_p = self.get_parent(parent, y)
+        parent[x_p] = y_p
+
+    def has_cycle(self):
+        parent = [-1]*self.vertices
+        for i in self.graph:
+            for j in self.graph[i]:
+                x = self.get_parent(parent, i)
+                y = self.get_parent(parent, j)
+                if x == y:
+                    return True
+                else:
+                    self.union(parent, x, y)
+        return False
+
+
+if __name__ == '__main__':
+    g = Graph(3)
+    g.addEdge(0, 1)
+    g.addEdge(0, 2)
+    g.addEdge(2, 1)
+
+    cycle = g.has_cycle()
+    if cycle:
+        print "Cyclic"
+    else:
+        print "Acyclic"
diff --git a/graph/dfs.py b/graph/dfs.py
@@ -30,6 +30,15 @@ def dfs(v):
                 stack.append(i)
 
 
+def dfs_recursion(v):
+    v.visited = True
+    print v.data,
+    for i in v.next_vertex:
+        # print "==", i.data, i.visited
+        if not i.visited:
+            dfs_recursion(i)
+
+
 if __name__ == '__main__':
     v0 = Vertex(10)
     v1 = Vertex(11)
@@ -42,4 +51,7 @@ def dfs(v):
     v2.next_vertex = v3
     v3.next_vertex = v3
 
-    dfs(v2)
+    # dfs(v2)
+    print ""
+    # Comment either call before running.
+    dfs_recursion(v2)
diff --git a/graph/kruskalsMST.py b/graph/kruskalsMST.py
@@ -0,0 +1,71 @@
+class Graph(object):
+    def __init__(self, v):
+        self.vertices = v
+        self.graph = []
+
+    def add_edge(self, u, v, weight):
+        self.graph.append([u, v, weight])
+
+    def get_parent(self, parent, i):
+        if parent[i] == i:
+            return i
+        return self.get_parent(parent, parent[i])
+
+    # establish parent child relation if not exists
+    def union(self, parent, x, y):
+        x_p = self.get_parent(parent, x)
+        y_p = self.get_parent(parent, y)
+        parent[x_p] = y_p
+
+    def kruskals(self):
+        mst = []
+        parent = []
+        for i in range(self.vertices):
+            parent.append(i)
+        self.graph = sorted(self.graph, key=lambda item: item[2])
+        e = 0
+        i = 0
+        while e < self.vertices - 1:
+            u, v, w = self.graph[i]
+            i += 1
+            x = self.get_parent(parent, u)
+            y = self.get_parent(parent, v)
+            # if this edge is not part of mst add it and increase used
+            # edge count and also establish a parent child relation between u,v
+            if x != y:
+                e += 1
+                mst.append([u, v, w])
+                self.union(parent, x, y)
+            else:
+                # don't do anything as this u,v is already in mast
+                pass
+        return mst
+
+
+if __name__ == '__main__':
+    g = Graph(9)
+    g.add_edge(0, 1, 4)
+    g.add_edge(1, 2, 8)
+    g.add_edge(1, 7, 11)
+    g.add_edge(2, 3, 7)
+    g.add_edge(2, 8, 2)
+    g.add_edge(2, 5, 4)
+    g.add_edge(3, 4, 9)
+    g.add_edge(3, 5, 14)
+    g.add_edge(4, 5, 10)
+    g.add_edge(5, 6, 2)
+    g.add_edge(6, 7, 1)
+    g.add_edge(6, 8, 6)
+    g.add_edge(7, 0, 8)
+    g.add_edge(7, 8, 7)
+
+    # g = Graph(4)
+    # g.add_edge(0, 1, 10)
+    # g.add_edge(0, 2, 6)
+    # g.add_edge(0, 3, 5)
+    # g.add_edge(1, 3, 15)
+    # g.add_edge(2, 3, 4)
+
+    mst = g.kruskals()
+    for u, v, weight in mst:
+        print u, "-->", v, "==", weight
