Graphs

Question 1

A _________________ is a pair V, E ,where V is a finite set and E is a binary relation on V.

Answer 1

directed graph

Question 2

TRUE or FALSE:
Edges from a vertex to itself (self- loops) are possible in a undirected graph.

Answer 2

FALSE. Only possible for directed graphs

Question 3

u -> v

Answer 3

u, v is incident from u and is incident to v.

Question 4

u -> v

Answer 4

v is adjacent to u.

Question 5

TRUE or FALSE:
In an undirected graph G = V, E , E
consists of unordered pairs of vertices.

Answer 5

TRUE

Question 6

u - v

Answer 6

u, v is incident on u and v.

Question 7

u - v

Answer 7

u is adjacent to v and
v is adjacent to u.

Question 8

In an undirected graph, the ________ of
a vertex is the ________________
incident on it.

Answer 8

degree, number of edges

Question 9

In a directed graph:

the ____________of a vertex is the
number of edges leaving it

the _____________ of a vertex is the number
of edges entering it

Answer 9

out-degree, in-degree

Question 10

In a directed graph:

the degree of a vertex is the _____ of its in-degree and its out-degree

Answer 10

sum

Question 11

A ______ from a vertex v0 to a vertex vk is a sequence of vertices

Answer 11

path

Question 12

The _____________ of a path is the number of edges in the path.

Answer 12

length

Question 13

A path is _________ if all vertices in the path are distinct.

Answer 13

simple

Question 14

Graph Representation using adjacency matrix

Answer 14

row is source
column is destination

Question 15

TRUE or FALSE:
In an undirected graph, the adjacency
matrix A is its own transpose: A = AT.

Answer 15

TRUE

Question 16

An array Adj of V lists, one for each
vertex in V.

Adj[u] consists of all the vertices adjacent to u in G.

Answer 16

Adjacency List

Question 17

Running time of operations:

Check if vertex u is adjacent to vertex v

Answer 17

Adj Mat - O(1)
Adj List - O(V)

Question 18

Running time of operations:

List all vertices that
are adjacent to u

Answer 18

Adj Mat - O(|V|)
Adj List - O(|V|)

Question 19

Running time of operations:

List all edges of G

Answer 19

Adj Mat - O(|V^2|)
Adj List - O(|V| + |E|)

Question 20

Adjacency lists provide a compact way to represent _____________
i.e. E significantly less than V2

Answer 20

sparse graphs

Question 21

Adjacency matrices are good for ____________ i.e. E is close to V2.

Answer 21

dense graphs

Question 22

Which is better for checking the adjacency between two vertices.

Answer 22

Adj Mat

Question 23

________________ visits vertices in waves emanating from the source vertex s.

Answer 23

Breadth-first Search (BFS)

Question 24

Starting from source vertex (s), it first visits all neighbors of s

Answer 24

BFS

Question 25

BFS uses a ___________ to do this.

Answer 25

queue

Question 26

BFS Algo (Pseudo code)

Answer 26

bfs(int s, int graphsize){
int j, v, visited[MAXGRAPHSIZE];
queue bfs_queue

for(j = 0; j<graphsize;j++) visited[j] = FALSE

enqueue(s, bfs_queue)

do{
v = dequeue(bfs_queue)
if(!visited[v]){
visited[v] = TRUE
print v
for each vertex j adjacent to v:
if(!visited[j])
enqueue(j, bfs_queue)
}
}while(!isEmpty(bfs_queue))

Question 27

_____________ is similar to the tree preorder traversal.

Answer 27

Depth-first search (DFS)

Question 28

The DFS strategy is to _____________ into the graph whenever possible

Answer 28

search deeper

Question 29

DFS explores edges out of the ______________________ that still has unexplored edges leaving it.

Answer 29

most recently visited vertex v

Question 30

In DFS, once all v’s edges are explored, the search “___________” to the previous vertex and its unexplored edges.

Answer 30

backtracks

Question 31

DFS uses a _________

Answer 31

stack

Question 32

DFS Algo (Pseudo code)

Answer 32

dfs(int s, int graphsize){
int j, v, visited[MAXGRAPHSIZE]
stack dfs_stack

   for(j=0;j<graphsize;j++) visited[j] = FALSE
   push(s, dfs_stack)

   do{
           v = pop(dfs_stack)
           if(!visited[v]){
                  visited[v] = TRUE
                  print v
                 for each vertex j adjacent to v:
                        if(!visited[j])
                             push(j, dfs_stack)
          }
     }while(!isEmpty(dfs_stack))

Question 33

Running time DFS and BFS

Answer 33

O(V+E)

Question 34

A ______________ is a subset of the edges that connects all the vertices together without forming a cycle.

Answer 34

spanning tree

Question 35

Problem Domain: Find a spanning tree whose sum of all the edge-weights is the minimum

Answer 35

Minimum Spanning Tree Problem

Question 36

Algorithms for Minimum Spanning Tree Problem

Answer 36

Kruskal’s and Prim’s Algorithm

Question 37

Grows a forest of edges by considering each edge in sorted order by weight

If the edge joins two distinct trees in the forest, it is added to the forest merging the two trees.

Answer 37

Kruskal’s Algorithm

Question 38

connect trees via the shortest edge

Answer 38

Kruskal’s Algorithm

Question 39

Kruskal’s Algorithm
Pseudo code

Answer 39

1. Sort the edges in increasing order of weight
2. Starting from the edge with the least weight to the last (or until the vertices are included in the tree): - add the to the MST if it doesn’t form a cycle

Question 40

How to check if the addition of an edge(u,v) will form a cycle in the MST

Answer 40

If both u and v belong the the same tree, the edge(u,v) cannot be added to the forest without creating a cycle

Question 41

The tree starts from an arbitrary root vertex and grows until it spans all the vertices in V

Each step adds to the tree an edge that connects it to an isolated vertex, without forming a cycle

Answer 41

Prim’s Algorithm

Question 42

maintain a tree by adding the nearest neighbor

Answer 42

Prim’s Algorithm

Question 43

Prim’s Algo Pseudo code

Answer 43

prims(source):
initialize visited array to zeroes
initialize distance array d to 999
initialize parent array p to -1

d[source] = 0
for number of vertices:
find vertex u, !visited[u] and d[u] is minimum
visited[u] = TRUE
for each vertex v adjacent to u and !visited[v]
distance = weight(edge(u,v))
if distance < d[v]:
d[v] = distance
p[v] = u

Question 44

To get the MST in Prim’s Method, get the edges (parent, vertext)

Answer 44

To get the total edge weight of the MST, take the summation of the distance array

Question 45

A shortest path from vertex u to vertex v is any path p that has the minimum weight (or shortest path length if unweighted)

Answer 45

Single-Source Shortest Path Problem (SSSP)

Question 46

Given a graph G = (V,E) find a shortest path from a given source vertex s ∈ V to every vertex v ∈ V.

Answer 46

SSSP

Question 47

Dijkstra’s Algorithm Pseudo code

Answer 47

dijkstra(source):

initialize visited array to zeroes
initialize distance array d to 999
initialize parent array p to -1

d[source] = 0
for number of vertices:
find vertex u, !visited[u] and d[u] is minimum
visited[u] = TRUE

  for each vertex v adjacent to u and !visited[v]
        distance = d[u] + weight(edge(u,v))
        if distance < d[v]:
               d[v] = distance
               p[v] = u

Question 48

Lemma: A shortest path between two vertices ___________________________ within it.

Answer 48

contains other shortest paths

Question 49

To get the shortest path, trace ______________ from the destination vertex to the source vertex (using parent Array)

Answer 49

BACKWARDS