الأحد، 27 ديسمبر 2020

DepthFirstSearchorDFSforaGraph // Home work

// // أضف تعليق

 DepthFirstSearchorDFSforaGraph



 

package depthfirstsearchordfsforagraph;


 // Java program to print DFS traversal from a given given graph 

import java.io.*; 

import java.util.*; 

  

// This class represents a directed graph using adjacency list 

// representation 

public class DepthFirstSearchorDFSforaGraph {


    

  private int V;   // No. of vertices 

  

    // Array  of lists for Adjacency List Representation 

    private LinkedList<Integer> adj[]; 

  

    // Constructor 

    DepthFirstSearchorDFSforaGraph(int v) 

    { 

        V = v; 

        adj = new LinkedList[v]; 

        for (int i=0; i<v; ++i) 

            adj[i] = new LinkedList(); 

    } 

  

    //Function to add an edge into the graph 

    void addEdge(int v, int w) 

    { 

        adj[v].add(w);  // Add w to v's list. 

    } 

  

    // A function used by DFS 

    void DFSUtil(int v,boolean visited[]) 

    { 

        // Mark the current node as visited and print it 

        visited[v] = true; 

        System.out.print(v+" "); 

  

        // Recur for all the vertices adjacent to this vertex 

        Iterator<Integer> i = adj[v].listIterator(); 

        while (i.hasNext()) 

        { 

            int n = i.next(); 

            if (!visited[n]) 

                DFSUtil(n, visited); 

        } 

    } 

  

    // The function to do DFS traversal. It uses recursive DFSUtil() 

    void DFS(int v) 

    { 

        // Mark all the vertices as not visited(set as 

        // false by default in java) 

        boolean visited[] = new boolean[V]; 

  

        // Call the recursive helper function to print DFS traversal 

        DFSUtil(v, visited); 

    } 

  

    public static void main(String args[]) 

    { 

        DepthFirstSearchorDFSforaGraph g = new DepthFirstSearchorDFSforaGraph(8); 

  

        g.addEdge(0, 1); 

        g.addEdge(1, 0); 

        g.addEdge(0, 4); 

        g.addEdge(1, 6); 

        g.addEdge(5, 1); 

        g.addEdge(2, 5); 

         g.addEdge(6, 2);

          g.addEdge(4, 2);

           g.addEdge(5, 3);

            g.addEdge(6, 4);

             g.addEdge(4,6);

              g.addEdge(5, 7);

               

                

  

        System.out.println("Following is Depth First Traversal "+ 

                           "(starting from vertex 5)"); 

  

        g.DFS(5); 

    } 

// This code is contributed by Aakash Hasija 


Download here

https://drive.google.com/file/d/1BxZ87bGyWDANY7ZokyYSsw1ZVDz4Yrm9/view?usp=sharing

0 التعليقات:

إرسال تعليق

ملحوظة: يمكن لأعضاء المدونة فقط إرسال تعليق.

تسجيل الدخول
الدخول
تسجيل الدخول