Write a C/C++ program that inputs a simple, unweighted, undirected graph from a

Question

Write a C/C++ program that inputs a simple, unweighted, undirected graph from a file and outputs vertices in the order visited by a DFS. The program should take two command-line arguments: the name of the graph file and the index of the vertex on which to start the DFS. Whenever your DFS has a choice between more than one child vertices, always choose the lower-indexed vertex first. A user should see something very similar to the following when invoking your program.

>./DFS graph2.txt 3

3 4 0 7

>

Explanation / Answer

#include<iostream>
#include<fstream>
#include<list>
#include<stdlib.h>
using namespace std;
class DSFGraph
{
        int V;
        list<int> *adj;
        void DSFprint(int v, bool visited[]);
        public:
        DSFGraph(int V);
        void addEdge(int v, int w);
        void DFS(int v);
};
DSFGraph::DSFGraph(int V)
{
        this->V = V;
        adj = new list<int>[V];
}
void DSFGraph::addEdge(int v, int w)
{
        adj[v].push_back(w); // Add w to v’s list.
}
void DSFGraph::DSFprint(int v, bool visited[]) // print DSF traversal
{
        visited[v] = true;
        cout << v << " ";
        list<int>::iterator i;
        for (i = adj[v].begin(); i != adj[v].end(); ++i)
                if (!visited[*i])
                        DSFprint(*i, visited);
}
//DFS traversal of the vertices reachable from v
void DSFGraph::DFS(int v) // mark as vertexs are not visited
{
        bool *visited = new bool[V];
        for (int i = 0; i < V; i++)
                visited[i] = false;
        DSFprint(v, visited);
}
int main(int argc, char **argv)
{
        DSFGraph g(4);
        char vertex[3];
        int i=0, a[10];
        FILE *fp;
        fp = fopen(argv[1], "r");
        while(fscanf(fp, "%s", vertex)!=EOF){
         a[i] = atoi(vertex);
         cout<<" "<<a[i++];
        }
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
        cout << " Depth First Traversal (starting from vertex:"<<atoi(argv[2])<<") ";
        g.DFS(atoi(argv[2]));
        cout<<" ";
        return 0;
}

--------Simple output ---------------------------

$ ./DSF graph2.txt 2
2 3 4 5 6 1 0
Depth First Traversal (starting from vertex:2)
2 0 1 3

./DSF graph2.txt 3
2 3 4 5 6 1 0
Depth First Traversal (starting from vertex:3)
3

./DSF graph2.txt 1
2 3 4 5 6 1 0
Depth First Traversal (starting from vertex:1)
1 2 0 3

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.