Lovedeep Singh

<<< Data Structures and Algorithms

Graph Basics

Graph data structure is an important data structure, this is also an underlying data structural basis in many research areas of Computer Science (Knowledge Graphs, Social Networks, etc)
Graph has some nodes/vertices which may be connected to each other with some edges (which can be directional, non directional, weighted, non weighted etc)
Infact any dynamic programming problem can be modulated as a graph problem
Graph is generally represented using adjacency matrix or adjaceny list or edge list

some pseudo ( not python ) code for traversal in a graph:
visited = {}
Depth First - going depth wise first
def dfs( graph, start ):
visit(start)
visited.add(start)
for node in graph.adj[start]:
if visited.contains(node):
continue
else
dfs(graph, node)

Breadth First - visiting nearer nodes first w.r.t. distance measured using number of edges
visited = {}
queue = {}
distance = {}
def bfs( graph, start ):
distance[start] = 0
queue.push(start)
while(queue is not empty ) :
node = queue.top()
queue.pop()
visit(node)
visited.add(node)
for x in graph.adj[node]:
if visited.contains(x):
continue
else:
queue.push(x)
distance[x] = distance[node]+1

Time Complexity for both DFS and BFS = O(E+V)
Space complexity for both = O(V)
where:
E = number of edges
V = number of vertices
DFS is bit slower and less space efficient since we are pushing and popping activation records and activation record stack may generally take up more space compared to queue

Page updated

Google Sites

Report abuse