Find Path (Given source and destination) Path Cost (Given source and destination)

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
100%

Hello i need help with my data structure project in c++:

the requirement is that I have to

  1. Find Path (Given source and destination)
  2. Path Cost (Given source and destination)

Using the image attached.

this is my program I have done so far:

Main.cpp

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

int main()
{
int ch;
Graph g(0);
cout << "Graph Operations" << endl << endl;
cout << "1-2 Create Graph" << endl;
cout << "[1] Adjacency List" << endl;
cout << "[2] Adjacency Matrix" << endl << endl;

cout << "3-4 Graph Traversal" << endl << endl;
cout << "[3] BFS Traversal" << endl;
cout << "[4] DFS Traversal" << endl << endl;

cout << "5-6 Find Path/Cost" << endl << endl;
cout << "[5] Find Path (Given source and destination) " << endl;
cout << "[6] Path Cost (Given source and destination) " << endl;

cout << "[0] Close Program" << endl;
cout << "Enter choice: ";
cin >> ch;
if (ch == 1)
{
g.addEdge(0, 5);
g.addEdge(0, 6);
g.addEdge(1, 3);
g.addEdge(1, 5);
g.addEdge(2, 4);
g.addEdge(3, 1);
g.addEdge(3, 2);
g.addEdge(3, 4);
g.addEdge(4, 0);
g.addEdge(4, 2);
g.addEdge(5, 0);
g.addEdge(6, 0);
g.addEdge(6, 3);
g.printGraph();
cout << endl << endl;

}
else if (ch == 2)
{
g.addEdge2(0, 5);
g.addEdge2(0, 6);
g.addEdge2(1, 3);
g.addEdge2(1, 5);
g.addEdge2(2, 4);
g.addEdge2(3, 1);
g.addEdge2(3, 2);
g.addEdge2(3, 4);
g.addEdge2(4, 0);
g.addEdge2(4, 2);
g.addEdge2(5, 0);
g.addEdge2(6, 0);
g.addEdge2(6, 3);
g.printGraph2();


}
else if (ch == 3)
{
int j;
cout << endl << "BFS Traversal..." << endl;
cout << "Input your prefered source / start: ";
cin >> j;
cout << endl;
g.BFS(j);
}
else if (ch == 4)
{
int k;
cout << endl << "DFS Traversal..." << endl;
cout << "Input your prefered source / start: ";
cin >> k;
cout << endl;
g.DFS(k);
}
cout << endl << endl;
}

 

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

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

public:
Graph(int);
void addEdge(int u, int v);
void addEdge2(int u, int v);
void printGraph();
void printGraph2();
void DFS(int v);
void BFS(int s);
};

 

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);
}
}
}
}

 

can someone show me how to find the path and path cost

(a)
Pointer
Index of
edge nodes
Weight
to next
adjacent vertex
edge node
graph
[0] |"Atlanta
5
800
6.
600
[1] "Austin
3
200
160 /
[2] "Chicago
4 1000
[3] "Dallas
1
200
2
900
4
780
[4] "Denver
0 1400
2 1000 /
[5] "Houston
800
[6] "Washington"
3 1300
600
[7]
[8]
[9]
Transcribed Image Text:(a) Pointer Index of edge nodes Weight to next adjacent vertex edge node graph [0] |"Atlanta 5 800 6. 600 [1] "Austin 3 200 160 / [2] "Chicago 4 1000 [3] "Dallas 1 200 2 900 4 780 [4] "Denver 0 1400 2 1000 / [5] "Houston 800 [6] "Washington" 3 1300 600 [7] [8] [9]
Dallas
1300
7
Washington
Austin
6
6
1400
Denver
Atlanta
160
Chicago
Houston
008
008
0001
000
006
007
007
Transcribed Image Text:Dallas 1300 7 Washington Austin 6 6 1400 Denver Atlanta 160 Chicago Houston 008 008 0001 000 006 007 007
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 6 steps with 6 images

Blurred answer
Knowledge Booster
Functions
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