Alien Dictionary

code:

 from collections import defaultdict

class Solution:

    def __init__(self):

        self.graph=defaultdict(list)

        

        

    def addEdge(self,u,v):

        self.graph[u].append(v)

        

    

    def topUtil(self,visited,i,stack):

        visited[i]=True

        

        for k in self.graph[i]:

            if visited[k]==False:

                self.topUtil(visited,k,stack)

        

        stack.append(i)    

        

        

        

    def findOrder(self,dict, N, k):

        

        for i in range(len(dict)-1):

            w1=dict[i]

            w2=dict[i+1]

            

            for j in range( min(len(w1),len(w2)) ):

                if w1[j]!=w2[j]:

                    #print(w1[j],w2[j])

                    self.addEdge(ord(w1[j])-97,ord(w2[j])-97)

                    break

                    

        #print(self.graph)

                

                    

    # top(self,k):

        visited=[False]*k

        stack=[]

        for i in range(k):

            if visited[i]==False:

                self.topUtil(visited,i,stack)

                

        ans=[]        

        while stack:

            ans.append(stack.pop())

        

        for l in range(len(ans)):

            

            ans[l]=chr(ans[l]+97)

            

        print(ans)

        

        

N = 5

K = 4

dict = ["baa","abcd","abca","cab","cad"]

g=Solution()       

g.findOrder(dict,N,K)

        

Find whether it is possible to finish all tasks or not from given dependencies Using Python

code:

from collections import defaultdict

class graph:

    def __init__(self,v):

        self.v=v

        self.graph=defaultdict(list)

        

    def addEdge(self,u,v):

        self.graph[u].append(v)

        

    

        

    def isCycleUtil(self,visited,i,recStack):

        visited[i]=True

        recStack[i]=True

        

        for j in self.graph[i]:

            if visited[j]==False:

                if self.isCycleUtil(visited,j,recStack)==True:

                    return True

            elif recStack[j]==True:

                return True

                

        recStack[i]=False

        return False

        

    def isCycle(self):

        visited=[False]*self.v

        recStack=[False]*self.v

        

        for i in range(self.v):

            if visited[i]==False:

                if self.isCycleUtil(visited,i,recStack)==True:

                    return True

                    

        return False

        

    

    def find(self):

        if self.isCycle()==True:

            return False

            

        inDegree=[0]*(self.v+1)

        

        for i in self.graph:

            for j in self.graph[i]:

                inDegree[j]+=1

               

        

        

        done=[False]*(self.v+1)

        q=[]

        

        for k in range(self.v+1):

            if inDegree[k]==0:

                q.append(k)

                done[k]=True

        

        print(inDegree)

        while q:

            t=q.pop(0)

            

            for node in self.graph[t]:

                

                done[node]=True

                inDegree[node]-=1

                if inDegree[node]==0:

                    q.append(node)

            

            

        

        for p in done:

            if p==False:

                

                return False

        return True

                

                

#Driver Code               

g=graph(4)

g.addEdge(1,0)

g.addEdge(2,1)

g.addEdge(3,2)

print(g.find())

                    

Knapsack(0/1) Problem Solution Using Python

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item or don’t pick it (0-1 property).

Code :

w=10 n=4 val=[10,40,30,50] wt=[5,4,6,3] row,col=(n,w) arr=[[0 for i in range(col+1)]for j in range(row+1)] for item in range(row): item=item+1 for capacity in range(col): capacity=capacity+1 maxWithCurr=0 maxWithoutCurr=arr[item-1][capacity] if capacity >= wt[item-1]: remaining=capacity-wt[item-1] maxWithCurr=val[item-1] maxWithCurr+=arr[item-1][remaining] arr[item][capacity]=max(maxWithCurr,maxWithoutCurr) print(arr[row][col]) print(arr)

Shortest Path Using Breadth First Search (BFS)

Shortest Path Using Breadth First Search (BFS)

Here , To find the shortest path using BFS first we have to know that the graph should always be unweighted graph .

If you know about the BFS algorithm then to find shortest path we have to add only one thing that is a dictionary named "dist" which records the distance of every node from given node As shown in below code.

Code :

from collections import defaultdict # This class represents a directed graph # using adjacency list representation class Graph: # Constructor def __init__(self): # default dictionary to store graph self.graph = defaultdict(list) # function to add an edge to graph def addEdge(self,u,v): self.graph[u].append(v) # Function to print a BFS of graph def BFS(self, s): dist=[0]*10 # Mark all the vertices as not visited visited = [False] * (len(self.graph)) # Create a queue for BFS queue = [] # Mark the source node as # visited and enqueue it queue.append(s) visited[s] = True while queue: # Dequeue a vertex from # queue and print it s = queue.pop(0) print (s, end = " ") # Get all adjacent vertices of the # dequeued vertex s. If a adjacent # has not been visited, then mark it # visited and enqueue it for i in self.graph[s]: if visited[i] == False: dist[i]=dist[s]+1 queue.append(i) visited[i] = True print(dist) # Driver code # Create a graph given in # the above diagram g = Graph() g.addEdge(0, 1) g.addEdge(1,0) g.addEdge(0, 3) g.addEdge(3,0) g.addEdge(1, 2) g.addEdge(2,1) g.addEdge(3, 7) g.addEdge(7,3) g.addEdge(3, 4) g.addEdge(4,3) g.addEdge(4, 7) g.addEdge(7,4) g.addEdge(4, 6) g.addEdge(6,4) g.addEdge(7, 6) g.addEdge(6,7) g.addEdge(6, 5) g.addEdge(5,6) print ("Following is Breadth First Traversal" " (starting from vertex 2)") g.BFS(2)