Scribd
Upload
8 views2 pages

Java DFS Graph Implementation

This document contains the code for a Depth First Search (DFS) graph class in Java. The class contains methods for initializing a graph with a given number of nodes, adding edges between nodes, and performing a DFS exploration of the graph starting from a given start node. The DFS exploration method uses a stack and boolean visited array to recursively traverse the graph depth-first.

Uploaded by

sara amer
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views2 pages

Java DFS Graph Implementation

This document contains the code for a Depth First Search (DFS) graph class in Java. The class contains methods for initializing a graph with a given number of nodes, adding edges between nodes, and performing a DFS exploration of the graph starting from a given start node. The DFS exploration method uses a stack and boolean visited array to recursively traverse the graph depth-first.

Uploaded by

sara amer
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

DFSGraph.

java

1 import [Link];
2
3 public class DFSGraph {
4
5 // number of node
6 int size;
7 // list of type adj_list has head of type Node
8 adjlist[] array;
9
10
11 public DFSGraph(int size) {
12 [Link]=size;
13 array=new adjlist [[Link]];
14
15 // initialize to array
16 for (int i = 0; i < size ; i++)
17 {
18 array[i]=new adjlist();
19 array[i].head=null;
20
21 }// end for
22
23 }//constructor
24
25
26
27
28 // Method to add new node take src which determine reference node, dest which determine
value in node
29 public void addnode(int src, int dest)
30 {
31 Node n =new Node(dest,null);
32 [Link]=array[src].head;
33 array[src].head=n;
34
35 }// end method addnode
36
37
38 // Method to explorer all node in tree take startvertex to determine first step
39
40 public void DFSExplore (int startvertex)
41 {
42
43 // array determine node visited or no
44 Boolean [] visited =new Boolean [size];
45 //initialize to array
46 for (int i=0;i<size;i++)
47 visited[i]=false;
48
49 //initialize stack
50 Stack<Integer> s=new Stack<Integer>();
51 [Link](startvertex);
52
53 // while stack isn't empty continuous
54 while (![Link]()){
55
56 // last item in stack
57 int n =[Link]();
58 //retrieval in its position because has still children
59 [Link](n);
60 // it is visited
61 visited[n]=true;

Page 1
[Link]

62 // take first node


63 Node head =array[n].head;
64 // visited all children is true
65 Boolean isDone=true;
66
67 // while still children continuous
68 while(head!=null){
69
70 if (visited[[Link]]==false){
71 [Link]([Link]);
72 visited[[Link]]=true;
73 isDone=false;
74 break;
75 }
76 else
77 head=[Link];
78 }// end while
79
80 // back track
81 if(isDone==true){
82 int outN=[Link]();
83 [Link]("Visite node : "+ outN);
84 }//end if
85
86 }// end while
87
88
89
90
91 }// end method DFSExplore
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112 }// end class
113

Page 2

You might also like