# Introduction

## #

OverviewGraphs are a generalization of trees. A graph is a set of *vertices* connected pairwise by *edges*.

Graphs can be directed. A directed edge is like a 1-way road and undirected edges are a 2-way road.

Graphs can have cycles or not.

Every tree is a graph, but not every graph is a tree.

## #

Terminologies**Undirected Graph**- a graph G=(V,E) is a structure comprising a set V or vertices/nodes with a set E of edges/lines, where each edge is 2-element subset of V that relates 2 vertices.**V**- set of vertices - V = {v1, v2, v3 ...}**E**- set of 2-element sets consisting of v(s) - E = {e1, e2, e3 โฆ} where edges are pairs of vertices (e = {v1, v2})**Path**- Sequence of vertices connected by edges**Cycle**- Path whose first and last vertices are the same**Degree**- Number of edges connected to a given vertex**Connected vertices**- 2 vertices are connected if there is a path between them**Connected graph**- a graph is connected if there is a path from every vertex to every other vertex in the graph- A graph that is not conected consists of a set of
**connected components** **Subgraphs**- a graph G'=(V', E') is a subgraph of G=(V, E) iff V' โ V and E' โ E. Therefore, every vertex of the subgraph is from the set V of the original graph and every edge from the subgraph is from the set E of the original graph.**Forest**- a joint set of trees**Spanning tree**- Subgraph that contains all of that graph's vertices and is a single tree**Spanning forest**- union of spanning trees of its connected components

## #

Graph Processing ProblemsHere are some graph-related problems:

- Is there a
**path**between 2 vertices? **Shortest path**- Finding
**cycles** **Euler cycle**- Is there a cycle that uses each edge exactly once?- Yes, iff connected and all vertices have an
*even*degree

- Yes, iff connected and all vertices have an
**Hamilton cycle**- Is there a cycle that uses each vertex exactly once?- NP-complete problem (No one knows an efficient solution to this)

**Connectivity**- Is there a way to connect all the vertices?**Biconnectivity**- Is there a vertex whose removal disconnects the graph?**Planarity**- Can the graph be drawn in the plane with no crossing edges?**Graph isomorphism**- Do two adjacency lists represent the same graph?

## #

Graph APIMethod | Description |
---|---|

Graph(int V) | Create an empty graph with v vertices |

addEdge(int v, int w) | Add an edge between vertices v and w |

adj(int v) | Returns vertices adjacent to the vertex v |

V() | Number of vertices |

E() | Number of edges |

toString() | String representation of graph (eg: for every vertex print all adjacent vertices (v-w)) |

## #

Representing Graphs### #

List of EdgesKeep all the edges in a linked list or an array.

Example: [{0, 1}, {0, 2}, {0, 3}, {0, 4}]

- Vertex 0 has 4 neighbours

### #

Adjacency MatrixMaintain a 2D boolean array of size `v * v`

. To see if vertices v and w are connected, check if `arr[v][w]`

is true.

The matrix is symmetric for undirected graphs while not necessarily so for directed graphs.

However, this is not practical for huge graphs.

### #

Adjacency ListsMost common way to represent a graph is using *adjacency list*.

Used for sparse graphs since our time taken is proportional to the number of edges. In real world applications, we tend to have many vertices but a small number of edges.

### #

Comparison of Various Methods (Time-Complexity)Method | Space required | Add edge | Check if edge is present between v and w | Iterate over vertices adjacent to v |
---|---|---|---|---|

List of edges | E | 1 | E | E |

Adjacency matrix | V^2 | 1 | 1 | V |

Adjacency list | E + V | 1 | degree(v) | degree(v) |