• C

Incedence matrix

using an incedence matrix to represent a graph, and using the Depth First Search algorithm, how does one code
the Depth First Search function to do this.

pseudo code for DFS function:

DFS(int i, processed[1 to n])
   processed[i] = 1;
   for each vertex W adjacent to V do
    if(!processed[w])
       then DFS(W, processed[])
misbellAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

ylCommented:
Assuming that processed and incedence are defined as:
 int processed[N];
 int incedence[N][N];

The DFS function will be something like:

DFS(int i, int processed[N], int incedence[N][N])
{
  int j;

  processed[i] = 1;

  for (j = 1; j <= N; j++)
      if (j != i        &&
          !processed[j] &&
          !incedence[i, j])
         DFS(j, processed, incedence);
}
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
ylCommented:
Correction: !incedence[i, j] should be incedence[i, j].
0
misbellAuthor Commented:
y1,
  is your definition of an incedence matrix the following?
each row represents a vertex and each column represents
an edge. Where i = vertex and j = edge? Did you code the
problem according to the definition above? It appears your
code is for an adjacency matrix where both i and j = vertex.

For example: both of the following represents the same
graph, but one is an adjacency matrix and the other
is an incedence matrix.

Incedence matrix:
10000000010
00100001000
01010001100
00000000000
00000100001
10000110000
00111000000
00000000010
01000000000
00000000100
00001000000
00000010001

Adjacency matrix:
000001010000
001000100000
010000101100
000000000000
000001000001
100010000001
011000000010
100000000000
001000000000
001000000000
000000100000
000011000000

Thanks,
misbell
0
ylCommented:
misbell,

The code I wrote was using an adjacency matrix. Here is the modified code to handle you incedence matrix.

int incedence[N][M];

DFS(int i, int processed[N], int incedence[N][M])
{
 int j, k;

 processed[i] = 1;

 for (j = 1; j <= M; j++)
     if (incedence[i, j])
        for (k = 1; k <= N; k++)
            if (k != i && !processed[k] && incedence[k, j])
               DFS(k, processed, incedence);
}
0
misbellAuthor Commented:
yl,

thanks for your assistance on this.

misbell
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.