Solved

Incedence matrix

Posted on 1997-11-14
5
501 Views
Last Modified: 2011-10-03
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[])
0
Comment
Question by:misbell
  • 3
  • 2
5 Comments
 
LVL 1

Accepted Solution

by:
yl earned 200 total points
ID: 1256326
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
 
LVL 1

Expert Comment

by:yl
ID: 1256327
Correction: !incedence[i, j] should be incedence[i, j].
0
 

Author Comment

by:misbell
ID: 1256328
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
 
LVL 1

Expert Comment

by:yl
ID: 1256329
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
 

Author Comment

by:misbell
ID: 1256330
yl,

thanks for your assistance on this.

misbell
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

910 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now