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;
}
}
}
Auto comment: topic has been updated by sa_fu (previous revision, new revision, compare).