Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Incedence matrix

Posted on 1997-11-14
5
Medium Priority
?
514 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
5 Comments
 
LVL 1

Accepted Solution

by:
yl earned 800 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

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

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…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
Suggested Courses

636 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