(Main.cpp) #include #include "Data.h" using namespace std; int main() {

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question

Please put a label if the code is Data.h,Implementation and main.cpp
Example Code:

(Main.cpp)

#include <iostream>
#include "Data.h"
using namespace std;

int main()
{
  int ch;
  Graph g(8);
  cout << "Graph Operations" << endl;
  cout << "[1] Adjacency List" << endl;
  cout << "[2] Adjacency Matrix" << endl;
  cout << "Enter choice: ";
  cin >> ch;
  if (ch == 1)
  {
    g.addEdge(0, 6);
    g.addEdge(1, 5);
    g.addEdge(2, 0);
    g.addEdge(2, 4);
    g.addEdge(3, 5);
    g.addEdge(4, 1);
    g.addEdge(4, 3);
    g.addEdge(5, 7);
    g.addEdge(6, 1);
    g.addEdge(6, 7);
    g.printGraph();
    cout << endl << "DFS Traversal..." << endl;
    g.DFS(1);
    cout << endl << endl;
    cout << endl << "BFS Traversal..." << endl;
    g.BFS(3);
  }
  else if (ch == 2)
  {
    g.addEdge2(0, 6);
    g.addEdge2(1, 5);
    g.addEdge2(2, 0);
    g.addEdge2(2, 4);
    g.addEdge2(3, 5);
    g.addEdge2(4, 1);
    g.addEdge2(4, 3);
    g.addEdge2(5, 7);
    g.addEdge2(6, 1);
    g.addEdge2(6, 7);
    g.printGraph2();
  }
  cout << endl << endl;
}
______________________________________________________________________________

(Data.H)

#pragma once
#include <list>
#include <iostream>
using namespace std;


class Graph
{
private:
  int V;
  list <int> *adj;                       //Programmer2
  int **adj2;                            //Programmer2
  void DFSUtil(int v, bool visited[]);   //Lead
  void BFSUtil(int s, bool visited[]);   //Lead

 public:
  Graph(int);                       //All
  void addEdge(int u, int v);       //All
  void addEdge2(int u, int v);      //Programmer2
  void printGraph();                //All
  void printGraph2();               //Programmer2
  void DFS(int v);                  //Lead
  void BFS(int s);                  //Lead
};
____________________________________________________________________________________

(Implementation.cpp)

#include <iostream>
#include <list>
#include "Data.h"
using namespace std;

Graph::Graph(int x)
{
  V = x;
  adj = new list <int> [V];
  adj2 = new int* [V];
  for (int i = 0; i < V; i++)
      adj2[i] = new int[V];
  for (int i = 0; i < V; i++)
    for (int j = 0; j < V; j++)
      adj2[i][j] = 0;

}

void Graph::addEdge(int u, int v)
{
  adj[u].push_back(v);
}

void Graph::addEdge2(int u, int v)
{
  adj2[u][v] = 1;
}

// A utility function to print the adjacency list
// representation of graph
void Graph::printGraph()
{
  cout << "Adjacency List..." << endl;
  for (int v = 0; v < V; ++v)
  {
    cout << "V[" << v << "]";
    for (auto x : adj[v])
      cout << " -> " << x;
    cout << endl;
  }
}

void Graph::printGraph2()
{
  cout << "Adjacency Matrix..." << endl << endl;
  cout << "\t";
  for (int i = 0; i < V; i++)
    cout << "V[" << i << "]" << "\t";
  cout << endl;
  for (int i=0; i<V; i++)
  {
    cout << "V[" << i << "]" << "\t";
    for (int j = 0; j < V; j++)
      cout << adj2[i][j] << "\t";
    cout << endl;
  }
  cout << endl;
}

void Graph::DFSUtil(int v, bool visited[])
{
  // Mark the current node as visited and
  // print it
  visited[v] = true;
  cout << v << " ";

  // Recur for all the vertices adjacent
  // to this vertex
  list<int>::iterator i;
  for (i = adj[v].begin(); i != adj[v].end(); ++i)
    if (!visited[*i])
      DFSUtil(*i, visited);
}

// DFS traversal of the vertices reachable from v.
// It uses recursive DFSUtil()
void Graph::DFS(int v)
{
  // Mark all the vertices as not visited
  bool *visited = new bool[V];
  for (int i = 0; i < V; i++)
    visited[i] = false;

  // Call the recursive helper function
  // to print DFS traversal
 
  DFSUtil(v, visited);
  for(int i=0; i< V; i++)
    if (!visited[i])
      DFSUtil(i, visited);

  for (int i = 0; i < V; i++)
    if (!visited[i])
      cout << i << " ";
}

void Graph::BFS(int s)
{
  // Mark all the vertices as not visited
  bool *visited = new bool[V];
  for (int i = 0; i < V; i++)
    visited[i] = false;

  BFSUtil(s, visited);
  for (int i = 0; i < V; i++)
    if (!visited[i])
      BFSUtil(i, visited);

  for (int i = 0; i < V; i++)
    if (!visited[i])
      cout << i << " ";
}

void Graph::BFSUtil(int s, bool visited[])
{
  // Create a queue for BFS
  list<int> queue;

  // Mark the current node as visited and enqueue it
  visited[s] = true;
  queue.push_back(s);

  // 'i' will be used to get all adjacent
  // vertices of a vertex
  list<int>::iterator i;

  while (!queue.empty())
  {
    // Dequeue a vertex from queue and print it
    s = queue.front();
    cout << s << " ";
    queue.pop_front();

    // Get all adjacent vertices of the dequeued
    // vertex s. If a adjacent has not been visited,  
    // then mark it visited and enqueue it
    for (i = adj[s].begin(); i != adj[s].end(); ++i)
    {
      if (!visited[*i])
      {
        visited[*i] = true;
        queue.push_back(*i);
      }
    }
  }
}


Create a separate library for your Graph ADT. You must have at
least the following files:
File
Data.h
Implementation.cpp
Main.cpp
Purpose
contains the data definition of the
class.
contains the C++ codes of the class
operations/functions.
main program.
Implement linked list as described.
• Create necessary functions in your main program.
• Include validations of inputs.
Specify the group member in-charge of the codes by indicating
his name as comments.
Transcribed Image Text:Create a separate library for your Graph ADT. You must have at least the following files: File Data.h Implementation.cpp Main.cpp Purpose contains the data definition of the class. contains the C++ codes of the class operations/functions. main program. Implement linked list as described. • Create necessary functions in your main program. • Include validations of inputs. Specify the group member in-charge of the codes by indicating his name as comments.
Expert Solution
steps

Step by step

Solved in 2 steps

Blurred answer
Knowledge Booster
Algebraic Expressions
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
  • SEE MORE QUESTIONS
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education