(7) Graphs

Question 1

Definition Graphs

Answer 1

• Graphs allow to represent pairs of elements and a relationship between these elements
• A graph is a pair of a set of vertices V (nodes) and a set of edges E (pairs)

Question 2

How is a graph implemented?

Answer 2

1. Store all vertices: Create a class Vertex and store for each vertex one object in a VertexNode in a List
2. Store all edges: - Option 1: Create a class Edge with two attributes of the type Vertex, create an edge object for each edge in the graph and store all Edge objets in EdgeNodes in a List
   - Option 2: create a list of neighbours in each vertex object, and store all neighbours in this list

Question 3

Which classes do we need for a graph?

Answer 3

1. Vertex class: stores some data and a List of VertexNodes with all neighbours
2. VertexNode class: stores a reference to a Vertex and a reference to the next VertexNode
3. List class: stores a reference to the first VertexNode
4. Graph class: stores a List of all the VertexNodes

Question 4

What kinds of graphs exist?

Answer 4

• directed: (v1, v2) does not imply (v2, v1) - undirected graphs (v1, v2) if and only if (v2, v1)

Question 5

Weighted Graph Definition

Answer 5

• weighted graphs have weights attached to each edge (can be directed or undirected)
• in an unweighted graph all edges have same weight

Question 6

What are use cases for graphs?

Answer 6

• Subway networks

- Supply-chains

Question 7

Which methods exist to search in a graph?

Answer 7

• Breadth first search (horizontal first)

- Dealt first search (go as deep as possible)

Question 8

What is the procedure of the breadth-first search algorithm?

Answer 8

1. start at a given node (=current_node)
2. if current_node = e -> we are done
3. if current_node ≠ e:
   - mark current_node as visited
   - enqueue all unmarked nodes which are direct neighbour nodes to current_node in queue nodes_to_visit
   – mark them as added nodes
4. if nodes_to_visit is empty -> we are done, element was not found
5. dequeue element from queue nodes_to_visit and set it as current_node
6. go to step 2

Question 9

What is the time complexity of the breadth-first search algorithm?

Answer 9

• O(E + V)

- Worst Case: all nodes are connected with each other

Question 10

Which algorithm can be used to find the shortest path?

Answer 10

Dijkstra algorithm

Question 11

What is the procedure of the Dijkstra algorithm?

Answer 11

• Initialize the starting node with “0” and all other nodes with ∞
• Repeat the following steps until all nodes are visited (Dijkstra):
  1. Choose an unvisited node with the shortest distance to the initial node and set it as current_node
  2. Check for every unvisited neighbour node of current_node: Is the path via current_node to the neighbour node shorter than the tentative distance to the neighbour node (value in the node)?  update distance value
  4. Mark current_node as visited

Question 12

What is the Dijkstra algorithm used for?

Answer 12

• Find the shortest path from a source node to every other node in the graph

Question 13

What is the time complexity of the Dijkstra algorithm?

Answer 13

• O(V^2 + E) = O(V^2)