Dynamic bool array in C++

You could consider using Boost's builtin multi-dimensional array as a less brittle alternative. As noted the code you supplied will work, but has issues.

What about:

std::vector<std::vector<bool> >   Madj(4,std:vector<bool>(4, false));

Unfortunately std::vector<bool> is specialized to optimize for size (not speed).
So it can be inefficient (especially if used a lot). So you could use an int array (if you find the bool version is slowing you down).

std::vector<std::vector<int> >   Madj(4,std:vector<int>(4, 0));

Note: int can be used in a boolean context and auto converted (0 => false, any other number is true (though best to use 1).

At least IMO, if you insist on doing this at all, you should normally do it rather differently, something like:

class bool_array { 
     bool *data_;
     size_t width_;

     // no assignment or copying
     bool_array &operator=();
     bool_array(bool_array const &);
public:
     bool_array(size_t x, size_t y) width_(x) {
         data_ = new bool[x*y];
         std::fill_n(data_, x*y, false);
     }

     bool &operator()(size_t x, size_t y) { 
         return data_[y+width_+x];
     }

     ~bool_array() { delete [] data_; }
};

This can be embellished (e.g., using a proxy to enforce constness), but the general idea remains: 1) allocate your bools in a single block, and 2) put them into a class, and 3) overload an operator to support reasonably clean indexing into the data.

You should also consider using std::vector<bool>. Unlike other instantiations of std::vector, it's not a container (as the standard defines that term), which can be confusing -- but what you're creating isn't a container either, so that apparently doesn't matter to you.

bool **Madj = new bool*[NodeCount];
for (int i=0; i<NodeCount; i++){
    Madj[i] = new bool [NodeCount];
    for (int j=0; j<NodeCount; j++){
        Madj[i][j] = false;
    }
}

If the first call to new succeeds but any of the ones in the loop fails, you have a memory leak since Madj and the subarrays up to the current i are not deleted. Use a vector<vector<bool> >, or a vector<bool> of size NodeCount * NodeCount. With the latter option, you can get to element (i,j) with [i*NodeCount+j].

I think this looks fine!

Depending on the use, you could use std::vector instead of a raw array.

But its true that the first Madj declaration should be "extern" to avoid linking or shadowing errors.

If you have only bools, consider using bitsets. You can combine that with other containers for multidimensional arrays, e.g vector<bitset>.