Code:
//global variable for colorint color[1001] = {0};
//prototype for Depths First Search
int DFS(int array[1001][1001], int vertex, int numVertices, int reset);
int main (int argc, char** argv)
{
//declare variables
FILE *in = NULL;
int i = 0;
int j = 0;
int numVertices = 0;
int vertex1 = 0, vertex2 = 0;
int num2 = 0;
int array[1001][1001] = {0};
//check to make sure enough arguments
if(argc != 2){
printf("wrong entry\n");
return 1;
}
//open file in read only
in = fopen(argv[1], "r");
//check to make sure file exists
if(in == NULL){
printf("File can not be opened.\n");
return 2;
}
//read in the first line of the input, which will give you the number of Vertices
fscanf(in, "%d", &numVertices);
//create the matrix of the graph
for(i=1; i<numVertices; i++)
{
fscanf(in, "%d %d", &vertex1, &vertex2);
array[vertex1][vertex2] = 1;
array[vertex2][vertex1] = 1;
}
int num = 0, smallest = 0;
//This for loop will go through every vertex. First it checks to see if the vertex has been visited.
//if so skip it, if not then call DFS. Then check to see if the returning component is the smallest.
//If not skip it, if so then put it in 'smallest'. Lastly bump the counter which keeps track of the number of components
for(i = 1; i<numVertices + 1; i++)
{
if(color[i] == 0)
{
num = DFS(array, i, numVertices, 1);
if(smallest > num || smallest == 0)
{
smallest = num;
}
num2++;
}
}
//print outputs
printf("The number of connected components is %d\n", num2);
printf("The smallest component has %d vertices\n", smallest);
}
//this function first sets the vertex to being visited, next it checks to see if the count has been changed yet
//if so then skip over it, if not change to zero. Next the function bumps the counter. The for loop takes the
//vertice that you brought down and goes through all of the other vertices. If there is a connecting vertex
//and it has not already been visited then recursively call DFS. Lastly return the number of times DFS was called
//recursively which will provide the number of vertices on each component.
int DFS(int array[1001][1001], int vertex, int numVertices, int reset)
{
int i = 0;
static int count = 0;
color[vertex] = 1;
if(reset == 1)
{
count = 0;
}
count++;
for(i = 1; i<numVertices+1; i++)
{
if((array[vertex][i] == 1) && (color[i] == 0))
{
DFS(array, i, numVertices, 0);
}
}
return count;
}
I couldn't figure it out, so I ended up making a two dimensional array, which is wayy wrong.