2)
Consider a directed acyclic graph
(dag) with ‘e’ arcs
and with two distinguished vertices
‘s’ to ‘t’.
By maximal, we mean no additional
path may be added, but it doesnot
mean that it is the largest size
such set.
SOLUTION :
In this problem one should look
for all those nodes which have
path from the starting vertex
and from the ending vertex. This
can be done by the adjacency matrix.
The following steps give brief
explanation of the acyclic graph
stating with its diagram :
Step 1 Make and Adjacency matrix.
Step 2 Look for all those vertices
which node have a path from the
starting node S.
Step 3 Now look for the same
thing for the node T.
Step 4 Check for the repetitions
if any.
The start node is S and end node
is T.
In the following diagram all
the nodes are connected to the
S but all other nodes except the
1st S is not connected to the
final node T.
ALGORITHM – O(e) To find
a maximal set of vertex disjoint
paths from ‘S’ to
‘T’
Steps
Make a adjacency matrix.
Count number of arcs or edges
connected to any vertex.
Traverse the list if the no. of
edges in any particular node is
zero.
Count that node, the final outcome
will contains all the nodes that
are disjoint.
To explain the above steps, the
following examples clarifies the
O(e) algorithm :
Suppose that the number of nodes
in the graph is constant :
i.e. arcs may be added or deleted
but nodes may not.
# define MAXNODES 50
Struct node{
/* information associated with
each node */
};
Struct arc{
Int adj; /* information associated
with each arc */
};
Struct graph{
Struct node nodes[MAXNODES];
Struct arc arcs[MAXNODES] [MAXNODES];
};
Struct graph g;
Int adj [MAXNODES] [MAXNODES];
Void Join (int adj [ ] [MAXNODES],
int node1, int node2)
{
adj [node1] [node2] = TRUE;
} /* end join */
int adjacent (int adj [ ] [MAXNODES],
int node1, int node2)
{
return ((adj[node1] [node2]==TRUE)?TRUE:FALSE);
} /* end adjacent */
Each node of the graph is represented
by an integer between O and MAXNODES-1
and the array field nodes represents
the appropriate information assigned
to each node. The array field
arcs is a two dimensional array
representing every possible ordered
pair of nodes. |
