CODEWITHSUNDEEP
algorithmdata-structuresdepth-first-search
Sahil
Sahil

Reputation: 9478

Depth First Search Using Adjacency Matrix

Can anyone explain the algorithm for depth first search using Adjacency matrix? I know the algo of depth first search using recursion and I tried to implement it using Adjacency matrix but it was not very successful.

What I have so far is

 dfs(G,i){

  mark i as visited;

  for(traverse through the edges of i vertex){

     if(vertex of edge is unseen){

       DFS(G,newVerted)
     }
   }

}

Upvotes: 3

Views: 36458

Answers (4)

user3960974
user3960974

Reputation: 

    void DFS(int i)
    {
        int j;
        printf("\n%d",i);
        visited[i]=1;
        for(j=0;j<n;j++)
            if(!visited[j]&&G[i][j]==1)
                DFS(j);
    }

Where n is the no of vertices and G is the graph and G[i][j] indicates vertex i is connected to vertex j

Upvotes: 7

Varun Teja
Varun Teja

Reputation: 523

You missed to print in function dfs(G,i)

The code is as follows

dfs(G,i){
int j;
printf("%d ",i);
visited[i]=1;
for(j=0;j<n;j++){
    if(visited[j]==0&&G[i][j]==1)
        dfs(G,j);
}

Here we use variable n as number of vertices in Graph.G is cost adjacency matrix.

Upvotes: 4

olagjo
olagjo

Reputation: 2155

I guess you could do it by maintaining a stack and a visited-list, and using a while-loop: Visited is a bool[], initialized to hold false at all positions, and I assume that the call G[node,neighbour] somehow returns a boolean, telling if there is an edge from node to neighbour. (Implicit comparison to 1 or simply make the adjacency matrix hold booleans)
Stack holds the indices of your nodes:

dfs(G,i){
    Initialize Stack
    Current = i
    PossibleEdge = 0
    Visited[Current] = true  //You have visited the starting node
    Do {
        While (PossibleEdge < count) {
            if (G[Current,PossibleEdge] && NOT Visited[PossibleEdge]){
                Stack.Push(Current)      //Save state
                Current = PossibleEdge   //Continue with the child node
                Visited[Current] = true 
                PossibleEdge = -1        //So that it will be incremented to 0
            }
            PossibleEdge++
        }
        PossibleEdge = Current           //Continue to next row of "parent node"
        Current = Stack.Pop()            //Get parent node back
    } While (Stack contains nodes)
}

I'm sure it could be optimized (and seeing that I'm dead tired, there might be some logical errors), but if the basic procedure makes sense, it's a start!
EDIT: Clarifying, and adding this tip: Recursion is probably easier ;)

Upvotes: 0

Luka Rahne
Luka Rahne

Reputation: 10447

I think it is simplest that just like in labyrinth you always go left. If you come from n node go on next node in cycle in increasing order.

I just do not know how do you know that you came around :D But cool thing is that you do not need extra space and marking.

EDIT
example 

    5
   / \
  7   3
 /\   /\
4  1 6  2

Am is then

......1
..1....
.1..11.
1.....1
..1...1
..1....
1..11..

So ordering start from 5 is 3 6 3 2 3 5 7 1 7 4 7 5 3# and because you went from 5->3

As I said if you are on node you go on next node based on node you came from. Next node you are going to visit is next number from prevous node (not current node you go from).

Upvotes: 0

Related Questions