Question

In: Computer Science

In this assignment, you will implement Breadth First Search (BFS). The input to your program is...

In this assignment, you will implement Breadth First Search (BFS). The input to your program is a graph in the adjacency list format. The input graph has at most 100 vertices. Your program must initiate a BFS from vertex 2 of the graph. If the graph is connected, your program must output “Graph is connected”. If the graph is disconnected, your program must output “Graph is not connected”. Your program should read from an input file: data2.txt and write to the output file: out2.txt.

Your program should be written in C or C++. You can use STL for a queue but not for a graph.

Input Example

1 3 4

2 4

3 1 4

4 2 1 3

1 2 4

2 1 3

3 2 4

4 1 3

1 2

2 1

3 4

4 3

Solutions

Expert Solution

Hi,

we used fstream for reading and writing into file

Below is the c++ implementation code:

#include<bits/stdc++.h>
#include<iostream>
#include <fstream>
#define NODE 100
using namespace std;
int graph[NODE][NODE];
void traverse(int s, bool visited[]) {
   visited[s] = true; //mark v as visited
   queue<int> que;
   que.push(s);//insert s into queue
   while(!que.empty()) {
      int u = que.front(); //delete from queue and print
      que.pop();
      for(int i = 0; i < NODE; i++) {
         if(graph[i][u]) {
            //when the node is non-visited
            if(!visited[i]) {
               visited[i] = true;
               que.push(i);
            }
         }
      }
   }
}
bool isConnected() {
   bool *vis = new bool[NODE];
   //for all vertex u as start point, check whether all nodes are visible or not
   for(int u; u < NODE; u++) {
      for(int i = 0; i < NODE; i++)
         vis[i] = false; //initialize as no node is visited
         traverse(u, vis);
      for(int i = 0; i < NODE; i++) {
         if(!vis[i]) //if there is a node, not visited by traversal, graph is not connected
            return false;
      }
   }
   return true;
}
int main()
{
    int n;
    cin>>n; // number of vertices
    // now to read and write file
    freopen("data2.txt","r",stdin);
    freopen("out2.txt","w",stdout);

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>graph[i][j];
        }
    }

   if(isConnected())
      cout << "The Graph is connected.";
   else
      cout << "The Graph is not connected.";
}

Related Solutions

create a code in JAVA that takes arguments to do a bfs(breadth first search) or a...
create a code in JAVA that takes arguments to do a bfs(breadth first search) or a dfs( depth first search) using a txt file as the graph input. I have made most of the main function as well as a nose function I just need the bfs and dfs functions to work here's what I have so far, the comments that start with TODO are the parts that I need to finish Main.java import java.io.*; import java.util; ArrayList; import java.util.Iterator;...
We can use breadth-first search to find the length of longest simple path in the BFS...
We can use breadth-first search to find the length of longest simple path in the BFS tree starting at s by the simple method of checking each v.d value at the end of the algorithm. BFS is Θ(|V | + |E| and this adds only Θ(|V |) work. Find an even easier approach that adds only constant time (Θ(1)) work via a simple modification to the BFS algorithm.
C Programming Question: Write a C - program to implement the following three operations: a) Breadth-first...
C Programming Question: Write a C - program to implement the following three operations: a) Breadth-first search using Adjacency List b) Breadth-first search using Adjacency Matrix c) Check whether a given graph is Bipartite using Breadth-first search (adjacency list).​​​​​​ Please take your time, but do submit the correct and full code. Thank you very much.
3.1 Bratko states that iterative deepening combines the best properties of breadth-first search and depth-first search...
3.1 Bratko states that iterative deepening combines the best properties of breadth-first search and depth-first search and is therefore, in practice, often the best choice amongst the basic search methods. Discuss this statement. 3.2 Discuss the concept of the ‘locality’ of the effects of actions in the context of planning problems.
Write a Java program that implements the Depth-First Search (DFS) algorithm. Input format: This is a...
Write a Java program that implements the Depth-First Search (DFS) algorithm. Input format: This is a sample input from a user. 3 2 0 1 1 2 The first line (= 3 in the example) indicates that there are three vertices in the graph. You can assume that the first vertex starts from the number 0. The second line (= 2 in the example) represents the number of edges, and following two lines are the edge information. This is the...
Use C programming to Implement the breadth-first tree traversal. The tasks are: a) Build the tree....
Use C programming to Implement the breadth-first tree traversal. The tasks are: a) Build the tree. b) Perform breadth first traversal on the tree that you have built at step a). Note: "Please comment the program"
Sorting with Binary Search Tree This assignment asks you to sort the lines of an input...
Sorting with Binary Search Tree This assignment asks you to sort the lines of an input file (or from standard input) and print the sorted lines to an output file (or standard output). Your program, called bstsort (binary search tree sort), will take the following command line arguments: % bstsort [-c] [-o output_file_name] [input_file_name] If -c is present, the program needs to compare the strings case sensitive; otherwise, it's case insensitive. If the output_file_name is given with the -o option,...
In this assignment, you will create a Java program to search recursively for a file in...
In this assignment, you will create a Java program to search recursively for a file in a directory. • The program must take two command line parameters. First parameter is the folder to search for. The second parameter is the filename to look for, which may only be a partial name. • If incorrect number of parameters are given, your program should print an error message and show the correct format. • Your program must search recursively in the given...
Write a program in C++ to implement Lamport’s logical clocks. Your program should take as input...
Write a program in C++ to implement Lamport’s logical clocks. Your program should take as input a description of several process schedules (i.e., lists of send, receive or print operations). The output of your program will be a linearization of these events in the order actually performed, annotated with Lamport clock values. The input of the program will be a collection of processes, each with a list of operations to perform. The processes are named p1...pn for some n (you...
For this computer assignment, you are to write a C++ program to implement a class for...
For this computer assignment, you are to write a C++ program to implement a class for binary trees. To deal with variety of data types, implement this class as a template. Most of the public member functions of the BinaryTree class call private member functions of the class (with the same name). These private member functions can be implemented as either recursive or non-recursive, but clearly, recursive versions of these functions are preferable because of their short and simple implementations...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT