Graph Algorithms Lab 7 focuses on implementing key graph algorithms, including Breadth First Search (BFS), Depth First Search (DFS), and Topological Sorting. This lab is essential for students studying Data Structures and Algorithms, providing practical experience in graph representation using adjacency lists. The document includes detailed explanations of each algorithm, sample code in C++, and output examples to illustrate the concepts. Ideal for computer science students and those preparing for technical interviews, this lab enhances understanding of graph traversal techniques.

Key Points

  • Explains Breadth First Search (BFS) algorithm implementation in C++
  • Covers Depth First Search (DFS) with practical coding examples
  • Includes Topological Sorting for Directed Acyclic Graphs (DAG)
  • Demonstrates graph representation using adjacency lists
  • Provides sample outputs to illustrate algorithm functionality
Mahek Patel
9 pages
Language:English
Type:Lab Report
Algorithms & Data Structures
Mahek Patel
9 pages
Language:English
Type:Lab Report
Algorithms & Data Structures
397
/ 9
Lab-07 Graph Algorithms-I
Aim: Implement following Graph algorithms.
Clearly mention the data structures (Adjacency Matrix or List) used to
represent graph and its complexity with necessary justification in the
journal.
1. Breadth First Search
2. Depth First Search
3. Topological Sorting over Directed Acyclic Graphs
1.Breadth-first Search
1. Breadth First Search & Depth First Search
#include <iostream>
#include <cstdlib>
#include <vector>
#include <queue>
using namespace std;
struct node {
int v;
node* next;
};
node** adj;
int n, m;
vector<int> visited;
void init() {
adj = (node**)malloc((n + 1) * sizeof(node*));
for (int i = 0; i <= n; i++)
adj[i] = NULL;
}
void INIT() {
visited.clear();
for (int i = 0; i <= n; i++)
visited.push_back(0);
}
node* createnode(int a) {
node* temp = (node*)malloc(sizeof(node));
temp->v = a;
temp->next = NULL;
return temp;
}
void addEdge(int a, int b) {
node* t1 = createnode(b);
if (adj[a] == NULL) {
adj[a] = t1;
return;
}
node* h = adj[a];
while (h->next != NULL)
h = h->next;
h->next = t1;
}
void printGraph() {
cout << "\nAdjacency List:\n";
for (int i = 1; i <= n; i++) {
cout << i << " -> ";
node* temp = adj[i];
while (temp != NULL) {
cout << temp->v << " ";
temp = temp->next;
}
cout << endl;
}
}
void bfs(int start) {
queue<int> q;
visited[start] = 1;
q.push(start);
cout << "\nBFS Traversal: ";
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u <<" ";
node* temp = adj[u];
while (temp != NULL) {
int v = temp->v;
if (!visited[v]) {
visited[v] = 1;
q.push(v);
}
temp = temp->next;
}
}
cout<<endl;
}
void DFS(int a) {
visited[a]=1;
cout << a << " ";
node *temp=adj[a];
while(temp!=NULL) {
int v=temp->v;
if(!visited[v])
DFS(v);
temp=temp->next;
}
}
/ 9
End of Document
397

Figures

Graph Algorithms Lab 7 - DAA — int main() {
2.Depth first search & topological sorting:
Graph Algorithms Lab 7 - DAA — printGraph();
Graph Algorithms Lab 7 - DAA — Figure 4

You May Also Like

FAQs

what is Graph Algorithms Lab 7 - DAA about

Graph Algorithms Lab 7 - DAA focuses on implementing fundamental graph algorithms using data structures like adjacency matrices and lists.

  • Breadth First Search (BFS)
  • Depth First Search (DFS)
  • Topological Sorting over Directed Acyclic Graphs (DAGs)

how to implement BFS in Graph Algorithms Lab 7 - DAA

The implementation of Breadth First Search (BFS) in Graph Algorithms Lab 7 - DAA involves using a queue to explore nodes level by level.

  • Initialize a queue and mark the starting node as visited.
  • While the queue is not empty, dequeue a node and explore its neighbors.
  • Enqueue unvisited neighbors and mark them as visited.

what are the steps for Depth First Search in Graph Algorithms Lab 7 - DAA

Depth First Search (DFS) in Graph Algorithms Lab 7 - DAA is implemented using recursion or a stack to explore as far as possible along each branch before backtracking.

  • Mark the current node as visited.
  • Recursively visit each unvisited neighbor.
  • Push nodes onto a stack to record the order of completion for topological sorting.

how does topological sorting work in Graph Algorithms Lab 7 - DAA

Topological sorting in Graph Algorithms Lab 7 - DAA organizes nodes in a directed acyclic graph (DAG) such that for every directed edge from node A to node B, node A comes before node B.

  • Perform DFS to visit all nodes.
  • Push each node onto a stack upon completion.
  • Pop nodes from the stack to get the topological order.

what data structures are used in Graph Algorithms Lab 7 - DAA

Graph Algorithms Lab 7 - DAA utilizes adjacency lists and matrices to represent graphs effectively.

  • Adjacency List: Efficient for sparse graphs, uses linked lists for neighbors.
  • Adjacency Matrix: Suitable for dense graphs, uses a 2D array to represent connections.

what is the complexity of BFS in Graph Algorithms Lab 7 - DAA

The time complexity of Breadth First Search (BFS) in Graph Algorithms Lab 7 - DAA is O(V + E), where V is the number of vertices and E is the number of edges.

  • Space complexity is O(V) due to the storage of the queue and visited nodes.

what is the complexity of DFS in Graph Algorithms Lab 7 - DAA

The time complexity of Depth First Search (DFS) in Graph Algorithms Lab 7 - DAA is also O(V + E), similar to BFS.

  • Space complexity can be O(V) for the recursion stack in the worst case.

how to visualize graphs in Graph Algorithms Lab 7 - DAA

Graph visualization in Graph Algorithms Lab 7 - DAA can be done using adjacency lists to represent connections between nodes.

  • Print the adjacency list to see the structure of the graph.
  • Use graphical tools or libraries for a more visual representation.

what are common applications of graph algorithms from Graph Algorithms Lab 7 - DAA

Graph algorithms from Graph Algorithms Lab 7 - DAA have various applications in computer science and real-world scenarios.

  • Network routing and optimization
  • Scheduling problems
  • Dependency resolution in software