FilesExpand file tree

master

/

Depth_First_Search.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

59 lines (49 loc) · 1.48 KB

master

/

Depth_First_Search.java

Copy path

Top

File metadata and controls

• Code
• Blame

59 lines (49 loc) · 1.48 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

package com.dsj.graphs;

import java.util.Stack;

public class Depth_First_Search {

Graph_Creation_Adj_List graph_to_be_searched;

boolean[] visitedNodeTrackerArr;

Stack<Integer> stack;

public Depth_First_Search(Graph_Creation_Adj_List graph_to_be_searched) {

this.graph_to_be_searched = graph_to_be_searched;

dfs();

System.out.println("DFS completed..");

}

private void dfs() {

stack = new Stack<Integer>();

int totalNodes = graph_to_be_searched.numberOfVertices;

visitedNodeTrackerArr = new boolean[totalNodes];

System.out.println("Begining DFS.....");

updateNodeStatus(0);

if (!stack.isEmpty()) {

traverse(stack.peek());

}

}

void updateNodeStatus(int index) {

System.out.println(graph_to_be_searched.arrIndexToVertexMap.get(index));

visitedNodeTrackerArr[index] = true;

insertLinkedNodes(index);

}

private void traverse(Integer index) {

if (isVisited(index) || stack.isEmpty()) {

return;

}

int temp = stack.pop();

updateNodeStatus(temp);

if (!stack.isEmpty()) {

traverse(stack.peek());

}

}

private void insertLinkedNodes(int temp) {

graph_to_be_searched.adjList[temp].forEach(connectedNode -> {

int indexForVal = graph_to_be_searched.getIndexForThis(connectedNode.getVertexId());

if (!isVisited(indexForVal)) {

if (!stack.contains(indexForVal))

stack.push(indexForVal);

}

});

}

private boolean isVisited(int index) {

return visitedNodeTrackerArr[index];

}

}