Lab 12 Notes

Graphs Theory Recap

• what graphs can be used for

  • modeling Facebook
  • modeling Roads/ PC Networks / etc.
  • very useful

• directed graph/nondirected graph

• acyclic graph/DAG, cyclic Graph

• how graph is different from trees?

• how to store a graph ?

  • matrix (easy, not optimal)
  • adjecent list (optmima, not that easy to maintain)

• how to traverse the graph

• BFS, DFS

• what is the main difference wrt BFS, DFS in trees?

  • we need color for each node (white/gray/back)
  • in addtion there are some side-effects can be obtain
  • when traversing

• What we obtain in addition when doing BFS for example

  • discovers all distances reachable from start
  • shortest distance for each node from start
  • spanning tree where start is the root

Today Summary

• today’s lab: show the assignment 8

• we are going to solve first 2 points

• the rest is for your final assignment

Today Work

• discuss graph theory

• show how to store a graph using lists

• implement in Java core of the assignment

  • classes Vertex, VertexNode, VertexList
  • constructors of classes
  • then implement findOrMake and what is needed
    • give them list of methods that they should reimplement
    • test for example print all method // maybe show them testCase
    • findVertex // do it recursivly
    • insertFirst

Organization issues: last 30 mins

- still lot to mark
- I plan to do it in the next 7 days
- We can schedule anothor meeting if you are interested to comment 
and discuss marks if there is enough interested
- Also if you have other questions
- I will send you an email

Recap: DFS algorithm for Trees

• We need queue data structure

Alg

DFS (Tree T)
    Queue q
    q.enqueue(T.head)
    while ! q.empty
        node = q.dequeue()
        print (node)
        for each child of node 
            q.engueue(child)
    end while

• How to adjust it for graphs ?

• We need 3 colors becuase we have cycles ?

• Ask: Do you prefer I just show the algorithm and we discuss?

• Or I develop the algorithm and we discuss while developing?

Observations:

• we calculate distance from the start node
• we need color for each node (white/gray/back)

Alg

DFS (Graph G)
    Queue q
    ColorAllWhite(G)                    // * TODO

    // start with start node    
    s := Graph.startNode()
    s.color := gray                     // *
    s.dist  := 0                        // *
    s.pred  := null                     // *
    q.enqueue(s)

    while ! q.empty()
        node = q.dequeue()
        for each adj node v of node
            if v.color = white          // first time we see it
                v.color := gray         // *
                v.dist  := node.dist+1  // *
                v.pred  := node         // *
                q.enqueue (v)
        node.color := black             // *

    end while

Running time: ?
\Theta( |V| + |E| )

• In this way we obtain:
  • discovers all distances reachable from start
  • shortest distance for each node from start
  • spanning tree where start is the root