Implementação-Grafo

//MAIN
package proj;
import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Graph g = new Graph(5);
		g.addEdge(g, 1, 2);
		g.addEdge(g, 2, 3);
		g.addEdge(g, 3, 4);
		g.printGraph(g);
		g.DFS(4);
	}

}


//graph
package proj;
import java.io.*;
import java.util.*;

public class Graph {
	public int V;
	public LinkedList<Integer> adj[]; //array de lista

	Graph(int v){ //TAMANHO do grafo(matriz)
		this.V = v;
	    adj = new LinkedList[v]; //cria a lista de adjacencia

	    for (int i=0; i<v; ++i) {
	    	adj[i] = new LinkedList<>(); //cria uma lista encadeada em cada index do array
	    }
	}

	void addEdge(Graph graph, int v, int w) { //adiciona uma aresta entre os dois vertices v e w
		graph.adj[v].add(w);
		graph.adj[w].add(v);
	}

	static void printGraph(Graph graph) {
        for(int v = 0; v < graph.V; v++) {
            System.out.println("Adjacency list of vertex "+ v);
            System.out.print("head");
            for(Integer pCrawl: graph.adj[v]){
                System.out.print(" -> "+pCrawl);
            }
            System.out.println("\n");
        }
    }

	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);
    }

}