Write a function that returns true (1) if there is an edge between give vertices u and v, otherwise false (0), in an directed graph which is rep adiacency lists
Write a function that returns true (1) if there is an edge between give vertices u and v, otherwise false (0), in an directed graph which is rep adiacency lists
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
Related questions
Question
c or c++
Expert Solution
Program
// C++ program to check if there is exist a path between two vertices u and v
// of a graph.
#include<iostream>
#include <list>
using
namespace
std;
// This class represents a directed graph using adjacency list
// representation
class
Graph
{
int
V;
// No. of vertices
list<
int
> *adj;
// Pointer to an array containing adjacency lists
public
:
Graph(
int
V);
// Constructor
void
addEdge(
int
v,
int
w);
// function to add an edge to graph
bool
isReachable(
int
s,
int
d);
};
Graph::Graph(
int
V)
{
this
->V = V;
adj =
new
list<
int
>[V];
}
void
Graph::addEdge(
int
v,
int
w)
{
adj[v].push_back(w);
// Add w to v’s list.
}
// A BFS based function to check whether d is reachable from s.
bool
Graph::isReachable(
int
s,
int
d)
{
// Base case
if
(s == d)
return
true
;
// Mark all the vertices as not visited
bool
*visited =
new
bool
[V];
for
(
int
i = 0; i < V; i++)
visited[i] =
false
;
// Create a queue for BFS
list<
int
> queue;
// Mark the current node as visited and enqueue it
visited[s] =
true
;
queue.push_back(s);
// it 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();
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 this adjacent node is the destination node, then
// return true
if
(*i == d)
return
true
;
// Else, continue to do BFS
if
(!visited[*i])
{
visited[*i] =
true
;
queue.push_back(*i);
}
}
}
// If BFS is complete without visiting d
return
false
;
}
// Driver program to test methods of graph class
int
main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
int
u = 1, v = 3;
if
(g.isReachable(u, v))
cout<<
"\n There is a path from "
<< u <<
" to "
<< v;
else
cout<<
"\n There is no path from "
<< u <<
" to "
<< v;
u = 3, v = 1;
if
(g.isReachable(u, v))
cout<<
"\n There is a path from "
<< u <<
" to "
<< v;
else
cout<<
"\n There is no path from "
<< u <<
" to "
<< v;
return
0;
}
Step by step
Solved in 2 steps
Knowledge Booster
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.Recommended textbooks for you
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)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
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)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education