# Basic terminologies:

Vertices,edges,undirected and directed graph,cyclic & acyclic graph,degree indegree & outdegree and weights. In an undirected graph, the sum of degrees of all vertices is double the vertices (We consider degree=indegree=outdegree in an undirected graph).

# Graph representation in C++

Let us say there are n nodes and m edges.

There are two ways to represent a graph

- Adjacency matrix:

adj[i][j] represents there is an edge from node i to j.

```
int n, m;
cin >> n >> m;
// declare the adjacent matrix
int adj[n+1][n+1];
// take edges as input
for(int i = 0;i<m;i++) {
int u, v;
cin >> u >> v;
adj[u][v] = 1;
adj[v][u] = 1; //write this line only if the graph is undirected
}
```

Time Complexity:**O(m)**

Space Complexity:**O(n*n)**

- Adjacency List

```
cin >> n >> m;
// declare the adjacent matrix
vector<vector<int>> adj[n+1];
vector<int> adj[n+1];
// take edges as input
for(int i = 0;i<m;i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
return 0;
}
```

Time Complexity:**O(m)**

Space Complexity:**O(n*n)**

If there are also weights in edges we create the adjacency list like vector <vector < pair <int,int> > > where first value is node and second value represents weight b/w the nodes.

Since there can be multiple components in a graph, for graph traversal we have to call BFS/DFS from every unvisited node, but to avoid repetition we will store information if a node is visited by creating a boolean array where is_visited[i]==true represents node 'i' is visited.

# BFS

Time Complexity:**O(n+e)** ( O(n+e): n time taken for visiting n nodes and e time taken for traversing through adjacent nodes)

Space Complexity:**O(n)** ( O(n) for visiting array and O(n) for queue )

# DFS

Time Complexity:**O(n+e)** ( O(n+e): n time taken for visiting n nodes and e time taken for traversing through adjacent nodes)

Space Complexity:**O(n)** ( O(n) for visiting array and O(n) for stack space )

# Cycle detection in undirected graph using DFS

If a node adjacent to a node is already visited except the adjacent node is its parent, the component contains a cycle.

# Cycle detection in the undirected graph using BFS

# Check whether a graph is bipartite or not using BFS

A graph will not be a bipartite iff it has a cycle with odd no. of nodes.