 # Graph¶

### Properties¶

1. finite set of vertices -> nodes
2. set of ordered pair (u,v) telling aedge bw vertex v and u.
3. f(u,v) weight/value/cost.

### Applications¶

networks -> facebook, node has person info.

### Representation¶

3. Incidence Matrix
4. Incidence List

Depends on use case -> type of operations 2D array of size V x V adj[i][j] = 1, adj[i][j] = w

##### Pros¶

deletion, isThereAnEdge -> O(1)

##### Cons¶

space -> O(V^2) even matrix is sparse inserting an edge -> O(V^2) array[i] -> list of vertices adjacent to ith vertex. Weights -> as lists of pairs

##### Pros¶
• Saves space O(|V|+|E|)
• worst case -> O(V^2)
• Adding a vertex is easier
##### Cons¶

isThereAnEdge -> O(V)

``````#include <iostream>
#include <vector>
using namespace std;

void addEdge(vector<int> adj[], int u, int v) {
}

void printGraph(vector<int> adj[], int V){
for (int v = 0; v < V; ++v) {
cout << "\n Adjacency list of vertex "
<< v << "\n head ";
for (auto x : adj[v])
cout << "-> " << x;
printf("\n");
}
}

int main(){

int V = 5;