Session 09 Flashcards
1
Q
Applications of Graphs?
A
- Representing relationships between componenets in electronic circuits.
- Transportation networks
- Computer networks
- Databases
2
Q
3 ways of representing graphs?
A
- Adjacency Matrix
- Adjacency List
- Adjacency Set
3
Q
Graph Traversals / Graph search algorithms ?
A
- DFS - Depth First Search
- BFS - Breadth First Search
4
Q
Applications of BFS ?
A
- Finding all connected components in a graph
- Finding all nodes within one connected components
- Finding the shortest path between two nodes
- Testing a graph for bipartiness
5
Q
Applications of DFS?
A
- Topological Sorting
- Finding connected components
- Finding strongly connected components
- Solving puzzles such as Mazes
6
Q
Application of Topological Sorting?
A
- Representing course prerequisities
- Detecting deadlocks
- Pipeline of computing jobs
- Checking for symbolic link loops
- Evaluating formulas in soreadsheets
7
Q
Variations of Shorted path algirithms ?
A
- Shortest path in unweighted graph
- S.p. in weighted graph
- S.p in weighted graph with negative edges
8
Q
Applicaitons for shortest path algorithm?
A
- Finding fastes way to go from one place
- Finding cheapest way to fly/send data from one city to another
9
Q
A
