Scribd Logo
Upload

Welcome to Scribd!

  • 6 views

    Espadero, Graphs

    Uploaded by

    Andrei Espadero
    The document discusses graph theory applications in Facebook and Google Maps. It compares BFS and DFS graph traversal algorithms and provides an example Java implementation of a graph data structure and traversal.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Espadero, Graphs

    Uploaded by

    Andrei Espadero
    6 views3 pages
    The document discusses graph theory applications in Facebook and Google Maps. It compares BFS and DFS graph traversal algorithms and provides an example Java implementation of a graph data structure and traversal.

    Original Title

    ESPADERO, GRAPHS

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses graph theory applications in Facebook and Google Maps. It compares BFS and DFS graph traversal algorithms and provides an example Java implementation of a graph data structure and traversal.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    6 views3 pages

    Espadero, Graphs

    Uploaded by

    Andrei Espadero
    The document discusses graph theory applications in Facebook and Google Maps. It compares BFS and DFS graph traversal algorithms and provides an example Java implementation of a graph data structure and traversal.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 3

    ESPADERO, MAR ANDREI D.

    BSIT-NET2A

    Intended Learning Activities


    Cite real applications of Graphs and discuss.
    1. Facebook: Each user is represented by a vertex, and when two vertices have an edge, they are friends.
    Graph theory is also used in buddy recommendation.
    2. Google Maps: To discover the shortest path between two nodes, it represents various locations as
    vertices and roads as edges.

    Assessment
    Compare and contrast BFS vs DFS through 3 examples of traversals
    1. For determining the shortest path, BFS (Breadth First Search) employs a Queue data structure. The
    Stack data structure is used by DFS (Depth First Search).
    2. BFS is better at finding vertices that are close to the specified source. When there are solutions that are
    not available at the source, DFS is a better option.
    3. When a dead end occurs in any iteration, the Breadth First Search (BFS) method traverses a graph in a
    breadth ward motion and uses a queue to remember to retrieve the next vertex to start a search. When a
    dead end occurs in any iteration, the Breadth First Search (BFS) method traverses a graph in a breadth
    ward motion and uses a queue to remember to retrieve the next vertex to start a search.
    Assignment
    Implement a Graph Data Structure Traversal using Java Program
    import java.util.*;

    class Edge {
    int src, dest, weight;
    Edge(int src, int dest, int weight) {
    this.src = src;
    this.dest = dest;
    this.weight = weight;
    }
    }
    class Graph {

    static class Node {


    int value, weight;
    Node(int value, int weight) {
    this.value = value;
    this.weight = weight;
    }
    };

    List<List<Node>> adj_list = new ArrayList<>();

    public Graph(List<Edge> edges)


    {

    for (int i = 0; i < edges.size(); i++)


    adj_list.add(i, new ArrayList<>());

    for (Edge e : edges)


    {

    adj_list.get(e.src).add(new Node(e.dest, e.weight));


    }
    }
    public static void printGraph(Graph graph) {
    int src_vertex = 0;
    int list_size = graph.adj_list.size();

    System.out.println("The contents of the graph:");


    while (src_vertex < list_size) {
    for (Node edge : graph.adj_list.get(src_vertex)) {
    System.out.print("Vertex:" + src_vertex + " ==> " + edge.value +
    " (" + edge.weight + ")\t");
    }

    System.out.println();
    src_vertex++;
    }
    }
    }
    class Main{
    public static void main (String[] args) {

    List<Edge> edges = Arrays.asList(new Edge(0, 1, 2),new Edge(0,2,4),


    new Edge(1, 2, 4),new Edge(2, 0, 5), new Edge(2, 1, 4),
    new Edge(3, 2, 3), new Edge(4, 5, 1),new Edge(5, 4,3));

    Graph graph = new Graph(edges);

    Graph.printGraph(graph);
    }
    }
    Output:
    The contents of the graph:
    Vertex:0 ==> 1 (2) Vertex:0 ==> 2 (4)
    Vertex:1 ==> 2 (4)
    Vertex:2 ==> 0 (5) Vertex:2 ==> 1 (4)
    Vertex:3 ==> 2 (3)
    Vertex:4 ==> 5 (1)
    Vertex:5 ==> 4 (3)

    You might also like