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
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
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

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

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

Author Comment

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

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

ID: 1256330
yl,

thanks for your assistance on this.

misbell
0

## Featured Post

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 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
Course of the Month11 days, 12 hours left to enroll

#### 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.