1. ## Memory Allocation

Hello all,

I had a homework assignment in my cs3050 last week, that I was having trouble with what should be the easiest part.

The homework looked like this:

In this program you will read a file specifying an undirected graph as a list of edges and output the number of connected components as well as the size (number of vertices) of the smallest component. The number of vertices is given on the first line of the input. The vertices are numbered in order from 1 to the total number of vertices. The rest of the input file simply lists the edges in arbitrary order as pairs of vertices, with each edge on a separate line. For example for the following input:
7
1 2
4 5
3 6
2 7
The output is:
The number of connected components is 3
The smallest component has

I had trouble setting up the adjacency list. I knew that I could just use breadths first search or depths first search once I had it, but I have always had trouble with allocating memory. I didn't end up figuring it out before it was due, but I know we are going to be having more like this.

All I need to know is how to get it all into the adjacency list and then I know what to do from there.

2. Let's see what you tried, so we can see where the problems were and help you understand what you did wrong.

3. 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;
}
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.

4. What anduril meant was that you are supposed to try to build the list. So he asked for the code to see in which point of the list you have troubles. However, it seems that you do not have code for a list. Are you interested in building your own list?

5. Oh sorry
I don't have any code for the list. As you can see I took the easy/wrong way out. I am interested in building a list.

6. Originally Posted by Goku
I couldn't figure it out, so I ended up making a two dimensional array, which is wayy wrong.
Actually, you can solve this with a 2-d array or linked lists. Either way, you have a data structure that shows a relationship of each node, and all the neighbors of that node.

An adjacency list is very similar to your 2-d array (array of arrays), except each row is a linked list of neighbors, so you don't have to store data about unconnected nodes. Basically, an adjacency list is an array of linked lists.

Your DFS will behave much the same either way, it's simply whether you look for neighbors by doing
Code:
```DFS()
for (i = 0; i < numVertices; i++)
if adjArray[vertex][i] is connected  // vertex has node i as a neighbor
do DFS from node j```
or something like:
Code:
```DFS()
for (p = vertex->adjList; p != NULL; p = p->next)  // p just walks the linked list of neighbors
do DFS from node p  // note, no need to check if vertex is connected to p, we know they are, since the adj list only contains actual neighbors```

7. How do I allocate the memory for the list once i read in the first line? Right now in my code, I just have the 2 dimensional array that is made 1000 x 1000 then change resize it after I read in the number of vertices.

8. Ok, it seems that you are way to far from having you own list.

I will show you the list I first used and till today, I am still based on it. It is fully commented and its ideal (in my opinion) for educational purposes.
Make sure you read it more than once. Actually I suggest you to study what you will find in the link I am going to share with you.

Here you are : Single linked list

9. Originally Posted by Goku
How do I allocate the memory for the list once i read in the first line? Right now in my code, I just have the 2 dimensional array that is made 1000 x 1000 then change resize it after I read in the number of vertices.
How have you made it this far in your programming classes if you can't create a basic linked list or even dynamically allocate an array of objects? If you don't understand those concepts, you need to study them. Also, if you don't understand what an adjacency list is conceptually, then you need to study that as well. You can't program a solution if you don't even understand the problem.

Once you're clear on the concepts, plan out a rough solution with paper and pencil, then turn that into code, little bits at a time. Start with some basics, like declaring a struct to hold all the pertinent adjacency list information (node visited, etc). Then, dynamically allocate an array of those nodes (using malloc). You need an array with numVertices elements in it.

10. Originally Posted by anduril462
How have you made it this far in your programming classes if you can't create a basic linked list or even dynamically allocate an array of objects?
This seems to be something of a trend. Students who are given homework so obviously above their current skill level. Could a professor really expect one to do graph algorithms without knowledge of a linked list or dynamic array? Hmm....

11. Originally Posted by MacNilly
This seems to be something of a trend. Students who are given homework so obviously above their current skill level. Could a professor really expect one to do graph algorithms without knowledge of a linked list or dynamic array? Hmm....
I don't think that it's fair to say that - You don't know what professor has taught or what resources have been provided. The OP might have not attended class, or read their prescribed text.

12. I go to class everyday, but the problem is in previous classes we have been spoon fed all prototypes and given brief descriptions of what each function does, and basically told what to do. We talked very limitedly about allocating memory and only used it in the very simplest of cases

Then this class starts and we are never shown any code and only talk algorithms without their applications. Then we are given home works like this one and given free reign on what to do. To say the least it is a bit overwhelming.

13. Well, you're on the right path by visiting this site. I joined many years ago, and I learned everything I know about C from here. In particular, the member Prelude has some great tutorials on data structures in the tutorial section, including linked lists.

14. I'll have to check it out, Thank you. And also thank you to everyone else who replied.