asked on

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[])

ASKER CERTIFIED SOLUTION

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

Correction: !incedence[i, j] should be incedence[i, j].

misbell

ASKER

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

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);
}

misbell

ASKER

yl,

thanks for your assistance on this.

misbell