A graph is a binary relation over a finite set of nodes (or vertices). Graphs are useful to represent computer networks, social networks, ecological networks, electrical circuits, finance, geospatial maps, and many other applications. In a directed graph, the edges have direction. In an undirected graph, edges have no direction or may be considered bidirectional. A weighted graph has weights assigned to edges. Traversal problems, identifying cycles, ranking nodes, shortest paths, spanning trees, flows, and others are solved with graph algorithms. The most basic representation of a graph is an **adjacency matrix**, simply a $n \times n$ binary matrix for a graph of $n$ nodes where the values in the matrix represents a relationship between two nodes as a boolean or weight. A large graph represented in this way will be a [[sparse matrix]]. An **adjacency list** reduces the sparsity of the adjacency matrix. Each node is linked to a list of the nodes to which it is connected. The size of the adjacency list is simply the sum of the number of nodes and number of edges. The **incidence matrix** is yet another popular option for representing graphs. Graph traversal can be conducted via [[breadth first search]] or [[depth first search]]. [[topological sort]] [[strongly connected components]] [[minimal spanning tree]] [[Kruskal's algorithm]] [[union-find data structure]] [[shortest path]] [[all pairs shortest path]] [[Floyd-Warshall algorithm]] [[matrix multiplication algorithm]] [[Bellman-Ford algorithm]] [[Djikstra's algorithm]] [[transitive closure]] ```python # n_verts: number of vertices of the graph # vertices are labeled from 0... n-1 # adj_list: an adjacency list represented as a list of lists. # if set to None, we will initialize it as an empty graph class UndirectedGraph: def __init__(self, n_verts, adj_list=None): self.n = n_verts if adj_list == None: adj_list = [ [] for j in range(self.n)] # initialize as empty list of lists else: assert len(self.adj_list) == n_verts for lst in adj_list: for elt in lst: assert 0 <= elt and elt < self.n_verts self.adj_list = adj_list def add_edge(self, i, j): assert 0 <= i and i < self.n assert 0 <= j and j < self.n assert i != j self.adj_list[i].append(j) self.adj_list[j].append(i) def get_list_of_edges(self): return [ (i, j) for i in range(self.n) for j in self.adj_list[i] if i < j ] ```