Scribd Logo
Upload

Welcome to Scribd!

  • 27 views

    Data Structures and Algorithm: Graphs

    Uploaded by

    Aman Baze
    This document discusses graphs and graph algorithms. It defines what graphs are, including vertices and edges. It covers different types of graphs like social networks and road networks. It also discusses common graph problems like finding paths and shortest paths. It explains how graphs can be represented and stored in memory using adjacency matrices and lists. It then covers graph search algorithms like depth-first search and breadth-first search. Finally, it discusses algorithms for finding shortest paths in weighted graphs, using Dijkstra's algorithm as an example.

    Copyright:

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

    Data Structures and Algorithm: Graphs

    Uploaded by

    Aman Baze
    27 views28 pages
    This document discusses graphs and graph algorithms. It defines what graphs are, including vertices and edges. It covers different types of graphs like social networks and road networks. It also discusses common graph problems like finding paths and shortest paths. It explains how graphs can be represented and stored in memory using adjacency matrices and lists. It then covers graph search algorithms like depth-first search and breadth-first search. Finally, it discusses algorithms for finding shortest paths in weighted graphs, using Dijkstra's algorithm as an example.

    Original Title

    Graphs

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses graphs and graph algorithms. It defines what graphs are, including vertices and edges. It covers different types of graphs like social networks and road networks. It also discusses common graph problems like finding paths and shortest paths. It explains how graphs can be represented and stored in memory using adjacency matrices and lists. It then covers graph search algorithms like depth-first search and breadth-first search. Finally, it discusses algorithms for finding shortest paths in weighted graphs, using Dijkstra's algorithm as an example.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    27 views28 pages

    Data Structures and Algorithm: Graphs

    Uploaded by

    Aman Baze
    This document discusses graphs and graph algorithms. It defines what graphs are, including vertices and edges. It covers different types of graphs like social networks and road networks. It also discusses common graph problems like finding paths and shortest paths. It explains how graphs can be represented and stored in memory using adjacency matrices and lists. It then covers graph search algorithms like depth-first search and breadth-first search. Finally, it discusses algorithms for finding shortest paths in weighted graphs, using Dijkstra's algorithm as an example.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 28

    DATA STRUCTURES AND

    ALGORITHM
    GRAPHS
    WHAT ARE GRAPHS
     A set of vertices
    connected by pairwise
    edges
     Why Study Graphs?
     Thousands of practical
    applications.
     Hundreds of graph
    algorithms known.
    GRAPH TERMINOLOGIES
     Path: Sequence of
    vertices connected by
    edges.
     Cycle: Path whose first
    and last vertices are the
    same.
     A tree is a graph without a
    cycle!
     Degree of a vertex:
    number of connections
    to/from a vertex
    FLAVORS OF GRAPH
    THE INTERNET
     Nodes:
     Computers
     Switches
     Routers

     Edges:
     Connections

     Weight:
     bandwidth,
     latency …
    SOCIAL NETWRORKS
     Vertices: People, Edges: Relationships
     Weight: Level of interaction among people
    ROAD NETWORK
     Vertices: Intersections;
     Edges: one way streets

     Weight: distance (or maybe road conditions)


    VERY COMMON GRAPH PROBLEMS
     Path: Is there a path from vertex A to vertex B?
     Checking network connectivity
     Garbage Collection

     Shortest Path: what is the shortest path between two


    vertices
     e.g. Network routing
    How is it stored in memory?

    GRAPH REPRESENTATION
    ADJACENCY-MATRIX REPRESENTATION
     Maintain a 2D V-by-V Boolean array
     adj[i][j] is set to one if vertex i is connected to vertex j
    ADJACENCY-LIST REPRESENTATION
     Maintain vertex-indexed array of lists.
    WHICH REPRESENTATION IS BETTER?
     Adjacency-matrix
     Takes O()
     A waste of space if the
    graph is sparse
     Adjacency-list
     Takes O(V+E)
     Good choice for many
    applications
     Most real world matrices
    are sparse
    GRAPH SEARCH
    MOTIVATION
     Goal: Given a starting vertex, s, find all vertices
    connected to s
     Two Commonly used Search Algorithms:
     Depth First Search(DFS)
     Breadth First Search(BFS)
    DEPTH FIRST SEARCH – THE IDEA
     The algorithm aggressively moves away from the
    starting node.
     We only go back when we there is a dead end
    DEPTH FIRST SEARCH -
    IMPLEMENTATION
     DFS uses a stack to remember where it should go when
    it reaches a dead end.

     Steps in DFS:
    Step 1: Pick a starting node
    Step 2: If possible, visit an adjacent unvisited vertex,
    mark it, and push it on the stack.
    Step 3: If there are no unvisited nodes, then pop a
    vertex off the stack, if it is not empty, and repeat step 2
    Step 4: If stack is empty, you are done. It’s possible to
    have a recursive implementation instead of using a stack
    DFS APPLICATION: FINDING A PATH
     Property of DFS: During DFS, the stack contains the
    path taken to reach at the current node
     This can be used to quickly determine a path from one
    vertex to another.
     Example use cases:
     findingdriving directions.
     checking connectivity in a network
    BREADTH FIRST SEARCH – THE IDEA
     Unlike DFS, BFS tries to stay as close to the starting
    position as possible
     It only then goes further when all the vertice adjacent to
    the starting vertex are visited
    BREADTH FIRST SEARCH -
    IMPLEMENTATION
     Uses a queue instead of a stack

    Steps in BFS:
    Step 1: Pick a starting node
    Step 2: If possible, visit an adjacent unvisited vertex,
    mark it, and insert it into the queue
    Step 3: If there are no unvisited adjacent nodes, then
    remove a vertex from the queue.
    Step 4a: if queue is not empty go to step 2.
    Step 4b: If the queue is empty, you are done
    BFS APPLICATION: SHORTEST PATH
     Property of BFS: It first finds all the vertices that are one
    edge away from the starting point, then all the vertices
    that are two edges away, and so on.
     When you find the specified vertex using BFS, you
    know the path you’ve traced so far is the shortest path to
    the node.
     This is only true for unweighted graph
     In communication networks, it can be used to find the
    route with minimum hops
    ALGORITHMS FOR WEIGHTED
    GRAPHS
    SHORTEST PATH
     Goal: Given a weighted, directed graph, find the shortest
    path from s to t.
     We will see Djikstra’s algorithm for finding the shortest
    path from one vertex s, to every other vertex (single
    source shortest path problem)
     Caution: Djikstra’s algorithm does not work if you have
    negative edge weightes
    DIJKSTRA’SALGORITHM –
    ILLUSTRATION(1/6)
    DIJKSTRA’SALGORITHM –
    ILLUSTRATION(1/6)
    DIJKSTRA’SALGORITHM –
    ILLUSTRATION(3/6)
    DIJKSTRA’SALGORITHM –
    ILLUSTRATION(4/6)
    DIJKSTRA’SALGORITHM –
    ILLUSTRATION(5/6)
    DIJKSTRA’SALGORITHM –
    ILLUSTRATION(6/6)

    You might also like