**Nodes** or **vertices** connected to each other through **edges**.

*A graph G is an ordered pair of a set of vertices V and a set of edges E.*

- Ordered pair vs Unordered pair { Set}
- Directed edges(Digraph) vs Undirected Edges
- Weighted vs Unweighted edges
- Unweighted graph = Weighted graph with all weights equal
- Self-looping edges on a single vertex
- Multi-edge graphs
- Maximum number of edges in a directed graph=
*(n)*(n-1)* - Maximum number of edges in an undirected graph=
*(n)*(n-1) / 2* **Dense**graph( Edges ~ (Vertices) squared) vs**Sparse**graph( Edges ~ (Vertices))

**Path= **Sequence of vertices where each adjacent vertex is connected by an edge.

A path in a graph G is a sequence of vertices v0, v1, …, vn so that for all i, (vi -> v(i+1)) is an edge of G.

**Walk=** A path in which vertices and edged may be repeated.

**Trail=** A walk in which no edges are repeated.

**Simple Path=** A walk in which no vertices and no edges are repeated.

**Connected Graph= **Path exists from any vertex to any other vertex.

** Undirected** graph is

*Connected*.

*Directed graph*is

*Strongly Connected*.

If directed graph is not strongly connected but can be converted to a connected(undirected) graph, it is called

**Weakly Connected**.**Closed Walk=**A walk which starts and ends at the same vertex. Length must be > 0.

**Simple Cycle=**No repetition of vertices other than start and end.

**Acyclic Graph=**Undirected Acyclic Graph =

**Tree**, Directed Acyclic Graph=

**DAG**

**Connected Components= **The vertices of a graph G can be partitioned into connected components so that v is reachable from w if and only if they are in the same connected component.

## Storage of Graph

- List of all edges
- As an ordered pair of {vertex list, edge list} = O(Edges) cost
**Adjacency Matrix**= O(Vertices) cost- Useful for dense graphs

**Adjacency List=**Store only those vertices which are connected- Array / Linked List /
**BST**

- Array / Linked List /

### Exploring Graph

**Depth First Traversal (Stack)**

- Needs adjacency list for efficient execution
- O(|E|) execution time

**Determine Connected Components**- Runtime = O(|V| + |E|)

**Determine Previsit and Postvisit numbers****Breadth First Traversal (Queue)**