Posts Tagged ‘graphs’

## Find a path between two vertices using Python

October 16, 2010
Leave a comment

Representation of the graphs and their usage is very easy with the concept of Dictionaries in Python. Dictionaries come very handy in representing Graphs in Adjacency list form.

Here is the Python code:

def Graph(): graph={} size1=int(raw_input('Enter the size of the graph:')) for i in range(size1): node=(raw_input('Enter a node:')) adj=[] ad=(raw_input('Enter adjacent vertex:( enter -1 when done):')) while(ad!='-1'): adj.append(ad) ad=(raw_input('Enter adjacent vertex:( enter -1 when done)')) graph[node]=adj visited={} for i in graph.keys(): visited[i]=False print visited start=raw_input('Enter start vertex:') end=raw_input('Enter start vertex:') print find_path(graph,start,end) def find_path(graph,start,end, path=[]) : path=path+[start] if start==end : return path if not graph.has_key(start) : return None else : for node in graph[start] : if node not in path: newpath = find_path(graph, node, end, path) if newpath : return newpath return None def main() : Graph() if __name__=='__main__' : main()

Advertisements