Help with the Depth-First algorithm

This is a discussion on Help with the Depth-First algorithm within the C Programming forums, part of the General Programming Boards category; Hello just wondering if anyone can see where I need to go from here to get the shortest path from ...

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    4

    Question 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;
      char linked_node[30];
      int length[30];
      int linked_node_id[30];
      int visited;
      int number_of_links;
      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++)
      {
        fscanf(f1,"%c %d\n", &nodes[i].name, &nodes[i].number_of_links);
        printf("Node %d name = %c, Number of linked nodes = %d\n", i
                                    , nodes[i].name,  nodes[i].number_of_links);
      }
      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);
        for(i=0; i < nodes[j].number_of_links; i++)
        {
          fscanf(f1,"%c %d\n", &nodes[j].linked_node[i], &nodes[j].length[i]);
          printf(" Linked node: %c with length %d\n", nodes[j].linked_node[i], nodes[j].length[i]);
        }
        printf("\n");
    
    /*Gives each node an integr value*/    
        for(i=0; i < nodes[j].number_of_links; i++)
        { 
          for(k=0; k < number_of_nodes; k++)
          {
            if(nodes[j].linked_node[i] ==  nodes[k].name)
            { 
              nodes[j].linked_node_id[i] = 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)
          printf("Node %c has a distance not found\n",nodes[k].name);
        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*/
       for(i=0; i < nodes[index].number_of_links; i++)
       {
         if (nodes[nodes[index].linked_node_id[i]].visited == 0)
         {  
           printf("Going to node %d, length = %d\n", 
                   nodes[index].linked_node_id[i], dist + nodes[index].length[i]);
           /*Calculates each nodes distance from root*/
           depth_first(nodes[index].linked_node_id[i], dist + nodes[index].length[i]);
           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
    Attached Files Attached Files
    Last edited by Pyrokenesis; 10-28-2002 at 07:59 AM.

  2. #2
    Visionary Philosopher Sayeh's Avatar
    Join Date
    Aug 2002
    Posts
    212
    Have you ever played with Z buffers or BSP trees?
    It is not the spoon that bends, it is you who bends around the spoon.

  3. #3
    Registered User
    Join Date
    Oct 2002
    Posts
    4
    I am a beginner with c programming so I have no idea what BPS trees or Z buffers are.

  4. #4
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511

    Wink

    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!
    Mr. C: Author and Instructor

  5. #5
    Registered User
    Join Date
    Oct 2002
    Posts
    4
    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. #6
    Registered User
    Join Date
    Oct 2002
    Posts
    4
    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!
    Last edited by Pyrokenesis; 10-28-2002 at 06:00 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need some help...
    By darkconvoy in forum C Programming
    Replies: 11
    Last Post: 05-09-2009, 02:34 AM
  2. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 01:30 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21