Graph represented by an adjacency matrix in C++

I’m working on my data structures knowledge and wanted to create a graph with a small DFS driver which simply prints the nodes as it visits them. Here’s my graph class:

#ifndef GRAPH_H_
#define GRAPH_H_

#include <stack>
#include <random>
#include <iterator>
#include <unordered_map>
#include <unordered_set>

template <typename T>
class Graph {
  public:
    Graph(bool directed) : directed{directed}, adj_matrix{} {}
    ~Graph() {}
    void add_edge(const T& start, const T& end) {
      adj_matrix[start][end] = true;
      adj_matrix[start][start] = false;
      adj_matrix[end][end] = false;
      adj_matrix[end][start] = directed ? false : true;
    }

    void DFS(T const *start=nullptr) const {
      if(!adj_matrix.size())
        return;
      if(start==nullptr) {
        DFS_helper(get_random_node());
      } else {
        DFS_helper(*start);
      }
    }

    void DFS_helper(const T& start) const {
      std::unordered_set<T> visited;
      std::stack<T> s;
      s.push(start);
      while(!s.empty()) {
        T top = s.top();
        s.pop();
        // If top is unvisited
        if(visited.find(top) == std::end(visited)) {
          // visit it
          visited.insert(top);
          std::cout << top << ' ';
          for(const auto& adj_node: get_adjacent_nodes(top)) {
             s.push(adj_node);
          }
        }
      }
      std::cout << 'n';
    }

  private:
    std::vector<T> get_adjacent_nodes(const T& v) const {
        std::vector<T> adj;
        for(const auto& pair: adj_matrix.at(v)) {
            T neighbor = pair.first;
            bool is_neighbor = pair.second;
            if(is_neighbor) {
                adj.push_back(neighbor);
            }
        }
        return adj;
    }
    T get_random_node() const {
      auto random_it = std::next(std::begin(adj_matrix), std::rand() % (adj_matrix.size()-1));
      return random_it->first;
    }
    const bool directed;
    std::unordered_map<T, std::unordered_map<T, bool>> adj_matrix;
};

#endif //GRAPH_H_

And here’s my driver (inspired from this Wikipedia image):

#include <iostream>
#include "graph.h"

int main() {
  bool directed = false;
  Graph<char> g(directed);
  g.add_edge('A', 'B');
  g.add_edge('B', 'D');
  g.add_edge('A', 'E');
  g.add_edge('E', 'F');
  g.add_edge('A', 'C');
  g.add_edge('C', 'G');
  g.add_edge('B', 'F');

  char a = 'A';
  g.DFS(&a);
}

I’m interested in any tips or recommendations!

Your code looks reasonable, yet I have one suggestion: decouple algorithms from output:

std::vector<T> DFS(T const *start=nullptr) const {
    if(!adj_matrix.size())
        return std::vector<T>();
    if(start==nullptr) {
        return DFS_helper(get_random_node());
    } else {
        return DFS_helper(*start);
    }
}

std::vector<T> DFS_helper(const T& start) const {
    std::unordered_set<T> visited;
    std::unordered_map<T, T*> parents {{start, nullptr}};
    std::stack<T> s;
    std::vector<T> nodes;
    s.push(start);
    while(!s.empty()) {
        T top = s.top();
        s.pop();
        // If top is unvisited
        if(visited.find(top) == std::end(visited)) {
            // visit it
            visited.insert(top);
            nodes.push_back(top);
            for(const auto& adj_node: get_adjacent_nodes(top)) {
                s.push(adj_node);
                parents[adj_node] = &top;
            }
        }
    }
    return nodes;
}

Suppose what happens if your friend needs to run your DFS on a large graph. Most definitely, he or she will be overwhelmed with all the output. So, let the DFS return silently a list of visited nodes; only after that print the nodes if need be.