Содержание
- 2. Definition G = (V, E) V – vertexes E – edges
- 3. Types Directed/undirected Weighted/unweighted Simple graph/multigraph Connected/unconnected Bipartite With cycles/without cycles
- 4. Ways of presenting in memory Adjacency matrix Memory: O(|V|^2)
- 5. Ways of presenting in memory Incidence matrix Memory: O(|V|*|E|)
- 6. Ways of presenting in memory List of edges Memory: O(|E|)
- 7. Ways of presenting in memory Adjacency list Memory: O(|E|)
- 8. Problems without explicit graph Labyrinth Number of objects
- 9. Basic algorithms Depth-First Search (DFS) void dfs(int u) { if (used[u]) return; used[u] = true; for
- 10. Basic algorithms Breadth-First Search (BFS) void bfs(int s) { queue q; q.push(s); used[s] = true; while(!q.empty())
- 11. Examples Find cycle in graph Count number of connected components in graph Find distance and path
- 13. Скачать презентацию