Introduction

Overview#

Graphs are a generalization of trees. A graph is a set of vertices connected pairwise by edges.

Graphs can be directed. A directed edge is like a 1-way road and undirected edges are a 2-way road.

Graphs can have cycles or not.

Every tree is a graph, but not every graph is a tree.

Terminologies#

  • Undirected Graph - a graph G=(V,E) is a structure comprising a set V or vertices/nodes with a set E of edges/lines, where each edge is 2-element subset of V that relates 2 vertices.
  • V - set of vertices - V = {v1, v2, v3 ...}
  • E - set of 2-element sets consisting of v(s) - E = {e1, e2, e3 โ€ฆ} where edges are pairs of vertices (e = {v1, v2})
  • Path - Sequence of vertices connected by edges
  • Cycle - Path whose first and last vertices are the same
  • Degree - Number of edges connected to a given vertex
  • Connected vertices - 2 vertices are connected if there is a path between them
  • Connected graph - a graph is connected if there is a path from every vertex to every other vertex in the graph
  • A graph that is not conected consists of a set of connected components
  • Subgraphs - a graph G'=(V', E') is a subgraph of G=(V, E) iff V' โŠ† V and E' โŠ† E. Therefore, every vertex of the subgraph is from the set V of the original graph and every edge from the subgraph is from the set E of the original graph.
  • Forest - a joint set of trees
  • Spanning tree - Subgraph that contains all of that graph's vertices and is a single tree
  • Spanning forest - union of spanning trees of its connected components

Graph Processing Problems#

Here are some graph-related problems:

  • Is there a path between 2 vertices?
  • Shortest path
  • Finding cycles
  • Euler cycle - Is there a cycle that uses each edge exactly once?
    • Yes, iff connected and all vertices have an even degree
  • Hamilton cycle - Is there a cycle that uses each vertex exactly once?
    • NP-complete problem (No one knows an efficient solution to this)
  • Connectivity - Is there a way to connect all the vertices?
  • Biconnectivity - Is there a vertex whose removal disconnects the graph?
  • Planarity - Can the graph be drawn in the plane with no crossing edges?
  • Graph isomorphism - Do two adjacency lists represent the same graph?

Graph API#

MethodDescription
Graph(int V)Create an empty graph with v vertices
addEdge(int v, int w)Add an edge between vertices v and w
adj(int v)Returns vertices adjacent to the vertex v
V()Number of vertices
E()Number of edges
toString()String representation of graph (eg: for every vertex print all adjacent vertices (v-w))

Representing Graphs#

List of Edges#

Keep all the edges in a linked list or an array.

Example: [{0, 1}, {0, 2}, {0, 3}, {0, 4}]

  • Vertex 0 has 4 neighbours

Adjacency Matrix#

Maintain a 2D boolean array of size v * v. To see if vertices v and w are connected, check if arr[v][w] is true.

The matrix is symmetric for undirected graphs while not necessarily so for directed graphs.

However, this is not practical for huge graphs.

Adjacency Lists#

Most common way to represent a graph is using adjacency list.

Used for sparse graphs since our time taken is proportional to the number of edges. In real world applications, we tend to have many vertices but a small number of edges.

Adjacency List

Comparison of Various Methods (Time-Complexity)#

MethodSpace requiredAdd edgeCheck if edge is present between v and wIterate over vertices adjacent to v
List of edgesE1EE
Adjacency matrixV^211V
Adjacency listE + V1degree(v)degree(v)

Implementation#

Vertex Class#

class Vertex:
def __init__(self, key):
self.id = key # key of the current vertex
self.connected_to = {} # dictionary of all the adjacent vertices mapped to the weight of the edge
# add an adjacent vertex with default edge weight of 0
def add_neighbor(self, neighbour, weight=0):
self.connected_to[neighbour] = weight
def __str__(self):
return str(self.id) + ' connected_to: ' + str([x.id for x in self.connected_to])
# return all the adjacent vertices
def get_connections(self):
return self.connected_to.keys()
def get_id(self):
return self.id
def get_weight(self, neighbor):
if neighbor in self.connected_to:
return self.connected_to[neighbor]
else:
return None

Graph Class#

class Graph:
def __init__(self):
self.vertices = {} # dictionary of vertices (maps from vertex id to Vertex object)
self.num_vertices = 0
def add_vertex(self, key):
self.num_vertices += 1
new_vertex = Vertex(key)
self.vertices[key] = new_vertex
return new_vertex
# returns the vertex object if it exists
def get_vertex(self, key):
if key in self.vertices:
return self.vertices[key]
else:
return None
def get_adjacent(self, key):
if key in self.vertices:
return self.vertices[key].get_connections()
else:
return None
# implementing containment operator - 'in'
def __contains__(self, v):
return v in self.vertices
# add an undirected edge between two vertices with a default cost of 0
def add_edge(self, v, w, cost=0):
if v not in self.vertices:
self.add_vertex(v)
if w not in self.vertices:
self.add_vertex(w)
self.vertices[v].add_neighbor(self.vertices[w], cost)
# add a directed edge from v to w, default cost is 0
def add_directed_edge(self, v, w, cost=0):
if v not in self.vertices:
self.add_vertex(v)
if w not in self.vertices:
self.add_vertex(w)
self.vertices[v].add_neighbor(self.vertices[w], cost)
def get_vertices(self):
return self.vertices.keys()
def __iter__(self):
return iter(self.vertices.values())
def __str__(self):
output = ''
for v in self.vertices.values():
output += str(v)
output += '\n'
return output