# Week 12 - Graph traversals

## Team

Team name:
Date:

Members

| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | |

## Activities

### Activity 1: Application of graphs
What does the graph represent?
• What do the vertices and edges represent?
• Are the edges directed or undirected? Why?

1) Facebook, vrienden op facebook, de connecties tussen de mensen, undirected want het gaat niet 1 richting op.
2) World wide web, paginas op het internet, directed want er kan een link op een pagina staan (pagina a naar pagina b), maar pagina b hoeft geen link te hebben naar pagina a.
3) Infrastructuur tussen steden, de wegen, undirected want het kan beide kanten.

### Activity 2: Representing graphs

Stikvraag het is een hashtable

### Activity 3: Graph construction

if (run_activity_3) {
        // activity 3
        // build an undirected graph that matches the graph of Figure 1
        graph undirected{false};
        // TODO: add edges
        undirected.add_vertex("a");
        undirected.add_vertex("b");
        undirected.add_vertex("c");
        undirected.add_vertex("d");
        undirected.add_vertex("e");
        undirected.add_vertex("f");
        undirected.add_vertex("h");
        undirected.add_edge("a", "c");
        undirected.add_edge("c", "b");
        undirected.add_edge("c", "d");
        undirected.add_edge("b", "d");
        undirected.add_edge("d", "e");
        undirected.add_edge("c", "f");
        undirected.add_edge("f", "h");
        undirected.to_dot("act3-undirected.dot");

        // build a directed graph that matches the graph of Figure 2
        graph directed{true};
        directed.add_vertex("a");
        directed.add_vertex("b");
        directed.add_vertex("c");
        directed.add_vertex("d");
        directed.add_vertex("e");
        directed.add_vertex("f");
        directed.add_vertex("h");
        directed.add_edge("c", "a");
        directed.add_edge("a", "b");
        directed.add_edge("b", "d");
        directed.add_edge("d", "c");
        directed.add_edge("d", "e");
        directed.add_edge("h", "e");
        directed.add_edge("e", "f");
        directed.add_edge("f", "h");
        directed.to_dot("act3-directed.dot");
    }

### Activity 4: A first traversal

Rechter graph traverse gaat in een eindeloze loop.

### Activity 5: Find all reachable vertices

Record your answer here

### Activity 6: Recursion overhead

Record your answer here

### Activity 7: Iterative traversal

And that's how you insert code blocks:

double *number = malloc(sizeof(double));

### Activity 8: Breadth-first search

### Activity 9: Comparison

### Activity 10: Cycles and visited nodes

### Activity 11: Understanding the recursion

### Activity 12: Understanding the iteration

### Activity 13: Cycle detection

## Look back

### What we've learnt

Fill in...

### What were the surprises

Fill in...

### What problems we've encountered

Fill in...

### What was or still is unclear

Fill in...

### How did the group perform?

How was the collaboration? What were the reasons for hick-ups? What worked well? What can be improved next time?