Graph Algorithms is a most interesting portion of algorithm design at now. This is actually a category named Graph Theory. Graph theory is the study of graphs, mathematical structures used to model pair wise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another. Graph theory is required for mapping, network communication, graphic design, gaming application, data organization and more.
Depth First Search, Breadth First Search, Topological Sorting and Flood Fill algorithm are some most common and basic level graph algorithm which we are going to discussed here at now:
Depth First Search:
To traverse a graph, DFS or Depth First Search is an algorithm. DFS traverse all the nodes of the graph as started from root node and going to the depth or leave node of that root nodes connected with and turn back and traverse another node. DFS use a stack implementation as it required some memory recommendation for its traverse.
Some people can say it as uninformed search algorithm as it does not need any information about the goal distance or such thing which can help the searching algorithm to search a specific node.
The algorithm working here is something like that:
- Push the root node onto a stack.
- Pop a node from the stack and examine it.
- If the element sought is found in this node, quit the search and return a result.
- Otherwise push all its successors (child nodes) that have not yet been discovered onto the stack.
- If the stack is empty, every node in the tree has been examined – quit the search and return "not found".
- If the stack is not empty, repeat from Step 2.
The DFS algorithm my code is here:
#include<iostream>
#include<queue>
using namespace std;
void dfs_visit(queue<int> *v,int u,int *c,int *pi)
{
int p;
c[u]=1;
while(v[u].size())
{
p=v[u].front(); //Check all the child nodes
v[u].pop();
if(c[p]==0)
{
pi[p]=u;
dfs_visit(v,p,c,pi); //recursive call
}
}
}
void dfs(queue<int> *v,int *c,int *pi,int n)
{
for(int i=1;i<=n;i++)
{
if(c[i]==0)
{
cout<<"New Forest"<<endl; //check for invidual nodes which
dfs_visit(v,i,c,pi); //are not still visited
}
}
}
int main()
{
int i,j,a,n,m,s,u,p,d;
cout<<"Number Of Nodes: ";
cin>>n;
queue<int> v[n+1];
int c[n+1],pi[n+1];
for(i=1;i<=n;i++)
{
cout<<"Number Of Adjacent Nodes Of "<<i<<" : ";
cin>>m;
c[i]=0;
pi[i]=0;
cout<<"The Nodes Are : ";
for(j=0;j<m;j++)
{
cin>>a;
v[i].push(a);
}
}
dfs(v,c,pi,n);
system("pause");
return 0;
}
Breadth First Search:
To traverse a graph, BFS or Breadth First Search is an algorithm. BFS traverse all the nodes of the graph as started from root node and traverse nodes as leveling access to the deeper. BFS use a queue implementation as it required some first in first out algorithm implementation.
Some people can say it as uninformed search algorithm as it does not need any information about the goal distance or such thing which can help the searching algorithm to search a specific node.
The algorithm working here is something like that:
procedure BFS(Graph,source):
create a queue Q
enqueue source onto Q
mark source
while Q is not empty:
dequeue an item from Q into v
for each edge e incident on v in Graph:
let w be the other end of e
if w is not marked:
mark w
enqueue w onto Q
My code is here for you:
#include<iostream>
#include<queue>
using namespace std;
void path(int s,int v,int *pi)
{
if(v==s)
cout<<s<<" ";
else if(pi[v]==0) //Printing path from source to destination
cout<<"No Path"<<endl; //according to the result of BFS
else
{
path(s,pi[v],pi);
cout<<v<<" ";
}
}
int bfs(int n,int s,queue<int> *v,int *pi,int *c)
{
queue<int> q;
int u,p;
c[s]=1;
q.push(s);
while(q.size())
{
u=q.front();
q.pop();
while(v[u].size())
{ //BFS algorithm using queue
p=v[u].front();
v[u].pop();
if(c[p]==0)
{
c[p]=1;
pi[p]=u;
q.push(p);
}
}
}
}
int main()
{
int i,j,a,n,m,s;
cout<<"Number Of Nodes: ";
cin>>n;
queue<int> v[n+1];
int pi[n+1],c[n+1];
for(i=1;i<=n;i++)
{
cout<<"Number Of Adjacent Nodes Of "<<i<<" : ";
cin>>m;
c[i]=0;
pi[i]=0;
cout<<"The Nodes Are : ";
for(j=0;j<m;j++)
{
cin>>a;
v[i].push(a);
}
}
cout<<"The Source Node : ";
cin>>s;
int t;
cout<<"Destination Node : ";
cin>>t;
bfs(n,s,v,pi,c);
path(s,t,pi);
system("pause");
return 0;
}
Topological Sorting:
We already have a sorting algorithm article. So, hope that all of we know a lot of sorting algorithm. But, this time, it’s quite different. Now, we are going to sort the graph according to its nodes. A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.
The graph shown to the left has many valid topological sorts, including:
- 7, 5, 3, 11, 8, 2, 9, 10 (visual left-to-right, top-to-bottom)
- 3, 5, 7, 8, 11, 2, 9, 10 (smallest-numbered available vertex first)
- 3, 7, 8, 5, 11, 10, 2, 9
- 5, 7, 3, 8, 11, 10, 9, 2 (fewest edges first)
- 7, 5, 11, 3, 10, 8, 9, 2 (largest-numbered available vertex first)
- 7, 5, 11, 2, 3, 8, 9, 10
The algorithm is similar to DFS algorithm just added some steps more:
L ← Empty list that will contain the sorted nodes
S ← Set of all nodes with no incoming edges
for each node n in S do
visit(n) function visit(node n)
if n has not been visited yet then mark n as visited for each node m with an edge from n to m do visit(m) add n to LThe code is here as following:
#include<iostream>
#include<queue>
#include<list>
using namespace std;
int f[100];
int times;
list<int> li;
void dfs_visit(queue<int> *v,int u,int *c,int *pi)
{
int p;
c[u]=1;
times=times+1;
while(v[u].size())
{
p=v[u].front();
v[u].pop();
if(c[p]==0)
{ //DFS code
pi[p]=u;
dfs_visit(v,p,c,pi);
}
}
f[u]=times=times+1;
li.push_front(u); //push the node to the list
}
void dfs(queue<int> *v,int *c,int *pi,int n)
{
times=0;
for(int i=1;i<=n;i++)
{
if(c[i]==0)
{
cout<<"New Forest"<<endl; //DFS Code
dfs_visit(v,i,c,pi);
}
}
}
int main()
{
int i,j,a,n,m,s,u,p,d;
cout<<"Number Of Nodes: ";
cin>>n;
queue<int> v[n+1];
int c[n+1],pi[n+1];
for(i=1;i<=n;i++)
{
cout<<"Number Of Adjacent Nodes Of "<<i<<" : ";
cin>>m;
c[i]=0;
pi[i]=0;
cout<<"The Nodes Are : ";
for(j=0;j<m;j++)
{
cin>>a;
v[i].push(a);
}
}
dfs(v,c,pi,n);
while(li.size())
{
cout<<li.front()<<" "; //print the topological sort
li.pop_front();
}
system("pause");
return 0;
}
Flood Fill Algorithm:
Flood fill, also called seed fill, is an algorithm that determines the area connected to a given node in a multi-dimensional array. It is used in the "bucket" fill tool of paint programs to determine which parts of a bitmap to fill with color, and in games such as Go and Minesweeper for determining which pieces are cleared. When applied on an image to fill a particular bounded area with color, it is also known as boundary fill.
The algorithm is simple. Just use a recursive function to check the node is connected or not which are adjacent to one node:
Flood-fill (node, target-color, replacement-color):
1. If the color of node is not equal to target-color, return.
2. Set the color of node to replacement-color.
3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
Perform Flood-fill (one step to the east of node, target-color, replacement-color). Perform Flood-fill (one step to the north of node, target-color, replacement-color). Perform Flood-fill (one step to the south of node, target-color, replacement-color).5. Return.The code seems to be very lengthy but its very simple and repetitive:
#include<iostream>
using namespace std;
int r,c,mat[100][100];
void rec(int i,int j)
{
if(i>=0 && i<r && j>=0 && j<c)
{
mat[i][j]=0;
if(mat[i+1][j]==1)
rec(i+1,j);
if(mat[i-1][j]==1)
rec(i+1,j);
if(mat[i][j+1]==1)
rec(i+1,j);
if(mat[i][j-1]==1)
rec(i+1,j);
if(mat[i+1][j+1]==1)
rec(i+1,j);
if(mat[i-1][j-1]==1)
rec(i+1,j);
if(mat[i+1][j-1]==1)
rec(i+1,j);
if(mat[i-1][j+1]==1)
rec(i+1,j);
}
return;
}
void floodfill()
{
int i,j,count=0;
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
if(mat[i][j]==1)
{
count++;
rec(i,j);
}
}
}
cout<<"The Number Of Disjoint Nodes: "<<count<<endl;
}
int main()
{
int i,j;
cout<<"Number of Row : ";
cin>>r;
cout<<"Number Of Column : ";
cin>>c;
cout<<"Give The Map : "<<endl;
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
cin>>mat[i][j];
}
}
floodfill();
return 0;
}
Hope that you enjoy the article. I am going to publish more articles on more graph algorithm very soon. Keep touch with us.
For more: www.pothikerdiary.comze.com
there are a lot of better implementations, especially for floodfill!
Your floodfill seems overflooded with code duplication.
I'd suggest the following implementation of rec(i, j):
void rec(int i, int j) { if (i < 0 || i >= r || j < 0 || j >= c) return; if (mat[i][j] != 1) return; mat[i][j] = 0; for (int di = -1; di <= 1; ++di) for (int dj = -1; dj <= 1; ++dj) if (di != 0 || dj != 0) rec(i + di, j + dj); }Other algorithms look fine (except for half of lines being blank), though I would personally recommend using vectors instead of queues for storing edges.