Yes that's true, there are efficient heuristic graph algorithms for many problems, for example the travelling salesman problem has several good heuristic algori

Yes that's true, there are efficient heuristic graph algorithms for many problems, for example the travelling salesman problem has several good heuristic algorithms that gives you a short path, but perhaps not the exact shortest. But for problems like connected components, there is only one right answer, a component is connected or it is not, there is no useful heuristic solution. Same goes for all shortest paths, yes A* is heuristic for finding an optimally short path from a specific source to a specific destination, but to get all destination shortest paths you have to visit all the nodes anyway, so there is only one useful solution.