**************** Topic 12 - Graph **************** * Graphs are a special type of data structure. * They are used to solve many problems, such as the shortest path problem. * However, if the implementation is not done carefully it can be too slow to use. What is a graph? ================ * We will start by giving a definition of a graph. .. admonition:: Definition: Graph * A **graph** :math:`G = (V,E)` consists of a set of vertices :math:`V` and a set of edges :math:`E`. * Each edge is a pair :math:`(v, w)`, where :math:`v,w\in V`. * Edges are sometimes referred as **arcs** and vertices as **nodes**. Directed Graphs --------------- .. admonition:: Definition: Directed Graph * When the edges (or arcs) :math:`(v,w)` are ordered the graph is **directed**. * Vertex :math:`w` is **adjacent** to :math:`v` if and only if :math:`(v,w)\in E`. * Directed graphs are also referred as **digraphs**. * The following figure represents a digraph: .. figure:: ../img/topic12/digraph.png :align: center .. admonition:: Activity :class: warning * Write all the pairs :math:`(v,w) \in E` of the previous graph. Undirected Graphs ----------------- * If there are directed graphs, there are undirected graphs! .. admonition:: Definition: Undirected Graph * In an undirected graph with edges :math:`(v,w)\in E`, there is an edge :math:`(w,v)\in E`. * :math:`w` is adjacent to :math:`v` and :math:`v` is adjacent to :math:`w`. .. admonition:: Activity :class: warning * Take the previous graph and transform it to an undirected graph. * Draw the undirected graph that contains the following edges: * :math:`E = \{(a,b), (b,a), (a,c), (c,a), (b,c), (c,b)\}` Representing graph in memory ============================ * Obviously, we cannot represent a graph like this in memory. * We could be as close as possible to the math representation: * Storing a list of nodes * And storing the list of arcs. .. admonition:: Activity :class: warning * What do you think about this representation? * Do you have a better representation? * There are two ways to represent a graph in memory: * Adjacency matrix * Adjacency list Adjacency Matrix ---------------- * The easiest way to represent is with a 2D matrix. * This is called an adjacency matrix. The idea: * Consider a matrix :math:`M`. * For each :math:`(u,v) \in E`: * We set :math:`M[u][v]` to 1. * Otherwise to 0. .. admonition:: Example * If we take the previous graph. * We can create the following adjacency matrix. .. figure:: ../img/topic12/adjacency_matrix.png :align: center * It is very easy to use adjacency matrix and very fast. * However, the space requirement is :math:`O(|V|^2)`. * It is a lot if the graph has a lotof nodes, but few arcs. * It is appropriate, if the graph is **dense** :math:`|E| = O(|V|^2)`. .. admonition:: Activity :class: warning * Why using a matrix for dense graphs is not a problem? * In most problems, graphs are not dense. .. admonition:: Example * Consider a street map of a city. * Assume a Manhattan-like orientation. * Any intersection is attached to roughly 4 streets. * So, if the graph is directed with two-way streets. * The number of edges is :math:`|E| \approx 4|V|` * If there are 3 000 intersection. * The number of vertices is 3 000. * And the number of edges is 12 000. * It requires an array of size 9 000 000. * A graph that is not dense is called **sparse**. * We need another way to represent **sparse** graph. Adjacency List -------------- * Adjacency list are a better solution when the graph is sparse. * For each vertex, we keep a list of all adjacent vertices. .. admonition:: Example * If we take the previous graph. * We can create the following adjacency list. * The space requirement is :math:`O(|E|+|V|)`. * It is linear in the size of the graph. .. figure:: ../img/topic12/adjacency_list.png :align: center .. admonition:: Activity :class: warning * Why are we not using adjacency lists for dense graphs? Weighted edges -------------- * Consider a problem in which you need to represent the streets and intersections in a city. * You would like to store the distance of each street. * A graph allows us to add **weights** on edges. * The changes to the previous representation are small: * Adjacency matrix: Instead of 0 and 1, we have the weight of the edge if it exists. If not :math:`- \infty` or :math:`+ \infty`. * Adjacency list: Add a new element in the list. .. admonition:: Activity :class: warning * Draw the directed graph that contains the following edges: * :math:`E = \{(a,b,2), (b,a,4), (a,c,3), (c,a,1), (b,c,10)\}` * Give the adjacency matrix and adjacency lists representation. More Definitions ================ * Graphs are used in a lot of algorithms. * To use them in these algorithms, we require some last definitions. .. admonition:: Definition: Path * In a graph, a **path** is a sequence of vertices :math:`v_1, v_2 \dots, v_N` such that :math:`(v_i, v_{i+1})\in E` for :math:`1 \leq i < N`. * The length of the path is the number of edges on the path (:math:`N-1`). .. admonition:: Definition: Cycle * In a cycle in a directed graph is a path of length at least 1 such that :math:`v_1 = v_N`. * In undirected graph the edges need to be distinct. * If a directed graph does not have a cycle, it is called a **acyclic** graph. .. admonition:: Activity :class: warning * Consider the graph given in the first example. * Give an example of a path. * Give a example of a cycle.