18 Graphs

19 Key concepts

19.1 Graph representations

A graph is a collection of nodes (also known as vertices) and edges that connect these nodes. Graphs are used to model relationships between objects or data points. The key concepts in a graph include:

Nodes or vertices: These are the points in the graph that represent objects or data points.
Edges: These are the connections between nodes that represent relationships between objects or data points. Edges can be directed (pointing in a specific direction) or undirected (bi-directional).
Weight: Some graphs have weights assigned to their edges to represent the cost, distance, or other quantitative measure of the relationship between nodes.
Paths: A path in a graph is a sequence of edges that connect a sequence of nodes.
Cycles: A cycle is a path that starts and ends at the same node.

Graphs can be represented in various ways, including:

Adjacency matrix: A two-dimensional array where the rows and columns represent nodes, and the values in the matrix indicate whether there is an edge between the nodes.
Adjacency list: A list of lists where each list represents a node, and the elements in each list are the nodes that are adjacent to that node.
Edge list: A list of tuples where each tuple represents an edge and contains the two nodes that the edge connects.

Each representation has its own strengths and weaknesses depending on the size and nature of the graph, as well as the specific use case.

19.2 Minimum spanning tree

A minimum spanning tree (MST) is a subset of the edges in an undirected, weighted graph that connects all of the vertices and has the minimum possible total edge weight. In other words, a minimum spanning tree is a tree that connects all the vertices of the graph while minimizing the total weight of the edges.

MSTs have many practical applications, such as in network design, transportation planning, and resource allocation. Finding the minimum spanning tree of a graph can be done using algorithms such as Kruskal’s algorithm, Prim’s algorithm, and Boruvka’s algorithm.

MSTs have several properties, such as:

An MST is always a tree, which means it does not contain any cycles.
An MST must connect all the vertices in the graph.
If the graph has multiple MSTs, then they will have the same total weight.
If the graph has unique edge weights, then the MST is also unique.

Finding the minimum spanning tree of a graph is an important problem in graph theory with many practical applications.

19.3 Shortest path finding

Shortest path finding is the problem of finding the shortest path between two nodes in a graph. This problem has many applications in areas such as transportation planning, network routing, and computer networking.

In a weighted graph, the shortest path between two nodes is the path with the lowest total weight. The weight of a path is the sum of the weights of all the edges in the path. Shortest path finding algorithms can be classified as either single-source or all-pairs algorithms.

Single-source algorithms find the shortest path from a single source node to all other nodes in the graph. Common single-source algorithms include Dijkstra’s algorithm and Bellman-Ford algorithm.

All-pairs algorithms find the shortest path between all pairs of nodes in the graph. The most well-known all-pairs algorithm is the Floyd-Warshall algorithm.

Shortest path finding algorithms can be implemented using a variety of data structures, such as priority queues, heaps, and adjacency lists. The choice of data structure depends on the specific algorithm being used and the characteristics of the graph being analyzed.

Overall, shortest path finding is an important problem in graph theory and has many practical applications in various fields.

20 Learning outcomes

20.1 Use different implementations of graphs (matrix adjacency, list adjacency. Edge list)

Here are some examples of how to use different implementations of graphs:

Matrix adjacency: In this implementation, the graph is represented as a 2D matrix where each row and column represents a vertex, and the entries in the matrix represent the edges between vertices. For example, if we have a graph with 4 vertices and edges (1,2), (1,3), and (2,4), the matrix representation would look like this:

    1   2   3   4
1   0   1   1   0
2   1   0   0   1
3   1   0   0   0
4   0   1   0   0

List adjacency: In this implementation, the graph is represented as a list of lists, where each vertex has a list of its adjacent vertices. For example, if we have the same graph as before, the list representation would look like this:

graph = [[2,3],
         [1,4],
         [1],
         [2]]

Edge list: In this implementation, the graph is represented as a list of tuples, where each tuple represents an edge in the graph. For example, if we have the same graph as before, the edge list representation would look like this:

graph = [(1,2),         (1,3),         (2,4)]

These are just a few examples of how to implement and use different representations of graphs. The choice of implementation depends on the specific problem being solved and the characteristics of the graph being analyzed.

20.2 Implement Prim’s algorithm to find the minimum spanning tree

Here is an example of how to implement Prim’s algorithm in pseudocode to find the minimum spanning tree of a graph:

Prim's algorithm (graph G, starting node s):
    Let S be the set of visited vertices, initially empty
    Let Q be the set of vertices in G, sorted by distance from s
    Let D be an array of distances, initialized to infinity for all vertices except s, which is initialized to 0
    Let P be an array of parent vertices, initially null for all vertices

    While Q is not empty:
        Let u be the vertex in Q with the minimum distance
        Remove u from Q and add it to S
        For each vertex v adjacent to u:
            If v is not in S and the weight of (u,v) is less than D[v]:
                Set D[v] to the weight of (u,v)
                Set P[v] to u
                Update the position of v in Q based on its new distance

    Return the set of edges {P[v], v} for all vertices v

In this algorithm, we maintain three data structures: S, which represents the set of visited vertices; Q, which is a priority queue of vertices sorted by distance from the starting node s; and D and P, which are arrays used to keep track of the distances and parent vertices for each vertex.

The algorithm starts by initializing the data structures, and then repeatedly selects the vertex with the minimum distance from Q, adds it to S, and updates the distances and parent vertices for its adjacent vertices if necessary. The algorithm terminates when all vertices have been visited.

Finally, the algorithm returns the set of edges {P[v], v} for all vertices v, which represents the minimum spanning tree of the graph.

Note that the specific implementation details, such as the choice of priority queue and the method for updating the position of a vertex in Q, may vary depending on the programming language and the specific use case.

20.3 Implement Dijkstra’s algorithm to find the shortest path between two nodes

Here’s an example of how to implement Dijkstra’s algorithm in pseudocode to find the shortest path between two nodes in a graph:

```textDijkstra’s algorithm (graph G, starting node s, ending node t): Let Q be a priority queue of vertices, sorted by distance from s Let D be an array of distances, initialized to infinity for all vertices except s, which is initialized to 0 Let P be an array of parent vertices, initially null for all vertices Add s to Q

While Q is not empty:
    Let u be the vertex in Q with the minimum distance
    Remove u from Q
    If u is t, return the path from s to t using P
    For each vertex v adjacent to u:
        Let w be the weight of the edge (u, v)
        If D[u] + w < D[v]:
            Set D[v] to D[u] + w
            Set P[v] to u
            If v is not in Q, add it to Q

If t was not reached, return null (there is no path from s to t)

```

In this algorithm, we maintain three data structures: Q, which is a priority queue of vertices sorted by distance from the starting node s; D, which is an array used to keep track of the distances for each vertex; and P, which is an array used to keep track of the parent vertices for each vertex.

The algorithm starts by initializing the data structures and adding the starting node s to the priority queue. It then repeatedly selects the vertex with the minimum distance from Q, removes it from Q, and updates the distances and parent vertices for its adjacent vertices if necessary. The algorithm terminates when the ending node t is reached or when Q is empty.

Finally, if the ending node t was reached, the algorithm returns the path from s to t using the parent vertices in P. Otherwise, it returns null to indicate that there is no path from s to t.