Graph Terms

Entity -> vertex /Node connection / path / relationship -> Edge

Some common Difference ---------------------- Directed Vs Undirected Flight (directed) Vs Roads (undirected) Weighted vs Unweighted Connected Vs Disconnected Cyclic vs Acyclic

Graphs Representation

Adjacency Matrix

int adj[i][j];

Advantage

- Is there an edge between A coonected to B ? This question can be answered in One look up __ - very good for "Dense Networks"

Disadvantages

-Navigation becomes Algorithmically complex. Who are the neighbors _ of vertex1? this question will require N checks_ -Space inefficient , Since we need MAX N*N space no matter the density of the graph. -How do you represent Multiple paths ? not possible .

Adjacency list --------------

Represent graph as a vector of vectors . A list of lists

Advantages

-nevigation becomes Algorithmically Simple. Who are the neighbors of vertex1? Just retrieve g[1]. The first row corresponding to vertex 1.

-Space Efficient , our storage space increase linearly with number of edges. -Can reoresent multiple paths with multiply entries. A second path from 3 to 2 with weight 10 ? g[3].push_back({2,10})

Disadvantages

Answering look up question like " is 1 connected to 2 " or " what is weight of the edge 1,2 — it becomes complex

Edge List

One edge , one entry

Advantages (B.F. algorithms)

• very covenient for iterating over all edges
• if we have coustom sort methods

default representation for graph problem ---------------------------------------- vector<vector> g; for unweighted graph vector <vector<pair<int,int>>g ; for weighted graph

Navigation a graph vs Array /Queue /Stack ------------------------------------------ -process -operation -Solve

Depth First Search or DFS for graph ------------------------------------

Navigation

DFS

vector<vector<int>>g;
int n,m;
vector<bool> vis;

void dfs(int u){
	vis[u]=true;
	for (auto i: g[u]){
	if(!vis[i]){
	dfs[i];
	}
	}
}

Connected Components --------------------

int conected_components(){
	int cc=0;
	for(int i=0;i<=n;i++){
	if(!vis[i]){
	  dfs(i);
	  c++;
	}
	}
	return cc;
}

Breath First Search (BFS)

Single Source Shortest path

void bfs(int u){
	queue<int>bfs_q;
	bfs_q.push_back(u);
	dist[u]=0;
	vis[u]=true;

	while(!bfs_q.empty()){
	u=bfs_q.front();
	bfs_q.pop();
	
	for(auto v:g[u]){
		if(!vis[v]){
		bfs_q.push(v);
		dist[v]=dist[u]+1;
		}
	}
}