DFS: Existence of Spanning Tree

Question

Can a depth-first-search be used to determine if some graph is connected given access to an arrays of edges and vertices of unknown size, with only the starting vertex as the input data?

struct node {
  int parent, rank;
};
typedef struct node node;

struct edge {
  int fromvertex, tovertex;
  float weight;
};
typedef struct edge edge;

node* nodes;
edge* edges;
int hasspantree(int startvertex)
{
  //find spanning tree?
}

Nodes and edges are assigned in a function that runs before the depth-first search, as so:

scanf("%d", nodecount);
scanf("%d", edgecount);
if ((nodes = malloc(*nodecount * sizeof(node))) == NULL) {
  printf("nodes malloc failed"); exit(1);
}
if((edges = malloc(*edgecount * sizeof(edge))) == NULL) {
  printf("edges malloc failed"); exit(1);
}

I can do it given this function declaration:

int hasspantree(int startvertex, int edgecount, int nodecount)

But I'd like to be able to do it with the previous declaration.

Answer 1

The short answer is, given your data (the starting node and 2 lists of unknown size), that is impossible to perform the DFS, simply because you don't know your graph (you don't know what is in memory graph-related data or garbage, as you don't know how to stop). So you cannot analyse an unknown graph. The question is whether the size of the graph (by the size of the graph I mean the size of the 2 arrays that define the graph in your case) is explicit (and it isn't, as your function doesn't take a size parameter) or implicit (the data structure contains the size or has a particular way of indicating it). So, you can use a terminator (a NULL pointer, similar to the use of the NUL character in strings) to indicate the end of the array. Also, you could have a global variable, but we all know that's not a good practice.