Graph Algorithms

import sysclass Graph:   def __init__(self,vertices):      self.vertices = vertices      self.graph = [[0 for column in range(self.vertices)] for row in range(self.vertices)]  def minDistance(self,sptSet,distance):      minimum_distance=sys.maxsize      for i in range(len(sptSet)):      if distance[i]<minimum_distance and sptSet[i]==False:        minimum_distance=distance[i]        min_index=i      return min_index  def Dj(self,source):     sptSet = [False] *self.vertices     distance = [sys.maxsize]*self.vertices     distance[source]=0     for count in range(len(sptSet)):         u = self.minDistance(sptSet,distance)         sptSet[u]=True    for v in range(self.vertices):       if self.graph[u][v]>0 and sptSet[v]==False and distance[v]>distance[u]+self.graph[u][v]:       distance[v]=distance[u]+self.graph[u][v]       print(distance)graph = Graph(8)graph.graph= [[0, 4, 0, 0, 0, 0, 0, 8, 0],[4, 0, 8, 0, 0, 0, 0, 11, 0],[0, 8, 0, 7, 0, 4, 0, 0, 2],[0, 0, 7, 0, 9, 14, 0, 0, 0],[0, 0, 0, 9, 0, 10, 0, 0, 0],[0, 0, 4, 14, 10, 0, 2, 0, 0],[0, 0, 0, 0, 0, 2, 0, 1, 6],[8, 11, 0, 0, 0, 0, 1, 0, 7],]graph.Dj(0)
using System;class Graph{public int vertices;public int[,] graph=new int[100,100];public Graph(int vertices){this.vertices=vertices;this.graph=new int[this.vertices,this.vertices];}public int ComputeMindistance(int[] distance,bool[] sptSet){int min_index=-1;int minimum=int.MaxValue;for(int i=0;i<this.vertices;i++){if(distance[i]<=minimum && sptSet[i]==false){minimum=distance[i];min_index=i;}}return min_index;}public void Dijkarat(int source){bool[] sptSet = new bool[this.vertices];int[] distance = new int[this.vertices];for(int i=0;i<this.vertices;i++){distance[i]=int.MaxValue;sptSet[i]=false;}distance[source]=0;for(int i=0;i<sptSet.Length-1;i++){int u = ComputeMindistance(distance,sptSet);sptSet[u]=true;for(int v=0;v<this.vertices;v++){if(this.graph[u,v]>0 && sptSet[v]==false && distance[v]>distance[u]+this.graph[u,v]){distance[v]=distance[u]+this.graph[u,v];}}}for(int i=0;i<this.vertices;i++){System.Console.Write("  "+distance[i]);}}}class Tester{public static void Main(){Graph graph=new Graph(9);graph.graph=new int[,]{{0, 4, 0, 0, 0, 0, 0, 8, 0},{4, 0, 8, 0, 0, 0, 0, 11, 0},{0, 8, 0, 7, 0, 4, 0, 0, 2},{0, 0, 7, 0, 9, 14, 0, 0, 0},{0, 0, 0, 9, 0, 10, 0, 0, 0},{0, 0, 4, 14, 10, 0, 2, 0, 0},{0, 0, 0, 0, 0, 2, 0, 1, 6},{8, 11, 0, 0, 0, 0, 1, 0, 7},{0, 0, 2, 0, 0, 0, 6, 7, 0}};graph.Dijkarat(0);}}
import sysclass Graph:def __init__(self,vertices):self.vertices = verticesself.graph=[]def addEdge(self,u,v,w):self.graph.append([u,v,w])def bellMan(self,source):distance = [sys.maxsize]*self.verticesdistance[source]=0for i in range(self.vertices-1):for u,v,w in self.graph:if distance[u]!=sys.maxsize and distance[v]>distance[u]+w:distance[v]=distance[u]+wfor u,v,w in self.graph:if distance[u]!=sys.maxsize and distance[v]>distance[u]+w:print("Negative cycle present")print(distance)graph = Graph(5)graph.addEdge(0,1,-1)graph.addEdge(0,2,4)graph.addEdge(1,2,3)graph.addEdge(1,3,2)graph.addEdge(1,4,2)graph.addEdge(3,2,5)graph.addEdge(3,1,1)graph.addEdge(4,3,-3)graph.bellMan(0)
Python -------------import sysclass Graph:    def __init__(self,vertex):       self.vertex=vertex       self.graph = [[0 for x in range(vertex)] for x in range(vertex)]   def FloydW(self):      for k in range(self.vertex):        for i in range(self.vertex):          for j in range(self.vertex):               self.graph[i][j] = min(self.graph[i][j],self.graph[i][k]+self.graph[k][j])     print(self.graph)graph = Graph(4)graph.graph = [[0,5,sys.maxsize,10],[sys.maxsize,0,3,sys.maxsize],[sys.maxsize,sys.maxsize,0,1],[sys.maxsize,sys.maxsize,sys.maxsize,0]]print(graph.graph)graph.FloydW()
using System;class Floyd{public static void Main() {int[,] graph = new int[4,4]{{0,5,999,10},{999,0,3,999},{999,999,0,1},{999,999,999,0}};FloydCalculation(graph,4);}public static void FloydCalculation(int[,] graph,int vertex){for(int k=0;k<vertex;k++){for(int i=0;i<vertex;i++){for(int j=0;j<vertex;j++){graph[i,j]  = Math.Min(graph[i,j],graph[i,k]+graph[k,j]);}}}for(int i=0;i<vertex;i++){for(int j=0;j<vertex;j++){System.Console.Write(graph[i,j]+" ");}System.Console.WriteLine();}}}
  • Spanning tree — — Subset of a graph with V vertex and |V-1| edges.
import sysclass Graph:def __init__(self,vertex):self.vertex = vertexself.graph = [[0 for x in range(self.vertex)] for x in range(self.vertex)]def minimumDistance(self,mstSet,key):minimum = sys.maxsizefor v in range(self.vertex):if key[v]<minimum and mstSet[v]==False:minimum = key[v]min_index = vreturn min_indexdef printMe(self,parent):print("Edge\t Weight")for v in range(1,self.vertex):print(parent[v] ," ",v,"\t",self.graph[v][parent[v]])def calculateMst(self):key = [sys.maxsize]*self.vertexkey[0] = 0mstSet = [False] *self.vertexparent = [None] *self.vertexparent[0] =-1for count in range(self.vertex):u = self.minimumDistance(mstSet,key)mstSet[u] =Truefor v in range(self.vertex):if mstSet[v]==False and self.graph[u][v]>0 and key[v]> self.graph[u][v]:key[v] =self.graph[u][v]parent[v] = uself.printMe(parent)graph = Graph(4)graph.graph = [[0,2,0,6,0],[2,0,3,8,5],[0,3,0,0,7],[6,8,0,0,9]]graph.calculateMst()
class Graph{public int vertex;public int[,] graph;public Graph(int vertex){this.vertex = vertex;this.graph = new int[this.vertex,this.vertex];}public  int FindMin(bool[] mstSet,int[] key){int minimum = int.MaxValue;int min_index=-1;for(int i=0;i<5;i++){if(key[i]<minimum && mstSet[i]==false){minimum = key[i];min_index=i;}}return min_index;}public void printDetails(int[] parent){System.Console.WriteLine("Edge\tWeight");for(int i=1;i<5;i++){System.Console.WriteLine(parent[i]+" "+i+" \t"+this.graph[i,parent[i]]);}}public void CalculateMst(){bool[] mstSet = new bool[this.vertex];int[] key = new int[this.vertex];int[] parent = new int[this.vertex];for(int i=0;i<this.vertex;i++){mstSet[i] = false;key[i] = int.MaxValue;}key[0]=0;parent[0]=-1;for(int i=0;i<this.vertex;i++){int u = FindMin(mstSet,key);mstSet[u] = true;for(int v=0;v<this.vertex;v++){if(this.graph[u,v]>0 && mstSet[v]==false && key[v]>this.graph[u,v]){key[v] = this.graph[u,v];parent[v]=u;}}}printDetails(parent);}}class Tester{public static void Main(){Graph graph = new Graph(5);graph.graph=new int[,]{{0,2,0,6,0},{2,0,3,8,5},{0,3,0,0,7},{6,8,0,0,9},{0,5,7,9,0}};graph.CalculateMst();}}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store