# Graph Algorithms [Graph Theory](https://en.wikipedia.org/wiki/Graph_theory) is a study of *graphs*, a mathematical structure modeling the associations between objects. It is vital for many computer science problems and worth attention for not only theoretical studies but also practical application development. This chapter discusses fundamental graph structures, typical graph problems and correlated algorithm analysis. Specifically, graph searching primitives such as DFS and BFS are the most important techniques throughout the graph algorithms. ## Graph Definitions Generally, there are two kinds of graphs: [directed graph](/algorithm-notes/outline/overview-3.md#directed-graph) and [undirected graph](/algorithm-notes/outline/overview-3.md#undirected-graph). Both of them involve a relationship between **Vertex** *V* and **Edge** *E*. ### Directed Graph Given a graph *G* = (*V*, *E*), wherein the *V* is a set of vertices of *G* and *E* is a set of edges going in and out from vertices with directions, connected them together. Specifically, given vertices {1, 2, 3, 4, 5, 6}, a graph can be built like below: ![](/files/-LQpLw-GI6MDfmbSCBQe)Figure 1. Directed Graph *Note: there are cycles (even self cycles, a vertex points to itself) in directed graphs and to be noted that problems like* [*topological sort*](/algorithm-notes/outline/overview-3/topological-sort.md) *could not have solutions if cycles present, the directed graph with no cycles is called DAG (directed acyclic graph)*. ### Undirected Graph Unlike [directed graph](/algorithm-notes/outline/overview-3.md#directed-graph), undirected graph only has edges with no directions between connected vertices. Since the relations among vertices have no ordering, there exists no self cycles. Similarly, ![](/files/-LQpLw-Iy4q4eOX00OMA)Figure 2. Undirected Graph ### Degrees In an [undirected graph](/algorithm-notes/outline/overview-3.md#undirected-graph), the degree of a vertex means the number of edges associated with that vertex. For instance, the degree of vertex 3 in the above graph is 3; While in the [directed graph](/algorithm-notes/outline/overview-3.md#directed-graph), the degree of a vertex is the summation of its **in-degree** and **out-degree**. Such **in-degree** means the number of edges pointing towards the vertex and **out-degree** means the number of edges pointing out of the vertex. *Note: the vertex with zero degree means it is a lonely island, disconnected from any other vertices in the graph*. ### Connectivity If for any given vertices in an [undirected graph](/algorithm-notes/outline/overview-3.md#undirected-graph), there exists paths reachable from all other vertices, then the graph is *connected*. Specifically, if an undirected graph *G* = (*V*, *E*) is connected, the number of edges is larger than or equal to number of vertices minus 1: |*E*| ≥ |*V*| - 1. There are only definitions of **strongly connected** and **weakly connected** in a [directed graph](/algorithm-notes/outline/overview-3.md#directed-graph). In a **strongly connected** directed graph *G* = (*V*, *E*), for any two distinct vertices x, y within *V*, there exists paths from x to y and from y to x; Substituting all directional edges of a directed graph with undirected ones could obtain a *base graph* of the original graph. If such a *base graph* is **connected**, then the original directed graph is **weakly connected**. ## Graph Representations Two vertices sharing a same edge are *adjacent* in a graph. To define such relationships among vertices, two practical uses of data structures are introduced: [adjacency matrix](/algorithm-notes/outline/overview-3.md#adjacency-matrix) and [adjacency list](/algorithm-notes/outline/overview-3.md#adjacency-list). ### Adjacency Matrix This matrix (e.g. *adj\[]\[]*) is a 2D array with size |V| ✗ |V|; In an undirected graph, if vertex *a* and vertex *b* are connected, then adj\[a]\[b] = 1 and adj\[b]\[a] = 1; if there are no edges between say vertex *e* and vertex *c*, then adj\[e]\[c] = 0, adj\[c]\[e] = 0; For a directed graph, the matrix cell value depends on the existance of directional edges; If vertex *a* has an edge going outward to vertex *b* while vertex *b* has no edges going inward to vertex *a*, then adj\[a]\[b] = 1 but adj\[b]\[a] = 0 ![](/files/-LQpLw-K9fmeJX7jYjQd)Figure 3. Adjacency Matrices of a Directed Graph and an Undirected Graph Adjacency matrix is practical when the graph is **dense** (at least one edge going in between two vertices) and finding the existence of edges is immediate (LOOKUP costs Ο(1)). It is less so if the graph is sparse (the graph topology structure approaches a ***forest*** rather than a graph). ### Adjacency List Adjacency list is an array of linkedlist in design and it costs only Ο(|V| + |E|) compared to [adjacency matrix](/algorithm-notes/outline/overview-3.md#adjacency-matrix). In addition, the array can be dynamic which means adding vertices to a graph is easier than a static structure like adjacency matrix. ![](/files/-LQpLw-MN0AWHkmdFe5F)Figure 4. Adjacency List of a Directed Graph Though it normally costs Ο(|E|) time to LOOKUP edge associations, it is a preferable choice than adjacency matrix in a massive-scale data network such as WEB. ## Table of Contents * [Breadth-First Search](/algorithm-notes/outline/overview-5/graph-search.md) - a searching primitive prototype for many important algorithms like \[Minimum Spanning Tree] and \[Dijkstra Shortest Path]. * [Depth-First Search](/algorithm-notes/outline/overview-5/graph-search.md) - in contrast to BFS, DFS provides a simple recursive implementation. * [Shortest Path Algorithms](/algorithm-notes/outline/overview-3/shortest-path.md) - a prevalent type of graph algorithm in practice, e.g. find a shortest path from location A to location B in map. * [Minimum Spanning Tree](/algorithm-notes/outline/overview-3/minimum-spanning-tree.md) - a technique to transform graphs to trees * [Graph Minimum-Cut](https://github.com/aaronoah/algorithm-notes/tree/9a534ff48627c60fe225a120d7cf880d1d057006/docs/graph-algorithms/minimum-cut.md) - split the graph into different groups for applications like [community finding](https://en.wikipedia.org/wiki/Community_structure#Algorithms_for_finding_communities). * [Topological Sort](/algorithm-notes/outline/overview-3/topological-sort.md) - sort a [DAG](/algorithm-notes/outline/overview-3.md#directed-graph) graph with respect to its topological relations. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://cs-notes.gitbook.io/algorithm-notes/outline/overview-3.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.