I want to find MST of a graph which has more than 2000 nodes. The problem I am getting is that I can not make adjacency matrix of size more than 1500X1500 (If size is more than this segmentation fault is occurring because we can create an array of max 10^7 size). How could this be done?
There are a number of issues here to think about.
You should be able to allocate an array of size 1500 × 1500 without causing a segfault, provided that you do it correctly. If you try to allocate an array of this size on the stack (that is, as a local variable), then you will probably blow out your stack space, which is likely what's causing the error you're getting. However, if you allocate it using new[] or by using a std::vector, then the memory is stored in the heap, which is designed to be able to accommodate requests like that.
Adjacency matrices are only one way to represent a graph, and they're known to be space hogs that are only really a good idea if you're working with extremely dense graphs. The most common alternative is the adjacency list, which uses way less storage space, is easy to implement, and supports many relevant operations faster than an adjacency matrix. You might want to consider making this switch in conjunction with putting things on the heap and not on the stack.