**Graphs**

- Graph is a non linear data structure.
- A
*graph*is a collection of nodes(called*vertices)*, and the connections between them, called*edges*. - Graph is either Undirected or directed.

- When the edges in a graph have a direction, the graph is called a
*directed graph*. - The edges are called
*directed edges*or*arcs*.

- Graphs are used to solve many real-life problems.
- Graphs are used to represent networks.
- The networks may include paths in a city or telephone network or circuit network.

- Graphs are also used in social networks like linkedIn, Facebook. For example, in Facebook, each person is represented with a vertex (or node).
- Each node is a structure and contains information like person id, name, gender, locale etc.
- All of facebook is then a collection of these nodes and edges. This is because facebook uses a graph data structure to store its data.

**Graph:** A graph is a data structure G = {V, E} that consists of

- A collection of vertices V
- A collection of edges E, represented as ordered pairs of vertices (u, v)

**Graph Terminology**

**Adjacency**: A vertex is said to be adjacent to another vertex if there is an edge connecting them. Vertices 2 and 3 are not adjacent because there is no edge between them.**Path**: A sequence of edges that allows you to go from vertex A to vertex B is called a path.

**Graph representation as matrix called Adjacency matrix:**

- An adjacency matrix is a 2D array of V x V vertices. Each row and column represents a vertex.
- If the value of any element
`a[i][j]`

is 1, it represents that there is an edge connecting vertex i and vertex j.

**Traversal:** We use weight graphs and directions to find the BFS, DFS.

**Applications:** Using the weighted graph we can understand “Shortest path” problem which is the application of Graph.