<p>I think the best place it could go would be whenever 2D arrays are introduced.  You could use them to represent the <a href="https://en.wikipedia.org/wiki/Adjacency_matrix" rel="nofollow noreferrer">adjacency matrix</a> of a graph and use that to begin answering all kinds of graph theory questions.  </p>

<p>You potentially could also cover it after going through class design and ArrayLists if you want to create a Vertex, Edge, and Graph classes... but I think this might get a little too complicated for AP A (they haven't even done LinkedLists yet!)</p>

CC BY-SA 3.0
2017-06-13T18:10:23.937Z
The question seemed a bit odd. Does the OP have a plethora of students scoring 5? If so that's an anomaly and congrats. Certainly, we can use many topics to explore CS, but time is short in a CS AP class and there's a lot to be covered. Perhaps, the time might be better spent exploring the topics covered on the AP test more thoroughly? Perhaps an array game?
d-cubed
CC BY-SA 3.0
2017-06-13T18:24:43.320Z
We do, indeed. We have an usual program with a HS CS "major", along with a 4-year core CS curriculum. My AP CS A kids enter the course about half a year ahead. They also simultaneously take a separate CS course, so they are learning linked list, trees, and some low-level concepts. This means that, though I cover the AP curriculum, I have a lot of latitude (and a duty!) to include other important concepts.
Ben I.
CC BY-SA 3.0
2017-06-13T17:31:38.000Z
2017-06-13T17:31:38.000Z
Matthew Fahrenbacher
<p>After 2D arrays is a good place.  We have them represent the adjacency matrix of a graph and create an adjacency list.  The students work through Warshall's, Floyd's, and Dijkstra's algorithms.  Then we wrap up with implementing DFS and BFS.</p>

CC BY-SA 3.0
2017-07-23T15:10:50.820Z
Welcome to [cseducators.se]. This might be a very good answer, but it could really benefit from some explanations and details. Could you add some details and explanations or examples on how to integrate your suggestion into the ap cs a curriculum?
ItamarG3
CC BY-SA 3.0
2017-07-23T15:02:07.070Z
2017-07-23T15:02:07.070Z
CS Cheerleader
<p>You may very well have some examples where you can discuss state machines and hence state diagrams, that is, graphs. </p>

<p>For example, if you're creating a game with a computer controlled character, that character might be in different states: pursue, search, attack &lt;-- you can introduce a graph representing the states and transitions.</p>

<p>I wrote about this a bit here: <a href="https://cestlaz.github.io/posts/2012-12-17-layers-of-a-lesson.html" rel="nofollow noreferrer">https://cestlaz.github.io/posts/2012-12-17-layers-of-a-lesson.html</a></p>

<p>If you have a class that goes beyond the APCS-A curriculum and do more recursion, you can look at a maze solver (as I do), knights tour, etc - this lets you discuss searching the state space graph - DFS (and allude to alternatives including heuristic search and such), paths, etc. You can also talk about circuits and cycles (knights tour variants)</p>

CC BY-SA 3.0
2017-06-13T18:42:24.323Z
2017-06-14T22:19:33.153Z
2017-06-14T22:19:33.153Z
Mike Zamansky
<p>During our year-end exit interviews with our outgoing seniors, the students made an explicit request to include some graph theory within our curriculum.  This seems like an excellent idea, but the only place where we can fit it is in AP CS A<sup><strong>1</strong></sup>.</p>

<p>Obviously, graph theory is not within the AP curriculum <em>per se</em>, but I wonder if there is some way to shoe-horn <em>at least a bit of it</em> into a lab somewhere.  Even so, I am having trouble finding a spot within the AP curriculum.  Obviously, AP CS A focuses a great deal on arrays, loops, and objects.  There's not a heavy emphasis on recursion (though it is present).  Is there somewhere where graph theory can find some kind of "fit" within an AP class?</p>

<p><sup><strong>1</strong></sup> I'm unable to find a clean, succinct list of topics covered in AP for those unfamiliar, but this teacher's site has a list of <a href="http://www.intuitor.com/student/AP_CompSci_I_Syl.php" rel="nofollow noreferrer">unit headings</a> that could serve as a very quick overview.</p>

CC BY-SA 3.0
2017-06-13T11:56:14.243Z
To those who might not be familiar with ap cs a curriculum, could you please give a link (perhaps in a comment, as it is not overly needed in the question itself) to a list of subjects covered?
ItamarG3
CC BY-SA 3.0
2017-06-13T15:34:03.373Z
(unable to edit the comment anymore, but it's still useful, to explain why there's need for a footnote in your question) The footnote works just fine, thanks.
ItamarG3
CC BY-SA 3.0
2017-06-13T17:25:21.300Z
Here is the course description as of 2014: https://secure-media.collegeboard.org/digitalServices/pdf/ap/ap-computer-science-a-course-description.pdf
Matthew Fahrenbacher
CC BY-SA 3.0
2017-06-13T18:11:03.823Z
Add it after they take the AP test. We have a couple weeks of school after the test.
d-cubed
<ap-computer-science-a><labs><graph-theory>
Integrating Graph Theory into AP CS A
# Integrating Graph Theory into AP CS A

(Asked by: username_0 on 2017-06-12)

During our year-end exit interviews with our outgoing seniors, the students made an explicit request to include some graph theory within our curriculum. This seems like an excellent idea, but the only place where we can fit it is in AP CS A**1**.

Obviously, graph theory is not within the AP curriculum *per se*, but I wonder if there is some way to shoe-horn *at least a bit of it* into a lab somewhere. Even so, I am having trouble finding a spot within the AP curriculum. Obviously, AP CS A focuses a great deal on arrays, loops, and objects. There's not a heavy emphasis on recursion (though it is present). Is there somewhere where graph theory can find some kind of "fit" within an AP class?

**1** I'm unable to find a clean, succinct list of topics covered in AP for those unfamiliar, but this teacher's site has a list of [unit headings](http://www.intuitor.com/student/AP_CompSci_I_Syl.php) that could serve as a very quick overview.

**Tags:** ap-computer-science-a, labs, graph-theory

> **Comments:**
> **username_1**: To those who might not be familiar with ap cs a curriculum, could you please give a link (perhaps in a comment, as it is not overly needed in the question itself) to a list of subjects covered?  
> **username_1**: (unable to edit the comment anymore, but it's still useful, to explain why there's need for a footnote in your question) The footnote works just fine, thanks.  
> **username_2**: Here is the course description as of 2014: https://secure-media.collegeboard.org/digitalServices/pdf/ap/ap-computer-science-a-course-description.pdf  
> **username_3**: Add it after they take the AP test. We have a couple weeks of school after the test.  

---

## 3 answers

### Answer by username_5 on 2017-06-13. Score: 4

You may very well have some examples where you can discuss state machines and hence state diagrams, that is, graphs.

For example, if you're creating a game with a computer controlled character, that character might be in different states: pursue, search, attack <-- you can introduce a graph representing the states and transitions.

I wrote about this a bit here: <https://cestlaz.github.io/posts/2012-12-17-layers-of-a-lesson.html>

If you have a class that goes beyond the APCS-A curriculum and do more recursion, you can look at a maze solver (as I do), knights tour, etc - this lets you discuss searching the state space graph - DFS (and allude to alternatives including heuristic search and such), paths, etc. You can also talk about circuits and cycles (knights tour variants)


---

### Answer by username_2 on 2017-06-13. Score: 2

I think the best place it could go would be whenever 2D arrays are introduced. You could use them to represent the [adjacency matrix](https://en.wikipedia.org/wiki/Adjacency_matrix) of a graph and use that to begin answering all kinds of graph theory questions.

You potentially could also cover it after going through class design and ArrayLists if you want to create a Vertex, Edge, and Graph classes... but I think this might get a little too complicated for AP A (they haven't even done LinkedLists yet!)

> **Comments:**
> **username_3**: The question seemed a bit odd. Does the OP have a plethora of students scoring 5? If so that's an anomaly and congrats. Certainly, we can use many topics to explore CS, but time is short in a CS AP class and there's a lot to be covered. Perhaps, the time might be better spent exploring the topics covered on the AP test more thoroughly? Perhaps an array game?  
> **username_0**: We do, indeed. We have an usual program with a HS CS "major", along with a 4-year core CS curriculum. My AP CS A kids enter the course about half a year ahead. They also simultaneously take a separate CS course, so they are learning linked list, trees, and some low-level concepts. This means that, though I cover the AP curriculum, I have a lot of latitude (and a duty!) to include other important concepts.  

---

### Answer by username_4 on 2017-07-23. Score: 0

After 2D arrays is a good place. We have them represent the adjacency matrix of a graph and create an adjacency list. The students work through Warshall's, Floyd's, and Dijkstra's algorithms. Then we wrap up with implementing DFS and BFS.

> **Comments:**
> **username_1**: Welcome to [cseducators.se]. This might be a very good answer, but it could really benefit from some explanations and details. Could you add some details and explanations or examples on how to integrate your suggestion into the ap cs a curriculum?  

---

