Scribd
Importer
23 vues29 pages

DSA Module-5 Part-A

Les notes de cours sur les structures de données et leurs applications abordent les concepts fondamentaux des graphes, y compris les définitions de sommets, d'arêtes, de graphes dirigés et non dirigés, ainsi que des opérations élémentaires telles que l'insertion et la suppression de sommets et d'arêtes. Le document explique également les représentations des graphes, y compris les matrices d'adjacence et les listes d'adjacence, ainsi que des algorithmes comme celui de Warshall pour trouver des matrices de chemin. Enfin, il traite des graphes pondérés et des opérations de recherche dans les graphes.

Transféré par

wadofas620
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
23 vues29 pages

DSA Module-5 Part-A

Les notes de cours sur les structures de données et leurs applications abordent les concepts fondamentaux des graphes, y compris les définitions de sommets, d'arêtes, de graphes dirigés et non dirigés, ainsi que des opérations élémentaires telles que l'insertion et la suppression de sommets et d'arêtes. Le document explique également les représentations des graphes, y compris les matrices d'adjacence et les listes d'adjacence, ainsi que des algorithmes comme celui de Warshall pour trouver des matrices de chemin. Enfin, il traite des graphes pondérés et des opérations de recherche dans les graphes.

Transféré par

wadofas620
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
Lecture Notes Data Structures and Applications [BCS304] Graphs Definitions Vertex — It is a synonym for a node and is generally represented by a circle Example: O © Edge — If ‘u’ and ‘v’ are two vertices, then an arc or a line joining the two vertices ‘u’ and ‘v’ is called an edge Example Undirected Edge — An edge without any direction is called an undirected edge and is denoted by an ordered pair (u, v) Example: (3, 6) Directed Edge — An edge with a direction is called an directed edge and is denoted by an directed pair - Example: <4, 7> Graph — A graph G consists of two sets V and E and is denoted as G~ (V, E), where, V is finite, nonempty set of vertices Eis finite set of edges Directed Graph — A graph G = (V, E) is called a directed graph if all the edges are directed. Itis also called as a digraph Example: Dr. Mahesh G Professor Dept of CSE, BMSIT & ML The graph G = (V, E), where V={1,2,3,4} E={<1,2>, <1,4>, <2,1>, <3,1>, <3,4> } Undirected Graph — A graph undirected. Example: 'V, E) is called a undirected graph if all the edges are Module 5 J Lecture Notes Data Structures and Applications [BCS304] The graph G = (V, E), where V={1,2,3,4} E={ (1,2), (2,4), (1,3), G,4)} Self Loop — A loop is an edge which starts and ends on the same vertex. It is represented by an ordered pair (,i) Example: On —O)> In the above graph the self loops are (1, 1) and (2, 2) Muttigraph — A graph with multiple occurrence of the same edge between any two vertices is called as a multigraph Example: Dr. Mahesh G Professor, Dept of CSE, BMSIT & M In the above graph, (1,2) and (1,3) are the multiple edges Complete Graph ~ A graph G ~ (VE) is said to be a complete graph, if there e between every pair of vertices. Example’ Ix] Note: In a complete graph with ‘n’ vertices there will be n(n-1)/2 edges Subgraph — A subgraph G’ of a graph Gis graph such that VG’) ) 123 4 T{o}i{ijo 2[o0}0/1]0 3 {o}ololl 6% ©) 4foh[olo Copy the adjacency matrix to path matrix 123 4 ifofi fi To 2fo fof fo 3|o0}]o}ol1 4\o}1}0]0 Path Matrix P. Let K=1, we find whether a path exists from i to j through through node 1 is o1 ti. 13 OV 0 ON ON 1 1 1 20 202 213 OV /0 ON A ON 1 1 1 o.1 3 0 303 OV 0 ON ON 1 1 1 401 4. 403 Module 5 2 a‘n xn” two dimensional array af Jf ] such that, land the path matrix obtained ae ee See ofi fifo ofofifo ofofofi oi [olo Path Matrix P. 2 Lecture Notes Data Structures and Applications [BCS304] Let K=2, we find whether a path exists from i to j through 2 and the path matrix obtained through node 2 is Let K=3, we find whether a path exists from i to j through 3 and the path matrix obtained through node 3 is laze) ifotitita 2fofohfa 3fofolofi sft htt Path Matrix P Module 5 13 Lecture Notes Data Structures and Applications [BCS304] Let K=4, we find whether a path exists from i toj through 4 and the path matrix obtained through node 3 is fa 12 13 14 WW 0; WN EN \ a 4 4 4 4 20 202 213 244 W/O) NL w/t 1\ n 4 4 4 4 o1 302 303 3 4 1/0 Wo 7d Woo 1\ A 4 4 4 4 401 412 413 444 WV /0 Wot WW ot 1\ in 4 4 4 4 Algorithm Read n Read the adjacency matrix Copy the adjacency matrix to path matrix Find the path matrix DaManesniG’ Professor Dept. of CSE, BMSIT& M for( k=1; k<-n; k++) for( j=1; j<=n; j++) t pal =0) HOLE == 1 && plkfj]== 1) pL) = 15 } } Write the path matrix Module 5 sJeyefe]- 1 Path Matrix 4 1 1 1 1 P 14 Lecture Notes Data Structures and Applications [BCS304] #include void main( ) { inti, j, k, n, a[20][20], p[20][20]; ("Enter the number of vertices\n"); anf("%od", &n), // Read the adjacency matrix for( i=1; i<=n; i++) { for( j=1; j<=m; j++) { scantt"%d", &afi]Li); 3 3 1! Copy the adjacency matrix to path matrix for( i=1; i Data Structures and Applications [BCS304] int min(int x, int y) { if(x void main( ) { int n, i,j, a[20][20], source, visited[20], e[20]12]; printf("Enter the number of vertices\n"); scanft"%d", &n); // Read the adjacency matrix for( i=1; i<=n; i+ ) { fort j { scanf("%d", &ali][iD); 3 3 printf("Enter the source vertex\n"); scanf("%d", &source); for(i=1; i<=n; i++) Dr. Mahesh G Professor ‘ visited{i Dept of CSE, BMSIT& M 3 bfs(_n, a, source, visited, e ); // To print the nodes which are reachable and not reachable from source 5 +H) if(visited[i] = = 0) { printf(%d is not reachable \n", i); flag = 1; } else { printf("%d is reachable \n", i); 3 } // To check if the graph is connected and for printing spanning tree if(flag == 1) { printf("The graph is not connected\n"); 3 else { print{("The graph is connected\n"); printf("The spanning tree or BFS traversal is\n"); for(i=1; <= n-l; i++) { printf("Edge from %d to %din", efi][1}, efilI2)); } } 3 Module 5 22 Lecture Notes Data Structures and Applications [BCS304] void bfs( int n, int a[20]{20}, int source, int visited{ J, int e[20][2] ) : int f= 0, r=-1, q[20];/ queue components intu, v, k= 1; /I visit the source node and insert it into the queue visited[source] = 1; r=rtly ale] = source: while( f <=) // as long as the queue is not empty { // delete an clement from the queue // find the nodes adjacent to 'u' and not visited for( v=1; v<=n; v+) { iff a[ul[v] == 1 && visited[v] = = 0) { visited[v]=1; // visit the node r all=v; J/insert the node to queue efKI0] efk][2]=v; // store the edges k=k+1; 3 3 3 } Module 5 23 Lecture Notes Data Struct res and Applications [BCS304] Depth First Search In this traversal technique, a node 's' is picked as a start node and marked visited, An unmarked adjacent node to’'s is selected to become the new start node and marked, possibly leaving the original start node with unexplored edges for the time being The search continues in the graph until the current path ends or until all the adjacent nodes are already marked, Then the search returns to the previous nodes which still had unmarked adjacent nodes and continues marking until all nodes are marked. Note: We use a recursive call to the DFS function, hence the data structure in use for DF stack, Example: Consider the graph shown below Dr. Mahesh G Professor, Dept of SE, BMSIT & M Assuming source = 1, the depth first traversal for the above graph is Module 5 24 Lecture Notes Data Structures and Applications [BCS304] Algorithm Initialize the visited{ } Step 1: Visit the source vertex ‘u! Step 2: For every node 'v' adjacent to vertex 'u! If'v' is not visited earlier Store the edges (from source vertex 'u' to adjacent nodes 'v’) Repeat through Step 1 with source as ‘v' #include void dfs( int n, int a[20]{20], int u, int visited ], int e[20][2] ) { inty; static int k= 1; // visit the source vertex 'u’ ey S visited{u] ——— J/find the nodes adjacent to 'u' and not visited for( v=1; v<=n; vi+) if( aful[v] == 1 && visited[y t efk][1] =u; e[k][2]=v; // store the edges k-k+1; df3( n, a, V, visited, e); } 3 3 Module 5 25 Lecture Notes Data Structures and Applications [BCS304] void main( ) { int n, i, j, a[20][20], source, visited{20], e{20][2}; printf("Enter the number of vertices\n"); scanf("%d", &n); // Read the adjacency matrix for( i=1; i<=n; i+ ) t for( j=l: jn; j++) { scanf{"%d", &ali]{j)); 3 3 printf("Enter the source vertex\n"); scanf{"%d", & source); visited[i] = 0; dfs( n, a, source, visited, e ); // To print the nodes which are reachable and not reachable from source 5 i++) if{visited{i] = = 0) { printf(%d is not reachable \n", i); flag = 1; } else { printf("%d is reachable \n", i); 3 } // To check if the graph is connected and for printing spanning tree if(flag == 1) { printf("The graph is not connected\n"), 3 else { print{("The graph is connected\n"); printf{"The spanning tree or DFS traversal is\n' for(i=l; i<=n-l; i+) { printf("Edge from %d to %din", efi][1}, efilI2)); } } Module 5 26 Lecture Notes Data Structures and Applications [BCS304] Lab Program Design, Develop and Implement a Program in C for the following operations on Graph(G) of Cities a, Create a Graph of N cities using Adjacency Matrix. b. Print all the nodes reachable from a given starting node in a digraph using DFS/BFS. method #include void bfs( int n, int a[20][20], int source, int visited] }, { int f= 0, r=-1, q[20};// queue components intu,v,k=1; // visit the source node and insert it into the queue visited{source] rartly alt] = source; while( £ <=) // as long as the queue is not empty { u=qlf —_// delete an element from the queue f-f+; //find the nodes adjacent to'u' and not visited for( v=1; v<=n; v++) { if afullv && visited[v] { visited[v] =1; // visit the node //insert the node to queue / store the edges } } 3 Module 5 27 Lecture Notes Data Structures and Applications [BCS304] void dfs( int n, int a[20][20], int u, int visitedf J, int e[20](2] ) { int v; static int k= 1; // visit the source vertex 'u! visited[u] = 1; // find the nodes adjacent to'u! and not visited for( v=1; v<=n; v++) if{ afulv] =~ 1 && visited[y] = - 0) { efkK][1] =u; efk][2]=v; _ // store the edges k=k+1; dfs( n, a, v, visited, e); } void main( ) { int n, i, j, a[20][20], source, visited{20], e[20][2],choice,flag: printi("Enter the number of vertices\n"); scanf{"%d", &n); // Read the adjacency matrix for(i=1; i<=n; i++) t for( j=1; j<=n; j++) t scanf{"%d", &afi]fj]); 3 } printf("Enter the source vertex\n"), scanf("%ed", &source), for(i=1; i<=n; i+) { visitedfi) Module 5 28 Lecture Notes Data Structures and Applications [BCS304] printf("[Link] [Link]\n" printi("Enter ur choice\n scanf("%d", &choice), if(choice == 1) bfa(-n, a, source, visited, e): else dfa( n, a, source, visited, e ); // To print the nodes which are reachable and not reachable from source flag = 0; ican; i++) Dr. Mahesh G ; Professor, ; Dept of CSE, BMSIT & A itedfi printf("%d is not reachable \n", i); flag 3 else t printf("%d is reachable \n’, i); 3 1) To check if the graph is connected and for pr if(flag == 1) Hi ing spanning tree printi("The graph is not connected\n"); else { printf("The graph is connected\n"); printf("The spanning tree or traversal is\n"); for(i=l; i<=n-l; i+) { printf("Edge from %d to %d\n", efi}[1], efi][2]); } 3 getch( ); Module 5 29

Vous aimerez peut-être aussi