CMPT435 Assignment 4- Graph  and tree data structures Solved

Goals • to    implement    graph    and    tree    data    structures,    and    to    understand    the    performance    of    
their    traversals
Requirements    
and    Notes • Develop    several    of    your    own    implementations    of    an    undirected    graph.    
The    @ile    graphs1.txt    contains    data    describing    multiple    undirected    
graphs.    Read    it    and    create    three    versions    of    each    graph:    
1. as    a    matrix    
2. as    an    adjacency    list    
3. as    linked    objects    
For    each    graph,    print    the    matrix    and    adjacency    list    versions.    For    the    
linked    objects    version    of    each    graph,    perform    depth-@irst    and    breadth-
@irst    traversals,    printing    each    vertex’s    IDs    as    you    encounter    it.    (I.e.,    print    
all    of    the    vertex    IDs    in    “depth-@irst”    order    and    then    in    “breadth-@irst”    
order.)    
• Develop    your    own    implementation    of    a    binary    search    tree.    Using    the    
text    @ile    magicitems.txt    from    our    web    site,    populate    your    BST    with    
that    data.    
• Randomly    select    42    magic    items    and    look    up    each    in    the    BST.    Print    the    
number    of    comparisons    for    each    lookup    and    compute    the    overall    
average.    
• In    your    LaTeX    summary    and    analysis    document,    analyze    the    asymptotic    
running    time    of    both    graph    traversals    and    explain    why    it    is    that    way.    
Also    analyze    the    asymptotic    running    time    of    BST    lookups    and    explain    
that    as    well.
Of    course,    your    code    must    …        
• separate    structure    from    presentation.    
• be    professionally    formatted    yet    uniquely    yours    (show    some    personality)    
• use    and    demonstrate    best    practices.    
• make    me    proud    to    be    your    teacher.
[−∞    if    not]
Resources • Graphs    are    described    in    our    text    in    section    22.1    on    via    notes    linked    from    our    web    page.    
• Breadth-@irst    and    depth-@irst    traversals    are    described    in    our    text    in    sections    22.2    and    
22.3    respectively.    
• Trees    are    described    in    our    text    in    chapters    12,    13,    and    18.