# Thread: Help with the Depth-First algorithm

1. ## Help with the Depth-First algorithm

Hello just wondering if anyone can see where I need to go from here to get the shortest path from each node listed in the program to the root node "A".
Below is the code and then beneath that, two networks of nodes. Each should be put in seperate text files and named.

Any help would be greatly appreciated!

Pyro...

Here is the code:
Code:
```/*Lab Experiment 2, Year 2*/

#include <stdio.h>
#define DINIT 10000

/*Defines a set of related variables*/
struct
{char name;
int length[30];
int visited;
int distance_from_root;
}nodes[100];

/*Defines the depth-first function for traversing the network*/
int depth_first(int,int);

main()
{

int i,j,k,number_of_nodes;

FILE *f1;

f1=fopen("Fournodenet.txt", "r");
fscanf(f1,"%d\n", &number_of_nodes);
printf("Number of nodes = %d\n", number_of_nodes);

/*Displays each node and its number of links*/
for(i=0; i < number_of_nodes; i++)
{
printf("Node %d name = %c, Number of linked nodes = %d\n", i
}
printf("\n");

/*Displays each nodes links & there respective lengths from each other*/
for(j=0; j < number_of_nodes; j++)
{
nodes[j].visited = 0; /*Gives initial value for seen nodes*/
nodes[j].distance_from_root = DINIT; /*Sets an unreachable target for distance from root*/
fscanf(f1,"%c\n", &nodes[j].name);
printf(" For node %c\n", nodes[j].name);
{
}
printf("\n");

/*Gives each node an integr value*/
{
for(k=0; k < number_of_nodes; k++)
{
{
}
}
}
}
fclose(f1);
printf("\n");

/*Function called*/
depth_first(0,0);
for(k=1; k < number_of_nodes; k++)
if (nodes[k].distance_from_root == DINIT)
else
printf("Node %c has distance from root %d\n",nodes[k].name, nodes[k].distance_from_root);
printf("\n");

return 0;
}

/*The Depth-First algorithm*/
int depth_first(int index, int dist)
{
int i,final_node;

printf("Entering node %d, length = %d\n", index,dist);
nodes[index].visited = 1; /*Flags a node*/
final_node = 1; /*Defines last node in path traversed*/
{
{
printf("Going to node %d, length = %d\n",
/*Calculates each nodes distance from root*/
final_node = 0; /*Recycles node*/
}
}
nodes[index].visited = 0; /*Unflags a seen node*/
if (final_node == 1)
{
printf("End of path\n");
if (dist < nodes[index].distance_from_root)
nodes[index].distance_from_root = dist;
}
printf("Leaving node  %d, length = %d\n", index,dist);
dist = 0;
return(nodes[index].distance_from_root);
}```
Here is are two networks:

Four nodes:

4
A 3
B 2
C 3
D 2
A B 6 C 1 D 4
B A 6 C 2
C A 1 B 2 D 2
D A 4 C 2

Ten nodes:

10
A 4
B 2
C 2
D 2
E 3
F 4
G 2
H 2
I 3
J 2
A B 3 E 1 F 2 G 2
B A 3 E 1
C D 2 H 1
D C 2 J 1
E A 1 B 1 I 4
F A 2 G 1 I 4 J 2
G A 2 F 1
H C 1 I 1
I E 4 F 4 H 1
J D 1 F 2

&#91;code]&#91;/code]tagged by Salem

2. Have you ever played with Z buffers or BSP trees?

3. I am a beginner with c programming so I have no idea what BPS trees or Z buffers are.

4. If you want the shortest path: Use Dijkstra's or Warshall Algorithms.

I am a beginner with c programming so I have no idea what BPS trees or Z buffers are.
Then why are you doing a shortest path problem that involves structs, files and pointers.

This does not sound like beginner stuff to me!

5. Haha, I know it seems bizarre, but my physics lecturers believe that even though we've only had a semester to learn c programming and the guy that taught c couldn't teach Thierry Henry from Arsenal football club how to speak French, we should understand and develop programs using stuctures pointers and the like (I do however have good-ish knowledge of Fortran 90/95)!

Anyway I need to use the Depth-First algorithm in c specifically. Thanks though, I'll certainly try to find those algorithms mentioned, for future use maybe.

Any actual help with correcting the algorithm I have or a better "Depth-First" algorithm for the networks given (maybe a better format for the networks) would be really really appreciated.

6. Cheers Salem, included your first comment, it didnt however change anything, but compiled ok. Your second comment has me slightly stumped, should the depth-first calling function include 'nodes[index].distance_from_root' somehow?

Cheers bro!