Graph represented by an adjacency matrix in C++
Your code looks reasonable, yet I have one suggestion: decouple algorithms from output: 

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

std::vector&lt;T&gt; DFS_helper(const T&amp; start) const {
    std::unordered_set&lt;T&gt; visited;
    std::unordered_map&lt;T, T*&gt; parents {{start, nullptr}};
    std::stack&lt;T&gt; s;
    std::vector&lt;T&gt; 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&amp; adj_node: get_adjacent_nodes(top)) {
                s.push(adj_node);
                parents[adj_node] = &amp;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.