Graphs

Question 1

What is a graph?

Answer 1

A set of vertices and edges. Each edge connects a pair of verticies

Question 2

What is a path in a graph

Answer 2

A sequences of vertices connected by edges with no repeated edges

Question 3

What is a simple path in a graph?

Answer 3

A path (which is a sequence of vertices connected by edges, with no repeated edges) with no repeated vertices.

Question 4

What is a cycle in a graph?

Answer 4

A path (which is a sequence of vertices connected by edges, where no edge is repeated) with at least one edge. The path’s first and last vertices are the same.

Question 5

What is a simple cycle?

Answer 5

A cycle (which is a path with at least one edge whose first and last vertices are the same, and where a path is a sequence of vertices connected by edges with no repeated edges) with no repeated vertices. Note that the first and last vertices will be the same.

Question 6

What is the length of a cycle or path in a graph?

Answer 6

It is the number of edges in a path (vertices connected by edges with no repeated vertices) or a cycle (path with at least one edge whose first and last vertices are the same).

Question 7

What is a connected graph?

Answer 7

A graph that contains a path (vertices with no rotated edges) between all vertices.

Question 8

Describe a tree in terms of a graph

Answer 8

An acyclic connected graph (or a graph with no cycles and where every vertex has a path to every other vertex)

Question 9

What is a spanning tree of a connected graph?

Answer 9

A connected graph is a graph that contains a path from every vertex, to every other vertex. The spanning tree is a subgraph that contains all the vertices of the connected graph. The subgraph is a tree (acyclic and connected graph)

Question 10

Describe how a depth first search algorithm visits the vertices of a graph

Answer 10

When visiting a vertex

1. Mark it as visited
2. Visit (recursively) all the vertices that are adjacent to it and that have not yet been marked

Question 11

What is the time complexity of DFS when marking all nodes?

Answer 11

The time complexity is proportional to the sum of all vertices degrees.

Question 12

Write a simple DFS algorithm that searches each vertex.

Answer 12

private void dfs(int source) {

marked[source] = true;
count++;
for(int w : adj.get(source))
if (!marked[w]) dfs(w)

Question 13

Name two problems DFS can solve when looking at graphs

Answer 13

Connectivity: are two different vertices connected? How many connected components does a graph have?

Single-source paths: find a path from source vertex to target vertex

Question 14

Write a simple DFS algorithm that finds paths from a source to all vertices

Answer 14

Utilize an array called edgeTo[], where edgeTo[w] = v indicates that v-w edge accesses w first in the path. The array is a parent-link representation of the tree rooted at the source. Said another way v is the parent of w.

Private void dfs(int s) {
marked[v] = true;
for (int w : adj.get(s)) {
if (!marked[w]) {
edgeTo[w] = s;
dfs(w);
}
}
}

Question 15

What is the time complexity of a depth first search algorithm providing a path from a source vertex to a target vertex?

Answer 15

The time complexity is equal to the length of the path.

Question 16

Name one problem breadth first search solves

Answer 16

This algorithm solves the single-source shortest paths problem. This is equivalent to finding the shortest path (path with fewest edges) from source to some vertex.

Question 17

How does breadth first search visit each vertex?

Answer 17

This algorithm visits each graph vertex by:
Remove the next vertex from the queue
Put onto the queue all unmarked vertices that are adjacent to the vertex and mark them as seen.

Question 18

Write a breadth first search algorithm that visits all nodes and records a path from a source to all vertices

Answer 18

Utilize the edge to array to record each vertices parent vertex. Each vertex in the graph is visited first from their parent vertex.

private void bfs(int s) {
Queue<Integer> queue = new Queue<Integer>();
marked[s] = true;
while(!queue.isEmpty()) {
int v = queue.dequeue();
for(int w : adj.get(v)) {
if (!marked[w]) {
edgeTo[w] = v;
marked[w] = true;
queue.enqueue(w);
}
}
}</Integer></Integer>

}

Question 19

Write a breadth first search algorithm that visits all nodes and records a path from a source to all vertices

Answer 19

Utilize the edge to array to record each vertices parent vertex. Each vertex in the graph is visited first from their parent vertex.

private void bfs(int s) {
Queue<Integer> queue = new Queue<Integer>();
marked[s] = true;
while(!queue.isEmpty()) {
int v = queue.dequeue();
for(int w : adj.get(v)) {
if (!marked[w]) {
edgeTo[w] = v;
marked[w] = true;
queue.enqueue(w);
}
}
}</Integer></Integer>

}

Question 20

Which graph algorithm finds the shortest path from source vertex s to all vertices?

Answer 20

The breadth first search algorithm finds these paths within a graph

Question 21

What is the worst case time complexity of breadth first search?

Answer 21

The worst case time complexity of this graph algorithm is Edges+Vertices

Question 22

What is the worst case time complexity of breadth first search?

Answer 22

The worst case time complexity of this graph algorithm is Edges+Vertices

Question 23

How can you modify the depth first search algorithm to determine if two vertices are connected?

Answer 23

Modify the depth first search algorithm by assigning a count or id value to every source vertex passed to the DFS method. The count value is a class instance variable. The DFS method is called for every vertex in the graph that has not been marked (visited) yet. Every time a DFS is called, increase the instance count value. This will ensure that every vertex that is reached by the DFS algorithm will be assigned to the same id value. Therefore, all vertices within the same subgraph will have the same id.