How to Create a Digital Agency Company Website Template Free Download
Continue…
Hands-on Graph Algorithms
For each node, we will define a “level”.
The level of the source node is 0
Level 1 nodes are the new nodes that can be directly accessed using an edge from level 0 nodes.
New nodes that can be reached directly from a level 1 node using an edge are level 2 nodes.
We will never return to a node twice, hence the term “new node”.
Exercise 2.1
a) In the graph above, take the source 1 and write the level next to each node.
We will learn the algorithm with an example. Suppose we want to go from node number 1 to node number 10.
First we source node 1. 1 then a ‘level 0’ node. Mark 1 as visited.
1 can go directly to node 2,3,4. So 2,3,4 are ‘level 1’ nodes. Now we mark them visited and work on them.
We will now work with the red nodes. All nodes in color are visited, never visit a node twice. From 2, 3, 4, the shortest route is 6, 7, 8.
Note that the number of levels we get the node, the length of its shortest path from the source. For example, 8 is found at level 2, so the distance of 8 is 2. The images are given different colors for each level. And red nodes mean we are working on them now. We haven’t reached 10 so let’s visit the next nodes:
We can see that after crossing 2 levels we are getting 10 at level 3. So the shortest path of 10 is 3. By searching the graph level by level we found the shortest path. Excluding the edges we didn’t use, we can rotate the image a bit like this:
bfs,bfs,graph
Note that the two graphs are the same, except that the empty nodes are rotated. I have lightened the edges which I have not used, if these edges are removed the graph becomes a tree. This tree is called BFS tree.
Digital Agency Company Website Template Free Download
That is, our work goes from the source to the level 1 nodes, then finds the level 2 nodes from the level 1 nodes, so the work will continue until we reach the destination or all the nodes have been visited.
Coding:
Hope everyone is familiar with Q data structure. A queue is a data structure exactly like a bus line. When a number is added to the queue it goes after all previous numbers, when a number is removed the first number is taken. It is called first in first out. We can use BFS AQ. When I get some new level 2 nodes from level 1 I will queue them up and always work on the first node. Then the big level nodes will always be at the back, we will move forward to work with the smaller levels. For the graph above we simulate this:
First push the source to the queue:
Q: [1]
Level of 1 will be 0 or level[1]=0. Now I will start BFS. First we will work with the front node of the queue. There is 1 in front of everyone, from there you can go to 2,3,4. 2,3,4 come from 1, then level[2]=level[1]+1=1, level[3]=level[1]+1=1, level[4]=level[3]+1 =1. Push them to the queue:
Q: [2,3,4,1]
1 is no longer useful, pop or throw away 1.
Q: [2,3,4]
Now let’s work with 4. 4 can go to 7. 7 came from 4, level[7]=level[4]+1=2. Push 7 to the queue:
Q: [7,2,3,4]
Now let’s pop 4:
Q: [7,2,3]
Can go from 3 to 7,8. 7 already taken, just need to push 8. Level[8]=Level[3]+1=2.
Q: [8,7,2,3]
Pop 3:
Q: [8,7,2]
This will continue until the queue is empty. In the level[] array we will get the distance of all nodes from the source!
We can code very easily using C++’s standard template library queue. Try it yourself first, then look at the code below:
vector<int>G[100];
void bfs(int n,int src)
{
queue<int>Q;
Q.push(src);
int visited[100]={0},level[100];
int parent[100];
visited[src]=1;
level[src]=0;
while(!Q.empty())
{
int u=Q.front(); //We will work with the front node of Q
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(!visited[v])
{
level[v]=level[u]+1;
parent[v]=u;
visited[v]=1;
Q.push(v);
}
}
Q.pop();
}
for(int i=1;i<=n;i++)
printf(“%d to %d distance %d”,src,i,level[i]);
}
Exercise 2.2
Not only is the length of the path sufficient, the path may also be necessary. Note that we are making parent[v]=u when going from u to v. We know for each node from which node we came to that node. Then we go from the node for which we want to find the path to its parent node until we reach the source. Write a function findpath(int) that takes a node as input and prints the path from the source to it. If the path does not exist, it will print “ERROR”.
Complexity:
Each node is visited once, each edge is visited once. Then the complexity will be O(V+E) where V is the number of nodes and E is the number of edges.
Sometimes BFS may need to be run on a 2-D grid. For example, a chess board has a knight and a king. In how many moves can the horse reach the king’s house? Or some cells are blocked in a 2-D array, now a minimum move from one cell to another is required, each move can only go forward-backward-left-right. Earlier we were expressing the node with a single number, now the node should be expressed with two numbers, row number and column number. Then we can create a structure to represent nodes like this:
struct node{int r,c;};
Or we can use C++’s “Pair”.
pair<int,int>
In this case the visited, parent, level arrays will be of 2 dimensions, eg visited[10][10] etc. I will push the structure instead of the node in the queue, that is, the queue will be like this: queue<node>Q. And when going from one room to another, check whether the board is going out. Let’s see a sample code:
Digital Agency Company Website Template Free Download
#define pii pair<int,int>
int fx[]={1,-1,0,0}; //Directions array
int fy[]={0,0,1,-1};
int cells[100][100]; // If cell[x][y] is -1 then the cell is block
int d[100][100],vis[100][100];
int row, col;
void bfs(int sx,int sy)
{
mem(vis,0);
vis[sx][sy]=1;
queue<pii>q;
q.push(pii(sx,sy));
while(!q.empty())
{
pii top=q.front(); q.pop();
rep(k,4)
{
int tx=top.uu+fx[k];
int ty=top.vv+fy[k];
if(tx>=0 and tx<row and ty>=0 and ty<col and cell[tx][ty]!=-1 and vis[tx][ty]==0)
{
vis[tx][ty]=1;
d[tx][ty]=d[top.uu][top.vv]+1;
q.push(pii(tx,ty));
}
}
}
}
Problems for Practice:
Bicoloring(Bipartite checking)
A Node Too Far(Shortest path)
Risk(Shortest path)
Bombs! NO they are Mines!!(bfs in 2d grid)
Knight Moves(bfs in 2d grid)
We Ship Cheap(Printing path)
Word Transformation(strings)
Happy Coding…
Before Download
You must Join our Facebook Group and Subscribe YouTube Channel
All Links in Below:
Join Our FreeWebsiteCreate Facebook Group to get an instant update for projects, templates, design resources, and solutions.
Join Our YouTube Channel & Subscribe with Bell Icon for New Video:
Join Our Official Facebook Page For the Latest updates All Code Projects are Free:
Visit our service page to get premium services.
Free Website Create – HTML CSS, PHP, JavaScript Programming Projects For Free
Follow Us
Thank You,
Before Download
You must Join our Facebook Group and Subscribe YouTube Channel
FreeWebsiteCreate.net tries to provide HTML, CSS, SCSS, JavaScript, React, Android Studio, Java, PHP, Laravel, Python, Django, C#(C Sharp), and ASP.net-related projects 100% free. We try to make learning easier. Free Website Create always tries to give free projects to new learners. Free projects and source code will help to learn quickly.
They can save time and learn more. In this post, we share a free portfolio project website code with HTML and CSS. This free code portfolio contains a single landing page with a responsive design. In this post, we get a free best carpenter and craftsman service website designed by FreeWebsiteCreate with HTML, CSS, Bootstrap, and JavaScript.