How To Find The Solution To A Graph
Introduction:
What is a graph? Do nosotros apply information technology a lot of times? Let'southward retrieve of an example: Facebook. The humongous network of y'all, your friends, family, their friends and their friends etc. are called equally a social graph. In this "graph", every person is considered as a node of the graph and the edges are the links between 2 people. In Facebook, a friend of yours, is a bidirectional relationship, i.eastward., A is B'due south Friend => B is A's friend, so the graph is an Undirected Graph.
Nodes? Edges? Undirected? We'll become to everything slowly.
Allow's redefine graph by maxim that it is a collection of finite sets of vertices or nodes (V) and edges (E). Edges are represented as ordered pairs (u, v) where (u, v) indicates that there is an edge from vertex u to vertex 5. Edges may contain toll, weight or length. The degree or valency of a vertex is the number of edges that connect to it. Graphs are of ii types:
Undirected: Undirected graph is a graph in which all the edges are bidirectional, essentially the edges don't point in a specific direction.
Directed: Directed graph is a graph in which all the edges are unidirectional. 
A weighted graph is the one in which each edge is assigned a weight or cost. Consider a graph of iv nodes equally shown in the diagram beneath. As you can meet each edge has a weight/toll assigned to it. Suppose nosotros need to go from vertex 1 to vertex iii. There are three paths.
1 -> 2 -> three
ane -> 3
1 -> 4 -> iii
The total cost of 1 -> ii -> 3 will be (1 + two) = iii units.
The full toll of one -> 3 will be 1 units.
The full cost of 1 -> 4 -> 3 will be (iii + ii) = 5 units.
A graph is called cyclic if there is a path in the graph which starts from a vertex and ends at the same vertex. That path is called a bike. An acyclic graph is a graph which has no cycle.
A tree is an undirected graph in which whatsoever two vertices are connected by only 1 path. Tree is acyclic graph and has N - i edges where Northward is the number of vertices.
Graph Representation:
In that location are variety of ways to represent a graph. 2 of them are:
Adjacency Matrix: An adjacency matrix is a V x 5 binary matrix A (a binary matrix is a matrix in which the cells can have just i of two possible values - either a 0 or 1). Element Ai,j is 1 if in that location is an edge from vertex i to vertex j else Ai,j is 0. The adjacency matrix can likewise be modified for the weighted graph in which instead of storing 0 or ane in Ai,j we volition store the weight or toll of the edge from vertex i to vertex j. In an undirected graph, if Ai,j = 1 then Aj,i = one. In a directed graph, if Ai,j = 1 and so Aj,i may or may not be i. Adjacency matrix providers constant time access (O(one) ) to tell if in that location is an edge between two nodes. Infinite complication of adjacency matrix is O(Vii).
The adjacency matrix of above graph is:
i/j : ane ii 3 4
1 : 0 1 0 1
two : i 0 1 0
three : 0 i 0 i
iv : 1 0 1 0
The adjacency matrix of higher up graph is:
i/j: 1 two iii 4
ane : 0 ane 0 0
2 : 0 0 0 one
iii : i 0 0 1
iv : 0 1 0 0
Consider the to a higher place directed graph and let u.s. create this graph using an Adjacency matrix and and so evidence all the edges that exist in the graph.
Input File:
iv
five
1 2
two 4
3 ane
3 4
4 2
Lawmaking:
#include <iostream> using namespace std; bool A[ten][x]; void initialize() { for(int i = 0;i < 10;++i) for(int j = 0;j < 10;++j) A[i][j] = false; } int main() { int ten, y, nodes, edges; initialize(); // Since there is no border initially cin >> nodes; // Number of nodes cin >> edges; // Number of edges for(int i = 0;i < edges;++i) { cin >> x >> y; A[ten][y] = true; // mark the edges from vertex x to vertex y } if(A[3][4] == true) cout << "In that location is an edge betwixt 3 and iv" << endl; else cout << "At that place is no edge between 3 and iv" << endl; if(A[ii][3] == true) cout << "At that place is an edge between 2 and three" << endl; else cout << "In that location is no edge between ii and 3" << endl; return 0; } Output:
There is an edge betwixt 3 and 4
In that location is no border betwixt ii and three
Adjacency Listing: The other way to stand for a graph is an adjacency list. Adjacency list is an assortment A of separate lists. Each element of the array Ai is a list which contains all the vertices that are adjacent to vertex i. For weighted graph we can store weight or price of the edge along with the vertex in the list using pairs. In an undirected graph, if vertex j is in list Ai then vertex i will be in listing Aj . Space complexity of adjacency list is O(5 + E) considering in Adjacency list nosotros shop information for only those edges that actually be in the graph. In a lot of cases, where a matrix is thin (A sparse matrix is a matrix in which most of the elements are nada. By contrast, if most of the elements are nonzero, so the matrix is considered dumbo.) using an adjacency matrix might non exist very useful, since information technology'll use a lot of space where most of the elements volition be 0, anyway. In such cases, using an adjacency list is better.
Consider the same undirected graph from adjacency matrix. Adjacency list of the graph is:
A1 → 2 → 4
A2 → i → three
A3 → two → 4
A4 → 1 → three
Consider the aforementioned graph from adjacency matrix. Adjacency list of the graph is:
A1 → 2
A2 → 4
A3 → 1 → four
A4 → 2
Consider the above directed graph and permit's lawmaking it.
Input File:
iv
5
i 2
2 4
3 1
three iv
4 2
Code:
#include<iostream > #include < vector > using namespace std; vector <int> adj[10]; int main() { int x, y, nodes, edges; cin >> nodes; // Number of nodes cin >> edges; // Number of edges for(int i = 0;i < edges;++i) { cin >> ten >> y; adj[ten].push_back(y); // Insert y in adjacency list of x } for(int i = i;i <= nodes;++i) { cout << "Adjacency list of node " << i << ": "; for(int j = 0;j < adj[i].size();++j) { if(j == adj[i].size() - 1) cout << adj[i][j] << endl; else cout << adj[i][j] << " --> "; } } render 0; } Output:
Adjacency list of node 1: 2
Adjacency list of node 2: 4
Adjacency list of node 3: one --> iv
Adjacency listing of node 4: 2
Graph Traversals:
While using some graph algorithms, we need that every vertex of a graph should be visited exactly once. The order in which the vertices are visited may be important, and may depend upon the particular algorithm or particular question which we're trying to solve. During a traversal, nosotros must go along runway of which vertices accept been visited. The nearly common mode is to mark the vertices which have been visited.
So, graph traversal ways visiting every vertex and every edge exactly once in some well-defined order. There are many approaches to traverse the graph. Ii of them are:
Depth Get-go Search (DFS):
Depth first search is a recursive algorithm that uses the idea of backtracking. Basically, information technology involves exhaustive searching of all the nodes by going ahead - if it is possible, otherwise it will backtrack. By backtrack, hither we mean that when we practise non get any further node in the electric current path and so we move dorsum to the node,from where nosotros can find the further nodes to traverse. In other words, nosotros will proceed visiting nodes equally soon as we find an unvisited node on the current path and when current path is completely traversed we will select the next path.
This recursive nature of DFS can be implemented using stacks. The bones idea is that we pick a starting node and button all its next nodes into a stack. Then, we pop a node from stack to select the next node to visit and push all its side by side nodes into a stack. We keep on repeating this process until the stack is empty. But, nosotros do not visit a node more than once, otherwise we might cease upward in an infinite loop. To avert this infinite loop, we volition mark the nodes as shortly every bit we visit it.
Pseudocode :
DFS-iterative (G, s): //where G is graph and s is source vertex. let S be stack South.push( southward ) // inserting due south in stack mark due south as visited. while ( S is not empty): // pop a vertex from stack to visit next five = Southward.top( ) S.pop( ) //button all the neighbours of v in stack that are not visited for all neighbours w of v in Graph 1000: if w is not visited : Southward.push( w ) marker w equally visited DFS-recursive(One thousand, southward): marker s as visited for all neighbours west of southward in Graph Grand: if w is non visited: DFS-recursive(G, westward) 
Applications:
1) How to find continued components using DFS?
A graph is said to be asunder if information technology is not continued, i.eastward., if there exist 2 nodes in the graph such that there is no edge between those nodes. In an undirected graph, a continued component is a set of vertices in a graph that are linked to each other by paths. Consider an example given in the diagram. Every bit we tin see graph G is a disconnected graph and has 3 connected components. Start connected component is one -> 2 -> 3 as they are linked to each other. Second connected component four -> 5 and 3rd connected component is vertex six. In DFS, if nosotros outset from a start node it volition marking all the nodes continued to start node as visited. So if we choose any node in a connected component and run DFS on that node it will mark the whole connected component as visited. So we will echo this process for other connected components.
Input File:
6
4
1 2
2 3
1 3
4 five
Code:
#include <iostream> #include <vector> using namespace std; vector <int> adj[x]; bool visited[ten]; void dfs(int s) { visited[s] = true; for(int i = 0;i < adj[south].size();++i) { if(visited[adj[s][i]] == false) dfs(adj[s][i]); } } void initialize() { for(int i = 0;i < x;++i) visited[i] = faux; } int principal() { int nodes, edges, x, y, connectedComponents = 0; cin >> nodes; // Number of nodes cin >> edges; // Number of edges for(int i = 0;i < edges;++i) { cin >> x >> y; // Undirected Graph adj[x].push_back(y); // Border from vertex ten to vertex y adj[y].push_back(x); // Edge from vertex y to vertex x } initialize(); // Initialize all nodes equally non visited for(int i = 1;i <= nodes;++i) { if(visited[i] == false) { dfs(i); connectedComponents++; } } cout << "Number of connected components: " << connectedComponents << endl; return 0; } Output:
Number of connected components: 3
Latitude First Search (BFS)
Its a traversing algorithm, where we start traversing from selected node (source or starting node) and traverse the graph layerwise which means it explores the neighbour nodes (nodes which are straight connected to source node) and so move towards the next level neighbour nodes. As the name suggests, nosotros move in breadth of the graph, i.east., we move horizontally first and visit all the nodes of the current layer and so we move to the side by side layer.
Consider the diagram beneath:
In BFS, all nodes on layer ane will be traversed before we move to nodes of layer 2. As the nodes on layer 1 take less distance from source node when compared with nodes on layer ii.
As the graph tin can contain cycles, so we may come at same node again while traversing the graph. So to avert processing of same node again, we utilize a boolean array which marks the node marked if we accept process that node. While visiting all the nodes of electric current layer of graph, nosotros will store them in such a manner, so that nosotros can visit the children of these nodes in the same order every bit they were visited.
In the above diagram, starting from 0, we will visit its children 1, 2, and iii and store them in the lodge they get visited. And then that after visiting all the vertices of electric current layer, we tin visit the children of 1 first(that are iv and 5), then of two (that are six and 7) then of 3(that is vii) then on.
To brand the above procedure easy, we will apply a queue to store the node and mark information technology as visited, and we volition shop it in queue until all its neighbours (vertices which are straight connected to it) are marked. As queue follow FIFO social club (Commencement In Start Out), information technology volition first visit the neighbours of that node, which were inserted first in the queue.
Pseudocode :
BFS (G, s) //where M is graph and south is source node. permit Q be queue. Q.enqueue( south ) // inserting southward in queue until all its neighbor vertices are marked. mark s as visited. while ( Q is non empty) // removing that vertex from queue,whose neighbour will be visited now. v = Q.dequeue( ) //processing all the neighbours of v for all neighbours west of 5 in Graph One thousand if w is not visited Q.enqueue( w ) //stores west in Q to further visit its neighbour mark due west as visited. For the Graph below: 
Initially, it will start from the source node and volition push south in queue and mark s every bit visited.
In get-go iteration, It will pop s from queue and so volition traverse on neighbours of due south that are i and 2. As ane and 2 are unvisited, they will be pushed in queue and will exist marked every bit visited.
In 2nd iteration, it will pop ane from queue and so will traverse on its neighbours that are southward and 3. As s is already marked then it will be ignored and 3 is pushed in queue and marked as visited.
In third iteration, it will pop two from queue and so volition traverse on its neighbours that are s,3 and 4. Equally iii and s are already marked and then they will be ignored and iv is pushed in queue and marked as visited.
In fourth iteration, it will popular 3 from queue and then will traverse on its neighbours that are 1, 2 and 5. Every bit ane and ii are already marked so they will be ignored and 5 is pushed in queue and marked as visited.
In 5th iteration, it will pop 4 from queue and and so will traverse on its neighbours that is two merely. As ii is already marked and so it volition be ignored.
In 6th iteration, it will pop 5 from queue and then volition traverse on its neighbours that is 3 only. Every bit 3 is already marked so information technology will exist ignored.
Now the queue is empty then it comes out of the loop.
Through this you can traverse all the nodes using BFS.
BFS can be used in finding minimum altitude from one node of graph to another, provided all the edges in graph have aforementioned weight.
Example:
Equally in the above diagram, starting from source node, to detect the altitude between 0 and 1, if we do non follow BFS algorithm, we tin can go from 0 to two and then to one. Information technology will give the distance between 0 and 1 as ii. But the minimum altitude is 1 which can exist obtained by using BFS.
Complexity: Time complication of BFS is O(V + East) , where V is the number of nodes and E is the number of Edges.
Applications:
1) How to determine the level of each node in the given tree ?
As nosotros know in BFS, we traverse level wise, i.e first nosotros visit all the nodes of one level and and then visit to nodes of another level. Nosotros can apply BFS to make up one's mind level of each node.
Implementation:
vector <int> five[10] ; // vector for maintaining adjacency list explained higher up. int level[10]; // to determine the level of each node bool vis[x]; //marking the node if visited void bfs(int s) { queue <int> q; q.button(southward); level[ s ] = 0 ; //setting the level of sources node as 0. vis[ southward ] = truthful; while(!q.empty()) { int p = q.front(); q.pop(); for(int i = 0;i < v[ p ].size() ; i++) { if(vis[ v[ p ][ i ] ] == fake) { //setting the level of each node with an increment in the level of parent node level[ v[ p ][ i ] ] = level[ p ]+one; q.button(v[ p ][ i ]); vis[ 5[ p ][ i ] ] = true; } } } } Higher up code is similar to bfs except ane change and i.e
level[ v[ p ][ i ] ] = level[ p ]+i;
here, when visiting each node, we set the level of that node with an increment in the level of its parent node .
Through this we can determine the level of each node.
In the diagram to a higher place :
node level[ node ] south(source node) 0 one i 2 one 3 2 four 2 5 2 vi 2 seven three 2) 0-1 BFS: This type of BFS is used when we have to observe the shortest distance from one node to some other in a graph provided the edges in graph have weights 0 or 1. Every bit if we apply the normal BFS explained to a higher place, it can give wrong results for optimal altitude betwixt 2 nodes.(explained beneath)
In this approach nosotros will not use boolean assortment to marker the node visited as while visiting each node we will cheque the condition of optimal distance.
We will use Double Ended Queue to store the node.
In 0-ane BFS, if the edge is encountered having weight = 0, and then the node is pushed to front end of dequeue and if the border'due south weight =i, then information technology volition exist pushed to dorsum of dequeue.
Implementation:
Hither :
edges[ v ] [ i ] is an adjacency listing that will exists in pair class i.e edges[ v ][ i ].showtime will contains the number of node to which v is connected and edges[ v ][ i ].2nd will contain the distance between v and edges[ v ][ i ].first .
Q is double ended queue.
distance is an array where, distance [ five ] volition contain the distance from start node to v node.
Initially define distance from source node to each node equally infinity.
void bfs (int outset) { deque <int > Q; // double ended queue Q.push_back( start); distance[ start ] = 0; while( !Q.empty ()) { int five = Q.front( ); Q.pop_front(); for( int i = 0 ; i < edges[v].size(); i++) { /* if distance of neighbour of v from get-go node is greater than sum of distance of v from beginning node and border weight between v and its neighbour (altitude betwixt v and its neighbour of 5) ,then alter it */ if(altitude[ edges[ v ][ i ].outset ] > distance[ v ] + edges[ 5 ][ i ].second ) { distance[ edges[ 5 ][ i ].first ] = altitude[ v ] + edges[ v ][ i ].second; /*if edge weight betwixt v and its neighbour is 0 then push button information technology to front of double concluded queue else push it to back*/ if(edges[ five ][ i ].second == 0) { Q.push_front( edges[ v ][ i ].first); } else { Q.push_back( edges[ v ][ i ].first); } } } Allow'south sympathize the above code with the Graph given below:
Adjacency Listing of to a higher place graph will be:
here s can be taken as 0 .
0 -> i -> iii -> 2
edges[ 0 ][ 0 ].first = 1 , edges[ 0 ][ 0 ].second = i
edges[ 0 ][ one ].first = three , edges[ 0 ][ 1 ].second = 0
edges[ 0 ][ 2 ].start = two , edges[ 0 ][ ii ].second = 1
1 -> 0 -> four
edges[ i ][ 0 ].start = 0 , edges[ one ][ 0 ].2nd = one
edges[ 1 ][ ane ].commencement = iv , edges[ 1 ][ one ].second = 0
2 -> 0 -> three
edges[ 2 ][ 0 ].first = 0 , edges[ ii ][ 0 ].second = 0
edges[ 2 ][ 1 ].first = 3 , edges[ 2 ][ 1 ].2nd = 0
3 -> 0 -> 2 -> 4
edges[ three ][ 0 ].offset = 0 , edges[ iii ][ 0 ].second = 0
edges[ 3 ][ 2 ].beginning = two , edges[ 3 ][ ii ].second = 0
edges[ iii ][ iii ].offset = 4 , edges[ 3 ][ iii ].second = 0
4 -> one -> 3
edges[ 4 ][ 0 ].start = 1 , edges[ four ][ 0 ].second = 0
edges[ 4 ][ 1 ].first = iii , edges[ 4 ][ 1 ].2d = 0
And then if nosotros utilize normal bfs here, information technology volition give the states wrong results past showing optimal distance between s and 1 node equally 1 and between a and 2 as i, but the real optimal altitude is 0 in both the cases. As it simply visits the children of s and calculate the distance between southward and its children which will give i as the answer.
Processing:
Initiating from source node, i.e 0, it volition move towards 1,2 and 3. As the edge weight betwixt 0 and i is 1 and betwixt 0 and two is 1 , then they will be pushed in back side of queue and as edge weight between 0 and 3 is 0, so it volition pushed in front side of queue. Accordingly, distance will be maintained in distance array.
Then three will be popped up from queue and same process will exist applied on its neighbours so on..
iii) Peer to Peer Networks: In peer to peer networks, Breadth Start Search is used to notice all neighbor nodes.
iv) GPS Navigation systems: Breadth First Search is used to find all neighboring locations.
5) Broadcasting in Network: In networks, a broadcasted packet follows Breadth Beginning Search to achieve all nodes.
Source: https://www.hackerearth.com/practice/notes/graph-theory-part-i/
Posted by: acostaablee1955.blogspot.com
0 Response to "How To Find The Solution To A Graph"
Post a Comment