- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Introduction to graphs презентация
Содержание
- 1. Introduction to graphs
- 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
- 10. Basic algorithms Breadth-First Search (BFS) void bfs(int
- 11. Examples Find cycle in graph Count number
- 12. Home task http://codeforces.com/group/Hq4vrJcA4s/contest/209195
Definition G = (V, E) V – vertexes E – edges
Слайд 3Types
Directed/undirected
Weighted/unweighted
Simple graph/multigraph
Connected/unconnected
Bipartite
With cycles/without cycles
Слайд 9Basic algorithms
Depth-First Search (DFS)
void dfs(int u)
{
if (used[u]) return;
used[u] = true;
for (auto
v : g[u])
dfs(v);
}
dfs(v);
}
Complexity: O(|V|+|E|)
Слайд 10Basic algorithms
Breadth-First Search (BFS)
void bfs(int s)
{
queue q;
q.push(s);
used[s] = true;
while(!q.empty())
{
int u =
q.front();
q.pop();
for(auto v: g[u])
if(!used[v])
{
q.push(v);
used[v] = true;
}
}
}
q.pop();
for(auto v: g[u])
if(!used[v])
{
q.push(v);
used[v] = true;
}
}
}
Complexity: O(|V|+|E|)
Слайд 11Examples
Find cycle in graph
Count number of connected components in graph
Find distance
and path from one vertex to each other in unweighted graph
