Graph 
Разница между en1 и en2, 13 символ(ов) изменены
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;↵
}↵
}↵
}↵
~~~~~↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский sa_fu 2024-08-30 07:48:48 8
en2 Английский sa_fu 2024-08-30 07:47:25 13 Tiny change: 'ph Terms\n=========== \n\n**Enti' -> 'ph Terms\n\n\n**Enti'
en1 Английский sa_fu 2024-08-30 07:45:58 2864 Initial revision (published)