# Given the adjacency matrix of a connected undirected simple graph, find a spanning tree for this graph using depth first search.

Given the adjacency matrix of a connected undirected simple graph, find a spanning tree for this graph using depth-first search.

#include <bits/stdc++.h>
using namespace std;

//making a class named as Graph to implement Graph
class Graph {
public:
//making maps to keep the data of visited vertex and Matrix
map<int, bool> visited;

void DFS(int v);
};
//Functon to add a new edge to the Graph
{
}
//DFS Traversal in the graph with the use of following Function
void Graph::DFS(int v)
{

//The vertex is now visited and now its marked as true in the map
visited[v] = true;
cout << v << "->";

list<int>::iterator i;
//iterating through all the vertex in the list and if not visited
//then doing DFS on it
if (!visited[*i])
DFS(*i);
}

int main()
{
Graph g;
cout<<"Enter the Number of Vertex in the Graph"<<endl;
int n;
cin>>n;

vector<vector<int>>v;
vector<int>temp;
vector<int>vertexlist;
cout<<"Enter the Vertex List:"<<endl;
vertexlist.push_back(0);
for(int i=0; i<n; i++){
int y;
cin>>y;
vertexlist.push_back(y);
}
v.push_back(vertexlist);
cout<<"Enter the Adjacency Matrix row wise"<<endl;
for(int i=1; i<=n; i++){
cout<<"Enter Row no "<<i<<endl;
for(int j=0; j<=n; j++){
if(j==0){
temp.push_back(vertexlist[i]);
}
else{
int x;
cin>>x;
temp.push_back(x);
if(x==1){
}
}
}
v.push_back(temp);
temp.clear();
}
cout<<endl;
cout<<"Here is the Adjacency Matrix. "<<endl<<endl;
for(int i=0; i<=n; i++){
for(int j=0; j<=n; j++){
cout<<v[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;

int i;
cout<<"Enter the Vertex from Which Spanning Tree Should Start"<<endl;
cin>>i;
cout << "Following is the Spanning Tree Using Depth First Traversal"
" (starting from vertex "<<i<<"\n";
g.DFS(i);cout<<"end"<<endl;

cout<<endl<<"Completed \n";

return 0;
}

OUTPUT:

The Graph of the above output is here.