Graphs

Question 1

Which is more general, tree or graph?

Answer 1

A graph which can have any combinations of nodes & edges

Question 2

What two classes of graphs are there?

Answer 2

Undirected and directed. Directed graphs have arrow lines as opposed to plane lines.

Question 3

What is the terminology for adjacent nodes for both types of graphs?

Answer 3

Neighbor nodes

Question 4

Which node does the target and source of a directed edge lie, respectively?

Answer 4

predecessor, successor

Question 5

What is an example of a cyclic path and acyclic path?

Answer 5

1→2→3→1 : cyclic
1→2→3→4: acyclic
1→1: cyclic

Question 6

What does DAG stand for?

Answer 6

Directed acyclic graph

Question 7

What is the name of a undirected/directed graph where all nodes neighbor every other node

Answer 7

A complete graph

Question 8

What is an edge called if it is assigned a number?

Answer 8

A weighted edge, which could represent length

Question 9

When is a graph strongly connected?

Answer 9

If every node is reachable with direction

Question 10

When is a graph weakly connected?

Answer 10

If every node is reachable regardless of direction

Question 11

If all nodes can be reached from a set of nodes how is this represented in java?

Answer 11

This can be represented as an array or list of root nodes

Question 12

What condition must bee satisfied in topological numbering?

Answer 12

If the order is u,v then u must always occur before v in any path

Question 13

What nodes are always in the first positions in topological ordering?

Answer 13

nodes with an in-number of zero

Question 14

What is the difference between in-degree, out-degree and degree?

Answer 14

in-deg: edges going in
out-deg: edges going out
deg: all in & out edges

Question 15

What two data structures are best suited for a dfs & bfs respectively?

Answer 15

dfs: stack
bfs: queue, which holds the nodes to be visited at each level

Question 16

What is the distance of a graph?

Answer 16

The number of edges from node A to node B

Question 17

How does an adjacency list represent the graph?

Answer 17

It lists each vertices on the left and all of it’s adjacent nodes on the right

Question 18

What is the complexity to look for weather a node is adjacent?

Answer 18

O(V), because the vertex could be neighbors with every other node, unless the graph is sparse (doesn’t have many edges)

Question 19

How does the adjacency list differ from the adjacency matrix?

Answer 19

The list of neighboring vertices is replaced by a list of 1 & 0 creating a 2x2 matrix

Question 20

Why is an adjacency list more efficient for sparse graphs, while an adjacency matrix is not?

Answer 20

Because the size of the matrix is O(V^2), which is unnecessary since a list wouldn’t have to include the 0’s

Question 21

For an 2D array implementation of an adjacency matrix what is the complexity for a an edge lookup?

Answer 21

O(1)

Question 22

What is the size of a graph?

Answer 22

O(V+E)

Question 23

What is a method where all nodes are visited in an arbitrary order?

Answer 23

graph traversal

Question 24

What is the general idea of a breadth-first-search?

Answer 24

traversal that visits a starting vertex, then all vertices of distance 1 from that vertex, then of distance 2, and so on, without revisiting a vertex

Question 25

Is a BFS always unique?

Answer 25

No, if there are vertices the same distance from the root node, then there are multiple cases

Question 26

What is the maximum amount of times a vertex is visited in a BFS?

Answer 26

1

Question 27

How are vertexes at any given level kept track of during the traversal?

Answer 27

1.) vertex is added to frontier queue
2.)vertex is added to discovered stack
3.)front of frontier queue is visited
4.)continues until frontier queue is empty
ie.
While the queue is not empty, the algorithm pops a vertex from the queue and visits the popped vertex, pushes that vertex’s adjacent vertices (if not already discovered), and repeats.

Question 28

What is the general idea of the depth-first-search?

Answer 28

To pick a adjacent node from the root and continue to the greatest distance away, then backtrack to an unvisited node and repeat

Question 29

What is the procedure to do a dfs programmatically?

Answer 29

1. ) Put the first node visited on the stack
2. )put all adjacent nodes on the stack
3. )visit the topmost unvisited node
4. )pop it from the stack along with all other visited nodes and repeat

Question 30

Can a dfs be implemented recursively?

Answer 30

yes

Question 31

What is the terminating side of the edge?

Answer 31

The target edge

Question 32

In a weighted graph what algorithm can find the shortest path from one vertex to another?

Answer 32

Dijkstra’s algorithm

Question 33

What is the algorithm for Dijkstra’s method?

Answer 33

1. ) set cost at initial node to 0 and the rest to infinity
2. ) set cost to neighboring nodes to the weight of each respective edge
3. ) choose lesser cost and repeat the process for that node

Question 34

How are the costs to every node for every iteration represented?

Answer 34

A (5), C (∞), E (∞), D (1); infinity is the cost for non-adjacent nodes

Question 35

Does Dijkstra’s method work for unweighted graphs?

Answer 35

Yes, each edge gets a weight of 1 or c

Question 36

Does Dijkstra’s method work for weighted graphs with negative edges?

Answer 36

No

Question 37

What is topological ordering for?

Answer 37

DAGs, otherwise it’s not possible

Question 38

What methods can be used to create a topological ordering?

Answer 38

A recursive/iterative modified dfs algorithm