Graph
Shown above is a simple graph. Let’s define the characteristic of the graph:
- This is a connected graph. Meaning, you can travel from anywhere to anywhere in this graph. Read further here
- This is an undirected graph. That simply means we don’t have any direction sense to the arrow connecting two nodes
- This is an unweighted graph which is a different way of saying all the edges carry equal weight
Adjacency List
An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph. Read the wiki page here.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| graph = {'A' : set(['G','B']), | |
| 'B' : set(['C','D','A']), | |
| 'C' : set(['F','D','B']), | |
| 'D' : set(['B','C']), | |
| 'E' : set(['F']), | |
| 'F' : set(['E','C']), | |
| 'G' : set(['A']), | |
| } | |
| print graph | |
| ##Output should be {'A': set(['B', 'G']), 'C': set(['B', 'D', 'F']), | |
| ## 'B': set(['A', 'C', 'D']), 'E': set(['F']), 'D': set(['C', 'B']), | |
| ## 'G': set(['A']), 'F': set(['C', 'E'])} |
Our graph is now being represented in python dictionary using set
Print Nodes of Graph
We will now transverse the graph in depth-first fashion and try to print all the elements of the graph. Let’s say we start from A, we explore all the immediate neighbors before backtracking and then turn back when there is no further nodes.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def depth_first_search(graph, start_node): | |
| visited_neighbours = set() #Keep track of the node we have visited like breadcrumbs to know the path | |
| neighbours = [start_node] #list to store the neighbors. We will start with neigbors of void, the start node | |
| while (len(neighbours) != 0): #All the elements will be transversed by the time we have this list size as zero | |
| neighbour = neighbours.pop() #pop will take out randomly any one element and deletes from the list | |
| if neighbour not in visited_neighbours: | |
| visited_neighbours.add(neighbour) | |
| new_prospected_neighbours = graph[neighbour] | |
| #Need to remove neighbours which are already visted | |
| new_neighbours = new_prospected_neighbours – visited_neighbours | |
| neighbours.extend(new_neighbours) | |
| return visited_neighbours | |
| depth_first_search(graph, 'A') | |
| #output: {'A', 'B', 'C', 'D', 'E', 'F', 'G'} |
Further Reading
Leave a Reply