Description
For this practice, you are to implement the DFS algorithm.
One graph has been set up in the class Graph constructor. Please finish the following functions :
(1) bool isDirected() : Check whether the given graph in the DFS constructor is a directed graph or not.
(2) DFS(const int v): the Input v is the starting vertex to do DFS. This function initializes the private member bool* visit and calls DFS_visit(const int v).
(3) DFS_visit(const int v): Visit all previously unvisited vertices that are reachable from the vertex v. The vertex with a lower index should be visited first.
For example, while both vertex 1 and vertex 2 can be visited by vertex 0, you should visit vertex 1 first because it has a lower index.
<Note : You should not change the code in main>
#include<iostream>
#define vertexNumber 8
using namespace std;
class Graph{
private:
int adjacencyMatrix[vertexNumber][vertexNumber];
bool* visited;
public:
Graph();
void DFS(const int v);
void DFS_visit(const int v);
void printVertex(int v){
// This function is just used to guarantee that you won't
// output the wrong format
cout<<v<<" ";
}
bool isDirected();
};
Graph::Graph(){
for(int i=0;i<vertexNumber;i++){
for(int j=0;j<vertexNumber;j++){
adjacencyMatrix[i][j]=0;
}
}
adjacencyMatrix[0][2]=1; adjacencyMatrix[1][0]=1;
adjacencyMatrix[1][4]=1; adjacencyMatrix[2][5]=1;
adjacencyMatrix[2][6]=1; adjacencyMatrix[3][1]=1;
adjacencyMatrix[4][7]=1; adjacencyMatrix[6][7]=1;
adjacencyMatrix[7][3]=1; adjacencyMatrix[7][5]=1;
}
bool Graph::isDirected(){
}
void Graph::DFS(const int v){
// Input v is used to set the start vertex
}
void Graph::DFS_visit(const int v){
// Visit all previously unvisited vertices that are reachable from vertex v
// When you find a new vertex, print it out
printVertex(v);
// TODO
}
int main(){
Graph g;
int start;
cin>>start;
if(g.isDirected()){
cout<<"Directed!"<<endl;
}else{
cout<<"Undirected!"<<endl;
}
g.DFS(start);
}
Input
Start vertex
Output
Directed?
DFS vertexes sequence
Tags
12485