- COMP.CS.300
- 7. Graphs
- 7.1 Course topics 10, 11 and 12
Course topics 10, 11 and 12¶
Course topic 10¶
Self-study¶
The topics for this week are the following: (i) Graphs (ii) Breadth first search, (iii) Depth first search, (iv) Implementing a graph in C++
The following links will take you to the video-lectures and the accompanying slides:
Graphs and Trees¶
The following three lecture videos were already part of the course topic on trees. However, since they also cover graphs, they are included here as well.
Breadth first search¶
Depth first search¶
Submit weekly exercises¶
Self-study¶
The topics for this week are (i) Weighted graphs and their implmentation in C++, (ii) Dijkstra’s algorithm, (iii) The A-star algorithm and (iv) The efficiencies of graph search algorithms
The following links will take you to the video-lectures and the accompanying slides:
Weighted graphs and their implmentation in C++¶
Dijkstra’s algorithm¶
video_dijkstra_01: Dijkstra (part 1)
video_dijkstra_02: Dijkstra (part 2)
There is a mistake in section 4 of the slides used in the video. This mistake is corrected in the slides that you can download.
The A-star algorithm¶
The efficiency of three graph algorithms¶
Weighted graphs¶
Dijkstra’s algorithm¶
The A-star algorithm¶
Extra links on the topic:
A site where you can visualize the progress of different graph search algorithms