Problem using DFS with a DAG graph

This is a discussion on Problem using DFS with a DAG graph within the C Programming forums, part of the General Programming Boards category; Hey there! I'm using DFS to search how many paths do I have from vertex1 to vertex2 in a DAG ...

  1. #1
    anguished incognito54's Avatar
    Join Date
    Apr 2004
    Posts
    24

    Problem using DFS with a DAG graph

    Hey there!
    I'm using DFS to search how many paths do I have from vertex1 to vertex2 in a DAG graph... But I have a problem that I search the vertexes a "infinity" of times... I went here and I didn't quite understood the language or the ideas... Like "If vertex w is unexplained then"...

    So here's my code
    Code:
    typedef struct node { 
    	int v;
    	struct node *next;
    } Node;
    
    typedef Node *ADJ;
    
    int n_paths(int vertex1, int vertex2) {
    	int n = 0;
    	ADJ temp;
    	temp = graph[vertex1];
    	if(vertex1 == vertex2)
    		return 1;
    	while(temp != NULL) {
    		n = n + n_paths(temp->v, vertex2);
    		temp = temp->next;
    	}
    	return n;
    }
    I ommited a big part of the code because I think this is the most important part... Any ideas how to optimize?
    Thnx!
    I've never felt the nausea of longing to feel nothing,
    I never wanted to cease to exist, just disappear...

  2. #2
    Registered User
    Join Date
    Oct 2001
    Posts
    62
    Hello, incognito54.

    I think you need to save the node indices you already visited to avoid an endless backtracking.

  3. #3
    anguished incognito54's Avatar
    Join Date
    Apr 2004
    Posts
    24
    i don't because a DAG is an acyclic graph...
    I've never felt the nausea of longing to feel nothing,
    I never wanted to cease to exist, just disappear...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 09:38 AM
  2. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 03:51 PM
  3. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 07:54 PM
  4. Help w/ graph as adjacency matrix
    By ac251404 in forum C++ Programming
    Replies: 4
    Last Post: 05-09-2006, 11:25 PM
  5. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM

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