Graphs and Programgraphs Flashcards
What is a directed graph?
A directed graph, also known as a digraph, is a set of nodes or vertices connected by edges, where the edges have a direction and connect one node to another.
What does a directed graph consist of?
A directed graph consists of a set of nodes or vertices (V) and a set of edges (E).
What is an edge in a directed graph?
An edge in a directed graph is a pair of nodes that shows the direction of the edge. The pair is written as (n, m), where n is the start node and m is the end node.
What is the difference between a directed graph and an undirected graph?
In a directed graph, edges have a direction, whereas in an undirected graph, edges have no direction.
What is the indegree of a node in a directed graph?
The indegree of a node in a directed graph is the number of edges that have the node as their end node.
What is the outdegree of a node in a directed graph?
The outdegree of a node in a directed graph is the number of edges that have the node as their start node.
Can a node in a directed graph have both indegree and outdegree?
Yes, a node in a directed graph can have both indegree and outdegree, or it can have only one of them depending on the graph structure.
What is a source node in a directed graph?
A source node is a node in a directed graph with an indegree of 0, meaning there are no edges pointing into that node.
What is a sink node in a directed graph?
A sink node is a node in a directed graph with an outdegree of 0, meaning there are no edges coming out of that node.
What is a transfer node in a directed graph?
A transfer node is a node in a directed graph with both an indegree and an outdegree that are greater than 0, meaning there are edges coming into and out of that node.
What is a directed path in a graph?
A directed path is a sequence of edges in a directed graph where each edge connects the end node of the previous edge to the start node of the next edge.
What is the empty sequence in a directed path?
The empty sequence, denoted by <>, is a valid directed path in a graph that consists of no edges and no nodes.
What is a cycle in a directed graph?
A cycle in a directed graph is a directed path that begins and ends at the same node, with at least one non-empty sequence of edges between the start and end nodes.
Is the empty sequence a cycle in a directed graph?
No, the empty sequence is not a cycle in a directed graph because it does not connect any nodes or edges.
What is control flow?
Control flow, also known as flow of control, refers to the order in which statements within a program are executed.
How is a Java program represented as a graph?
A Java program can be represented as a directed graph, where nodes represent statements or fragments of statements, and edges represent the flow of control between statements. An edge is drawn from node i to node j if statement j can be executed directly after statement i.
What are the nodes and edges in a program graph?
Nodes in a program graph represent individual statements or fragments of statements in the Java program. Edges represent the flow of control between statements, indicating the order in which they are executed.
What is manual program execution?
Manual program execution involves stepping through a program line by line, executing each statement in turn and observing the output or changes to program state.
How can manual program execution help understand control flow?
By manually executing a program and observing the order in which statements are executed, one can gain a better understanding of the control flow of the program. This can help with debugging and identifying potential issues with the flow of control.
What is the relation between the program graph and control flow?
The program graph is a visual representation of the control flow of a program. It shows the order in which statements are executed and the flow of control between them. Every path through the program graph corresponds to a possible execution of the program.
What is the significance of the source node and sink node in a program graph?
The source node is the node in a program graph that represents the starting point of the program, while the sink node represents the end point of the program. Every terminating execution of the program corresponds to a path through the program graph that begins at the source node and ends at the sink node.
Can there be multiple paths through a program graph that correspond to the same execution of a program?
No, every terminating execution of a program corresponds to exactly one path through the program graph. However, there may be multiple paths through the graph that represent different ways of reaching the same end result.
How can program graphs be useful in testing and debugging?
Program graphs can help identify paths through the program that have not been executed or tested, allowing for more comprehensive testing. They can also help identify potential logic errors or issues with the flow of control in the program. By visualizing the control flow of the program, developers can better understand how the program works and identify areas for improvement.
