# Graphs
## Types of Graphs
### Undirected Graph
An **undirected graph** is a graph in which edges have no orientation. The edge (u, v) is identical to the edge (v, u).
### Directed Graph
A **directed graph** or digraph is a graph in which edges have orientations. For example, the edge (u, v) is the edge
from node u to node v.
### Weighted Graphs
A **weighted graph** is a graph whose edges contain a certain weight to represent an arbitrary value such as cost, distance, quantity, etc. Such edges are usually denoted as a triplet (u, v, w).
### Special Graphs
#### Trees
A **tree** is an undirected graph with no cycles. Equivalently, it is a connected graph with N nodes and N-1 edges
#### Directed Acyclic Graphs (DAGs)
**DAGs** are directed graphs with no cycles.
#### Bipartite Graph
A **bipartite graph** is one whose vertices can be split into two independent groups U, V such that every edge connects betweens U and V.
#### Complete Graphs
A **complete graph** is one where there is a unique edge between every pair of nodes.
A complete graph with n vertices is denoted as the graph Kn.

## Representing Graphs
### Adjacency Matrix
A **adjacency matrix** m is a matrix where the cell m[i][j] represents the edge weight of going from node i to node j.
### Adjacency List
An **adjacency list** is a way to represent a graph as a map from nodes to lists of edges.
### Edge List
An **edge list** is a way to represent a graph simply as an unordered list of edges. Assume the notation for any triplet (u,v,w) means: *“the cost from node u to node v is w”*.

## Algorithms
### Depth First Search (DFS)
The Depth First Search (DFS) is the most fundamental search algorithm used to **explore nodes and edges** of a graph.
Complexity: `O(V + E)`
#### Find Number of components with DFS
#### Topological order with DFS