Graphs – Depth First Search
<p class="p2">/*Copyrights to vsdevelopers.io*/</p>
<p class="p2">/*For more programs visit vsdevelopers.io */</p>
<p class="p2">/*Java program to perform DFS on a graph*/</p>
<p class="p2">/*The graph is represented using adjacency list*/</p>
<p class="p3"><span class="s1">import</span> java<span class="s2">.</span>util<span class="s2">.*;</span></p>
<p class="p4">public class <span class="s4">VSDGraphDfs</span> <span class="s5">{</span></p>
<p class="p4">publicstaticclass<span class="s6">VSDGraph</span> <span class="s5">{</span></p>
<p class="p4">int<span class="s7">v</span><span class="s2">;</span></p>
<p class="p5"><span class="s8">LinkedList</span> <span class="s7">adList</span><span class="s5">[]</span><span class="s2">;</span></p>
<p class="p6">VSDGraph<span class="s5">(</span><span class="s1">int</span> <span class="s9">size</span><span class="s5">)</span> <span class="s5">{</span></p>
<p class="p2"><span class="s7">v</span> <span class="s2">=</span> <span class="s9">size</span><span class="s2">;</span>// No.of vertices</p>
<p class="p2"><span class="s7">adList</span> <span class="s2">=</span> <span class="s1">new</span> <span class="s6">LinkedList</span><span class="s5">[</span><span class="s7">v</span><span class="s5">]</span><span class="s2">;</span>// Adjacency list to mark the edges</p>
<p class="p2">// Initializing vertices using constructor</p>
<p class="p3"><span class="s1">for</span> <span class="s5">(</span><span class="s1">int</span> <span class="s10">i</span> <span class="s2">=</span> <span class="s11">0</span><span class="s2">;</span> <span class="s12">i</span> <span class="s2"><</span> <span class="s7">v</span><span class="s2">;</span> <span class="s12">i</span><span class="s2">++</span><span class="s5">)</span></p>
<p class="p7"><span class="s7">adList</span><span class="s5">[</span><span class="s12">i</span><span class="s5">]</span> <span class="s2">=</span> <span class="s1">new</span> <span class="s8">LinkedList</span><span class="s5">()</span><span class="s2">;</span></p>
<p class="p3"><span class="s5">}</span></p>
<p class="p2">// Function to add edge to the graph</p>
<p class="p6"><span class="s1">void</span> VSDaddEdge<span class="s5">(</span><span class="s1">int</span> <span class="s9">v1</span><span class="s2">,</span> <span class="s1">int</span> <span class="s9">v2</span><span class="s5">)</span> <span class="s5">{</span></p>
<p class="p8"><span class="s8">adList</span><span class="s13">[</span><span class="s14">v1</span><span class="s13">]</span><span class="s15">.</span><span class="s16">add</span><span class="s13">(</span><span class="s14">v2</span><span class="s13">)</span><span class="s2">;</span></p>
<p class="p3"><span class="s5">}</span></p>
<p class="p2">// Function to perform DFS, taking initial vertex as parameter</p>
<p class="p6"><span class="s1">void</span> VSD_Dfs<span class="s5">(</span><span class="s1">int</span> <span class="s9">s</span><span class="s5">)</span> <span class="s5">{</span></p>
<p class="p9"><span class="s6">System</span><span class="s2">.</span><span class="s17"><b><i>out</i></b></span><span class="s2">.</span><span class="s18">println</span><span class="s5">(</span>"The DFS of given graph is:"<span class="s5">)</span><span class="s2">;</span></p>
<p class="p2"><span class="s1">boolean</span> <span class="s10">visited</span><span class="s5">[]</span> <span class="s2">=</span> <span class="s1">new</span> <span class="s1">boolean</span><span class="s5">[</span><span class="s7">v</span><span class="s5">]</span><span class="s2">;</span>// Array to mark visited vertices</p>
<p class="p2"><span class="s4">LinkedList</span> <span class="s10">stack</span> <span class="s2">=</span> <span class="s1">new</span> <span class="s16">LinkedList</span><span class="s5">()</span><span class="s2">;</span>// Queue to traverse over vertices depth wise</p>
<p class="p10">visited<span class="s5">[</span><span class="s9">s</span><span class="s5">]</span> <span class="s2">=</span> <span class="s1">true</span><span class="s2">;</span></p>
<p class="p10"><span class="s8">stack</span><span class="s15">.</span><span class="s16">push</span><span class="s13">(</span><span class="s14">s</span><span class="s13">)</span><span class="s2">;</span></p>
<p class="p3"><span class="s1">while</span> <span class="s5">(</span><span class="s12">stack</span><span class="s2">.</span><span class="s18">size</span><span class="s5">()</span> <span class="s2">!=</span> <span class="s11">0</span><span class="s5">)</span> <span class="s5">{</span></p>
<p class="p3"><span class="s9">s</span> <span class="s2">=</span> <span class="s5">(</span><span class="s1">int</span><span class="s5">)</span> <span class="s12">stack</span><span class="s2">.</span><span class="s18">pop</span><span class="s5">()</span><span class="s2">;</span></p>
<p class="p7"><span class="s6">System</span><span class="s2">.</span><span class="s17"><b><i>out</i></b></span><span class="s2">.</span>println<span class="s5">(</span><span class="s9">s</span><span class="s5">)</span><span class="s2">;</span></p>
<p class="p11"><span class="s8">Iterator</span> <span class="s10">i</span> <span class="s2">=</span> <span class="s7">adList</span><span class="s5">[</span><span class="s9">s</span><span class="s5">]</span><span class="s2">.</span><span class="s18">iterator</span><span class="s5">()</span><span class="s2">;</span></p>
<p class="p12"><span class="s1">while</span> <span class="s5">(</span><span class="s12">i</span><span class="s2">.</span>hasNext<span class="s5">())</span> <span class="s5">{</span></p>
<p class="p3"><span class="s1">int</span> <span class="s10">temp</span> <span class="s2">=</span> <span class="s5">(</span><span class="s1">int</span><span class="s5">)</span> <span class="s12">i</span><span class="s2">.</span><span class="s19">next</span><span class="s5">()</span><span class="s2">;</span></p>
<p class="p10"><span class="s1">if</span> <span class="s5">(</span>visited<span class="s5">[</span>temp<span class="s5">]</span> <span class="s2">!=</span> <span class="s1">true</span><span class="s5">)</span> <span class="s5">{</span></p>
<p class="p10">visited<span class="s5">[</span>temp<span class="s5">]</span> <span class="s2">=</span> <span class="s1">true</span><span class="s2">;</span></p>
<p class="p10"><span class="s8">stack</span><span class="s15">.</span><span class="s16">push</span><span class="s13">(</span><span class="s8">temp</span><span class="s13">)</span><span class="s2">;</span></p>
<p class="p3"><span class="s5">}</span></p>
<p class="p3"><span class="s5">}</span></p>
<p class="p3"><span class="s5">}</span></p>
<p class="p3"><span class="s5">}</span></p>
<p class="p3"><span class="s5">}</span></p>
<p class="p4">publicstaticvoid<span class="s20">main</span><span class="s5">(</span><span class="s6">String</span> <span class="s9">args</span><span class="s5">[])</span> <span class="s5">{</span></p>
<p class="p5">VSDGraph<span class="s10">g</span> <span class="s2">=</span> <span class="s1">new</span> <span class="s18">VSDGraph</span><span class="s5">(</span><span class="s11">15</span><span class="s5">)</span><span class="s2">;</span></p>
<p class="p7"><span class="s12">g</span><span class="s2">.</span>VSDaddEdge<span class="s5">(</span><span class="s11">0</span><span class="s2">,</span> <span class="s11">1</span><span class="s5">)</span><span class="s2">;</span></p>
<p class="p7"><span class="s12">g</span><span class="s2">.</span>VSDaddEdge<span class="s5">(</span><span class="s11">0</span><span class="s2">,</span> <span class="s11">2</span><span class="s5">)</span><span class="s2">;</span></p>
<p class="p7"><span class="s12">g</span><span class="s2">.</span>VSDaddEdge<span class="s5">(</span><span class="s11">1</span><span class="s2">,</span> <span class="s11">3</span><span class="s5">)</span><span class="s2">;</span></p>
<p class="p7"><span class="s12">g</span><span class="s2">.</span>VSDaddEdge<span class="s5">(</span><span class="s11">1</span><span class="s2">,</span> <span class="s11">4</span><span class="s5">)</span><span class="s2">;</span></p>
<p class="p7"><span class="s12">g</span><span class="s2">.</span>VSDaddEdge<span class="s5">(</span><span class="s11">2</span><span class="s2">,</span> <span class="s11">5</span><span class="s5">)</span><span class="s2">;</span></p>
<p class="p7"><span class="s12">g</span><span class="s2">.</span>VSDaddEdge<span class="s5">(</span><span class="s11">2</span><span class="s2">,</span> <span class="s11">6</span><span class="s5">)</span><span class="s2">;</span></p>
<p class="p7"><span class="s12">g</span><span class="s2">.</span>VSDaddEdge<span class="s5">(</span><span class="s11">3</span><span class="s2">,</span> <span class="s11">7</span><span class="s5">)</span><span class="s2">;</span></p>
<p class="p7"><span class="s12">g</span><span class="s2">.</span>VSDaddEdge<span class="s5">(</span><span class="s11">3</span><span class="s2">,</span> <span class="s11">8</span><span class="s5">)</span><span class="s2">;</span></p>
<p class="p7"><span class="s12">g</span><span class="s2">.</span>VSDaddEdge<span class="s5">(</span><span class="s11">4</span><span class="s2">,</span> <span class="s11">9</span><span class="s5">)</span><span class="s2">;</span></p>
<p class="p7"><span class="s12">g</span><span class="s2">.</span>VSDaddEdge<span class="s5">(</span><span class="s11">4</span><span class="s2">,</span> <span class="s11">10</span><span class="s5">)</span><span class="s2">;</span></p>
<p class="p7"><span class="s12">g</span><span class="s2">.</span>VSDaddEdge<span class="s5">(</span><span class="s11">5</span><span class="s2">,</span> <span class="s11">11</span><span class="s5">)</span><span class="s2">;</span></p>
<p class="p7"><span class="s12">g</span><span class="s2">.</span>VSDaddEdge<span class="s5">(</span><span class="s11">5</span><span class="s2">,</span> <span class="s11">12</span><span class="s5">)</span><span class="s2">;</span></p>
<p class="p7"><span class="s12">g</span><span class="s2">.</span>VSDaddEdge<span class="s5">(</span><span class="s11">6</span><span class="s2">,</span> <span class="s11">13</span><span class="s5">)</span><span class="s2">;</span></p>
<p class="p7"><span class="s12">g</span><span class="s2">.</span>VSDaddEdge<span class="s5">(</span><span class="s11">6</span><span class="s2">,</span> <span class="s11">14</span><span class="s5">)</span><span class="s2">;</span></p>
<p class="p7"><span class="s12">g</span><span class="s2">.</span>VSD_Dfs<span class="s5">(</span><span class="s11">0</span><span class="s5">)</span><span class="s2">;</span></p>
<p class="p3"><span class="s5">}</span></p>
<p class="p13">}</p>
