15 GRAPHS Flashcards by Kaman Hung

What is a graph in computer science?

A fundamental data structure composed of a set of nodes and a set of edges.

How well did you know this?

Not at all

Perfectly

How do graphs differ from other data structures?

Graphs arise naturally from the data itself, mirroring the data they represent.

How well did you know this?

Not at all

Perfectly

What are the two main components of a graph?

Nodes
Edges

How well did you know this?

Not at all

Perfectly

What do undirected edges represent?

Two-way relationships, such as roads or friendships.

How well did you know this?

Not at all

Perfectly

What do directed edges indicate?

A flow in a single direction, like one-way streets.

How well did you know this?

Not at all

Perfectly

What is an example of using directed edges in a task?

Modeling task dependencies, such as the order of brewing coffee.

How well did you know this?

Not at all

Perfectly

What are weighted edges used for in graphs?

To capture the cost of the link between nodes.

How well did you know this?

Not at all

Perfectly

What are the two common representations of graphs in memory?

Adjacency matrices
Adjacency lists

How well did you know this?

Not at all

Perfectly

How does an adjacency list represent a graph?

Stores a separate list of neighbors for each node.

How well did you know this?

Not at all

Perfectly

What does an adjacency matrix consist of?

A matrix with one row and one column for each node, representing edge weights.

How well did you know this?

Not at all

Perfectly

What is the purpose of searching graphs?

To explore nodes and find specific information or paths.

How well did you know this?

Not at all

Perfectly

What is a depth-first search?

A graph search method that explores paths deeply before backtracking.

How well did you know this?

Not at all

Perfectly

What is a breadth-first search?

A graph search method that explores nodes closer to the starting point first.

How well did you know this?

Not at all

Perfectly

What is Dijkstra’s algorithm used for?

Finding the shortest path from a starting node to all other nodes in a graph.

How well did you know this?

Not at all

Perfectly

What is a key constraint for Dijkstra’s algorithm?

All edge weights must be non-negative.

How well did you know this?

Not at all

Perfectly

What data structures does Dijkstra’s algorithm maintain?

Array of distances
Array indicating the last node visited
Set of unvisited nodes

How well did you know this?

Not at all

Perfectly

What happens in each iteration of Dijkstra’s algorithm?

The closest unvisited node is visited and distances to its unvisited neighbors are updated.

How well did you know this?

Not at all

Perfectly

True or False: Dijkstra’s algorithm can work on graphs with negative edge weights.

False

How well did you know this?

Not at all

Perfectly

What is the initial distance setup in Dijkstra’s algorithm?

All distances are set to infinity except for the starting node, which is set to zero.

How well did you know this?

Not at all

Perfectly

Fill in the blank: Dijkstra’s algorithm uses a ______ to improve efficiency.

min-heap

How well did you know this?

Not at all

Perfectly

What does the adjacency list representation provide?

A localized view of neighbor relationships.

How well did you know this?

Not at all

Perfectly

What type of relationships do weighted edges allow us to model?

Complex interrelations among nodes.

How well did you know this?

Not at all

Perfectly

What is an example of a real-world system modeled as a graph?

Social networks, transportation networks, and computer networks.

What is the initial configuration of distances in Dijkstra’s algorithm?

All distances at infinity except for node A, which is set to zero.

What does the last column in Dijkstra's algorithm indicate?

The preceding node for each node in the search.

What is the main purpose of maintaining a back pointer in Dijkstra's algorithm?

To reconstruct the path from the starting node to the target node.

How does Dijkstra's algorithm determine the next node to visit?

By selecting the unvisited node with the smallest distance.

What happens when a shorter path to a neighbor is found in Dijkstra's algorithm?

The distance to that neighbor is updated, along with the back pointer.

True or False: Dijkstra's algorithm can be used for graphs with negative edge weights.

False.

What is the minimum spanning tree of a graph?

The smallest set of edges such that all nodes are connected.

Who independently proposed Prim's algorithm?

R. C. Prim and Vojtěch Jarník.

How does Prim's algorithm operate?

It builds up a minimum spanning tree one node at a time from an unvisited set.

What is the key question Prim's algorithm asks at each iteration?

Which unvisited node is closest to the currently visited set?

What data does Prim's algorithm maintain at each step?

The best edge (including weight) to each node.

Fill in the blank: Prim's algorithm focuses on minimizing the cost of _______.

[adding new nodes to the connected set].

True or False: The final spanning tree produced by Prim's algorithm is always unique.

False.

What type of graph does Kahn's algorithm work on?

Directed acyclic graph (DAG).

What is the purpose of topological sorting?

To order nodes based on their dependencies in a directed acyclic graph.

How does Kahn's algorithm identify nodes to add to the sorted list?

By finding nodes with no incoming edges.

What do we track in Kahn's algorithm instead of actually removing edges?

An auxiliary array counting the number of incoming edges to each node.

What does a directed edge from A to B indicate in a DAG?

Node A must come before node B.

What is the significance of cycles in real-world road networks?

They allow for return paths, which are absent in acyclic graphs.

How does the algorithm terminate in Kahn's algorithm?

When all nodes have been added to the sorted list.

What is Kahn’s algorithm used for?

Topological sorting of a directed acyclic graph ## Footnote Kahn's algorithm is particularly useful for ordering tasks or nodes where dependencies exist.

What auxiliary data structures does Kahn's algorithm utilize?

An array for sorted nodes, an array for counting incoming edges, and a stack for next nodes ## Footnote These structures help manage the nodes and their relationships during the sorting process.

What does the count array represent in Kahn's algorithm?

The number of incoming edges for each node ## Footnote This helps in identifying nodes that can be processed next during the topological sort.

How does Kahn’s algorithm identify initial nodes for processing?

It finds nodes with zero incoming edges and adds them to the stack ## Footnote This step is crucial as it starts the sorting process with nodes that have no dependencies.

What happens in the WHILE loop of Kahn's algorithm?

It processes nodes from the stack and updates the count of incoming edges for their neighbors ## Footnote Nodes with zero incoming edges are added to the stack for further processing.

What is a potential issue if the graph contains cycles?

The sorted list will be incomplete ## Footnote In such cases, an additional check is needed to ensure all nodes are processed.

What is the significance of directed edges in Kahn's algorithm?

They constrain how nodes are explored and processed ## Footnote This directionality is essential for accurately representing dependencies.

What real-world phenomena can graphs represent?

Streets, social networks, computer networks, complex tasks ## Footnote Graphs provide a versatile framework for modeling various systems and relationships.

What tasks can graphs be useful for in computer science?

Path planning, program compilation order, searching, minimum spanning tree, maximum flow determination ## Footnote These tasks highlight the practical applications of graph algorithms.

True or False: Kahn's algorithm removes edges from the graph during execution.

False ## Footnote It modifies counts rather than actually removing edges.

Fill in the blank: In Kahn's algorithm, after processing a node, its outgoing edges' counts are _______.

decreased

What is the end goal of Kahn's algorithm?

To return a sorted array of nodes ## Footnote This sorted array represents a valid topological ordering of the nodes.

What is the relationship between data structure and algorithms in the context of graphs?

The structure of the data drives new problems and algorithms ## Footnote Understanding data structure is vital for defining problems and finding solutions.