***** Graph ***** Concepts ======== + Vertex/Node * degree + Edge/Arc * directed * undirected * weighted + Connectivity * path between two vertices - length * distance between two vertices * adjacent * connected * cyclic * acyclic + Graph properties * directed/undirected * weighted/unweighted * cyclic/acyclic * connected/unconnected * dense/sparse .. graph-examples: Examples ======== .. graphviz:: :caption: Directed connected cyclic graph digraph G { node[shape=circle]; a -> {b, c, d}; b -> {a, d}; } .. graphviz:: :caption: Undirected connected cyclic weighted graph graph G { node[shape=ellipse]; Atlanta -- Dallas [label=4]; Atlanta -- Miami [label=4]; Atlanta -- Orlando [label=3]; Dallas -- Austin [label=1]; Dallas -- Orlando [label=6]; } .. graphviz:: :caption: Undirected connected acyclic graph (Tree) graph G { node[shape=circle]; b -- a; a -- {c, d}; b -- {e, f}; } .. graphviz:: :caption: Directed acyclic graph (DAG) task planning digraph G { rankdir=LR; node[shape=box]; task1 -> task2; task2 -> {task3, task4}; task3 -> {task5, task6}; task4 -> task6; } Representations =============== For the undirected graph: .. graphviz:: :caption: Undirected graph graph g1 { rankdir=LR; 1 -- 3, 4; 2 -- 1; 3 -- 4, 5; 4 -- 5; } + List of edges A list of edges is a 1d array in which every element in the array represents an edge. It is the simplest way to represent a graph. It is also an easy way to store a graph in a relational database. It is not efficient for most graph algorithms though. .. csv-table:: 1, 2 1, 3 1, 4 3, 4 3, 5 4, 5 + Adjacency list An adjacency list is a 1d array in which every element in the array represents a vertex and points to a list of its neighbors. .. graphviz:: :caption: Adjacency list digraph ll { rankdir=LR; node [shape=record]; first[label=" 1| 2| 3| 4| 5", height=5]; a1 [label="{ 2 | }"]; b1 [label="{ 3 | }"]; c1 [label="{ 4 | }"]; a2 [label="{ 2 | }"]; a3 [label="{ 1 | }"]; b3 [label="{ 4 | }"]; c3 [label="{ 5 | }"]; a4 [label="{ 1 | }"]; b4 [label="{ 3 | }"]; c4 [label="{ 5 | }"]; a5 [label="{ 3 | }"]; b5 [label="{ 4 | }"]; first:f1 -> a1:data:w; a1:ref:c -> b1:data; b1:ref:c -> c1:data; first:f2 -> a2:data:w; first:f3 -> a3:data:w; a3:ref:c -> b3:data; b3:ref:c -> c3:data; first:f4 -> a4:data:w; a4:ref:c -> b4:data; b4:ref:c -> c4:data; first:f5 -> a5:data:w; a5:ref:c -> b5:data; } + Adjacency matrix An adjacency matrix is a 2d array in which each row represents a source vertex and each column represents a destination vertex. The elements in the matrix represents the edge between the two vertices. .. csv-table:: Adjacency Matrix :header-rows: 1 :stub-columns: 1 _, 1, 2, 3, 4, 5 1, 0, 1, 1, 1, 0 2, 1, 0, 0, 0, 0 3, 1, 0, 0, 1, 1 4, 1, 0, 1, 0, 1 5, 0, 0, 1, 1, 0 Graph Traversal =============== + Depth-first search (DFS) Starting from one vertex, visit all vertices along the path started from the starting vertex till then end of the path (no unvisited neighbors) and then backtrack. * iterative using a stack * recursive + Breadth-first search (BFS) Starting from one vertex, visit all other vertices in the order of the distances to the starting vertex. * iterative using a queue Algorithms ========== Minimum spanning tree --------------------- This algorithm generates a tree that connects all connected vertices in a graph with the minimum total edge weight. See `visualization`__ .. __: https://visualgo.net/en/mst + Prim's algorithm + Kruskal's algorithm Dijkstra's shortest path ------------------------ Among the many variations of the shortest path algorithms, single-source shortest path algorithm is most commonly discussed. The objective is to find the shortest path of all other vertices to given a vertex (source). Shortest path problem with unweighted graph can be solved using BFS. Dijkstra's approach works with weighted (non-negative weight) graph. See `visualization`__ .. __: https://visualgo.net/en/sssp + invented by Edsger Dijkstra + employs a priority queue ADT Graph Glossary ============== .. glossary:: Vertex/Node (Graph) Entities that are interconnected Edge/Arc (Graph) The connection between two vertices Adjacency Two vertices are adjacent if connected by an edge Neighbors (Graph) All vertices that are adjacent Path (Graph) A sequence of edges from one vertex to another Length of path (Graph) The number of edges along a path Distance (Graph) The length of the **shortest** path between two vertices Full graph A graph in which all vertices are connected to other vertices Sparse graph A graph in which the number of edge is way fewer than the number for a full graph with the same number of vertices Directed graph A graph in which every edge has a direction from one vertex to another Undirected graph A graph in which every edge is symmetric Cyclic Graph A graph in which you can always find at least a path that starts and ends on a same vertex Acyclic Graph Can not find any path that starts and ends on a same vertex Weighted graph A graph in which every edge has a weight Depth-first search (DFS, Graph) Starting from one vertex, visit all vertices along the path started from the starting vertex till then end of the path (no unvisited neighbors) and then backtrack. Breadth-first search (BFS) Starting from one vertex, visit all other vertices in the order of the distances to the starting vertex.