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<int>> 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;↵
}↵
}↵
}↵
~~~~~↵
↵
↵
**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<int>> 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;↵
}↵
}↵
}↵
~~~~~↵
↵
