Click here to Skip to main content
15,442,578 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Write a complete C++ program that implements the Depth First Search (DFS)

-You must ask the user to enter the number of vertices n for your graph, and go over the source vertices or nodes in numerical or alphabetical order.

-Based on the number of vertices, randomly generate the edges.

-Assume you are using the Adjacency Matrix to represent your graph.

-Assume you have an un-directed graph.

What I have tried:

How can I amend the code according to the above information?
C++
#include <iostream> 
#include <list> 
using namespace std; 
//graph class for DFS travesal  
class DFSGraph 
{ 
    int V;    // No. of vertices 
    list<int> *adjList;    // adjacency list

    void DFS_util(int v, bool visited[]);  // A function used by DFS

public: 
    // class Constructor
    DFSGraph(int V)
    {
        this->V = V; 
        adjList = new list<int>[V]; 
    }

    // function to add an edge to graph 
    void addEdge(int v, int w)
    {
        adjList[v].push_back(w); // Add w to v’s list.
    }
     
    void DFS();    // DFS traversal function 
};

void DFSGraph::DFS_util(int v, bool visited[]) 
{ 
    // current node v is visited 
    visited[v] = true; 
    cout << v << " "; 
   
    // recursively process all the adjacent vertices of the node 
    list<int>::iterator i; 
    for(i = adjList[v].begin(); i != adjList[v].end(); ++i) 
        if(!visited[*i]) 
            DFS_util(*i, visited); 
}

// DFS traversal 
void DFSGraph::DFS() 
{ 
    // initially none of the vertices are visited 
    bool *visited = new bool[V]; 
    for (int i = 0; i < V; i++) 
        visited[i] = false; 

    // explore the vertices one by one by recursively calling  DFS_util
    for (int i = 0; i < V; i++) 
        if (visited[i] == false) 
            DFS_util(i, visited); 
}
   
int main() 
{ 
    // Create a graph
    DFSGraph gdfs(5); 
    gdfs.addEdge(0, 1); 
    gdfs.addEdge(0, 2); 
    gdfs.addEdge(0, 3);
    gdfs.addEdge(1, 2); 
    gdfs.addEdge(2, 4);
    gdfs.addEdge(3, 3); 
    gdfs.addEdge(4, 4);
 
    cout << "Depth-first traversal for the given graph:"<<endl; 
    gdfs.DFS(); 

    return 0; 
}
Posted
Updated 24-Dec-20 10:21am
v4
Comments
Richard MacCutchan 20-Dec-20 12:10pm    
Please use the Improve question link above, add your code, and explain what the errors are. No one here is going to do your work for you.
Patrice T 20-Dec-20 12:19pm    
Show you code with error messages to get help.
Member 15026042 20-Dec-20 12:27pm    
The problem is that I do not know C ++ well. I am in my first year at the university and have started learning programming
Patrice T 20-Dec-20 12:50pm    
and the error messages are ?
Richard MacCutchan 20-Dec-20 13:17pm    
Sorry, I know nothing about adjacency matrices or depth first searches. You need to explain what error messages you are seeing.

you are in the first half of your homework. Read the task description more careful and implement it more precise.
So you should ask the user how many vertices should be used. You can use cin for input.
Than you should create randome vertices, for that you can use rand function.

tip: the bool for visited should be a flag on DFS.
 
Share this answer
 
Comments
Member 15026042 20-Dec-20 13:25pm    
Can you help me write the code, I searched the internet but couldn't find the information I need, the above code found it in the internet
Here's one way to get a random value :
C++
// obtain a random value scaled to be within limits

template< typename T >
inline T GetRandomValue( T minval, T maxval )
{
	return ( rand() * ( maxval - minval ) / (T) RAND_MAX ) + minval;
}
The random number generator must first be seeded by calling srand one time, usually at the beginning of main. For a random sequence call it like this :
C++
srand( time( nullptr ) % RAND_MAX );
for a repeatable sequence call srand with a constant value, like 47. So after you ask the user how many vertices to use you need to have a for loop and call GetRandomValue to get the value to use for each vertex.
 
Share this answer
 
Comments
Member 15026042 20-Dec-20 15:02pm    
thanks you vary much
If you just started programming, copying code from an unfamiliar source won't help you very well. If you're just in your first year, that code likely contains elements you are not familiar with, and as a result it will be harder for you to solve your task, rather than easier. It's better to start from scratch, go as far as you can go, and then come to a site like this and tell us, exactly, what problem you have.

Knowing what questions to ask is a skill, and it is crucial in learning. Ask your questions well, and you will receive useful anwers, that help you to both learn, and complete your task. Bad questions may help you complete the task, but will not help you learn, and you will be dependend on help for a long time.

If you start from other people's code, you will not be able to ask the right questions, because you don't even know what that code does or doesn't do! If you feel that you understand parts of that code well enough that you could reimplement it yourself without looking at the original code again, then, fine, use it. But for those parts you don't understand, as a student, you're better off deleting it right away, and then implement whatever is missing in a manner that you do understand!

In the end your goal should be code that you understand so well that you could explain every detail of it to someone else. Only then did you learn something useful!
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900