# Graphs Flashcards

1
Q

What is the definition of a graph?

A
2
Q

What does adjacent mean in a graph? Draw an example.

A
3
Q

What is the definition of an undirected graph?

A
4
Q

What is the definition of a directed graph?

A
5
Q

Explain how a tree is a directed graph

A
6
Q

What is a path in a graph?

A
7
Q

What is a cycle in a graph?

A
8
Q

What does connected mean in a graph?

A
9
Q

What does it mean for a graph to be complete?

A
10
Q

What is a subgraph in a graph?

A
11
Q

What type of information can the vertices represented in a graph?

What type of information can an edge represent in a graph?

A

Vertices

• The vertices in a graph may represent something(cities on a map, computers in a network)
• Vertices in a graph may contain information(information about the cities or computers represeted

Edges

• The edges may represent spatial connections between vertices or some other type of connection between the vertices.
• The edges may also contain information(distance between two cities, the cost of travel between two cities, capacity of a computer connection, weight of a connection in a neural network).
• If the information is a number, then the graph is called a weighted graph
12
Q

In general, what is an Adjacency Matrix?

A
13
Q

What is an example of an adjacency matric of an undirected graph?

A
14
Q

What is an example of an adjacency matrix of a Digraph

A
15
Q

What is an example of an adjacency matrix of a weighted graph?

A
16
Q

What are the advantages and disadvantages of an adjacency matrix?

A
17
Q

What is an adjacency list?

Show examples of undirected and digraphs.

A
18
Q

What are the advantages and disadvantages of an adjacency list?

A
19
Q

How do you decide to use an adjacency matrix or list?

A
20
Q

What is the definition and two types of a graph traversal?

A
21
Q

Perform a depth-first traversal of the following graph, draw the stack at each step.

What would the output be if we printed the contents of the vertex when we visit it?

A

Attached is an example of one step.

Output: 0, 1, 2, 4, 3, 6, 7, 5, 8, 9

22
Q

Display the output and the stack for a depth-first traversal of this graph starting at 6.

A
23
Q
A
24
Q

What is the Pseudocode for a depth-first traversal?

A
25
Q

What is a breadth-first traversal in a graph? Perform one on the following graph and print the output:

A

A breadth-first traversal visists all nearby vertices first before moving farther away. It is a queue-based, iterative traversal

26
Q
A
27
Q
A
28
Q

What is the Pseudocode for a breadth-first traversal?

A
29
Q

What needs to be done to record paths for a breadth-first traversal?

A
30
Q

Traverse the following example and show how you would record the path for a breadth-first traversal.

A
31
Q

What are connected components?

A
32
Q

How does a traversal work for unconnected graphs?

A
33
Q

What is the difference in the path that Depth-first and Breadth-first take?

A