finding parents of specific node in DAG

Hello everyone,
I have to write a function to find parent nodes of the given node?
my graph structure is look like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Graph
{
    int V;    // No. of vertices in graph
    list<int> *adj; // Pointer to an array containing adjacency lists
 
public:
    Graph(int V);   // Constructor
    void addEdge(int u, int v);
    void parent_nodes(int Node);
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
 
void Graph::addEdge(int u, int v)
{
    adj[u].push_back(v); // Add v to u’s list.
}
 
void Graph::parent_nodes(int Node)
{
    int n = 0;
    for (n; n < Node; n++) 
    {
     list <int>::iterator iter;
     for (iter = adj[n].begin(); iter != adj[n].end(); ++iter)
	if (*iter == Node)
	     cout << n << " ";
		}
}

int main()
{
Graph g(5);
		g.addEdge(0, 5);
		g.addEdge(1, 5);
		g.addEdge(2, 5);
		g.addEdge(3, 5);
		g.addEdge(0, 1);
		g.addEdge(2, 3);

		g.parent_nodes(5);
}



i have written the parent_nodes function so far but obviously it's not efficient for larger Graphs
is there any other way to do this?

i'm new to Graphs...so

any suggestions will be appreciated...
Last edited on
> for (n; n < Node; n++)
¿why do you stop at `Node' instead of traverse all the vertices?

> is there any other way to do this?
keep track of your parents
may also use an incidence matrix instead of adjacency list
why do you stop at `Node' instead of traverse all the vertices?

because all my graph nodes are sorted in Ascending order...but your right for generality
i should visit all vertices...

keep track of your parents

could you please tell me how i do this?
1
2
3
4
5
6
7
8
9
10
11
12
13
class node{
   vector<int> children;
   vector<int> parent;
};

class graph{
   vector<node> vertex;
};

void graph::addEdge(int u, int v){
   vertex[u].children.push_back(v);
   vertex[v].parent.push_back(u);
}
Last edited on
Topic archived. No new replies allowed.