DAG

0.0(0)
studied byStudied by 0 people
GameKnowt Play
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/10

flashcard set

Earn XP

Description and Tags

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

11 Terms

1
New cards

What does DAG stand for?

Directed Acyclic Graph

2
New cards

What makes a graph "acyclic"?

It contains no cycles, meaning no path leads back to the same node.

3
New cards

What direction does the edge in a DAG represent?

A one-way relationship from one node to another.

4
New cards

Where are DAGs commonly used?

In scheduling, data processing (like Apache Airflow), and blockchain systems.

5
New cards

Can DAGs have loops or cycles?

No, DAGs cannot have cycles.

6
New cards

What is a topological sort?

An ordering of nodes such that for every directed edge from A to B, A appears before B.

7
New cards

Is topological sorting possible in any graph?

No, it is only possible in DAGs.

8
New cards

What is a real-world use of DAGs in computing?

Modeling tasks in job scheduling or version control (like Git).

9
New cards

How is a DAG different from a tree?

A DAG can have multiple parents per node and does not require a root.

10
New cards

What algorithm is often used to detect cycles in a graph?

Depth-First Search (DFS) with recursion stack.

11
New cards