Graph · Licor's Space

Definition and Glossary

A graph is a set of vertices and a collection of edges that each connect a pair of vertices.

A path in a graph is a sequence of vertices connected by edges.

A graph is connected if there is a path from every vertex to every other vertex in the graph.

A cycle is a path with at least one edge whose first and last vertices are the same.

An acyclic graph is a graph with no cycles. A tree is an acyclic connected graph.

A spanning tree of a connected graph is a subgraph that contains all of that graph’s vertices and is a single tree.

A directed graph (or digraph) is a set of vertices and a collection of di- rected edges. Each directed edge connects an ordered pair of vertices.

An edge-weighted graph is a graph model where we associate weights or costs with each edge.

Reverse postorder in a DAG is a topological sort.

Representation of Graph

List of edges
The very primitive way, just keep a list of all the edges in the graph.
Adjacency Matrix
Using a two-dimensional matrix is one of the easiest ways to represent a graph.
Pros: simple to implement
Cons: waste of space if the graph is sparse
Adjacency List Keeping an array of all the vertices in the graph and then each vertex maintains a list of the other vertices that it is connected to is a more space-efficient way.
Adjacency Set
Replace the list with set in the adjacency list representation.

Search

Depth-first search(DFS)
A recursive method. To visit a vertex:
1. Mark it as having been visited.
2. Visit (recursively) all the vertices that are adjacent to it and that have not yet been marked.
```
# graph is adjacency list representation, an array of arrays
def dfs(graph, vertex, visited):
    visited[vertex] = True
    for v in graph[vertex]:
        if not visited[v]:
            dfs(graph, v, visited)
```
Application:
*search in a connected graph *topological sort
Breadth-first search(BFS) Maintain a queue of all vertices that have been marked but whose adjacency lists have not been checked. We put the source vertex on the queue, then perform the following steps until the queue is empty:
1. Take the next vertex v from the queue and mark it.
2. Put onto the queue all unmarked vertices that are adjacent to v.
```
# graph is adjacency list representation, vertices range from 0 to n
def bfs(graph, vertex):
    queue = []
    visited = [False]*len(graph)
    visited[vertex] = True
    queue.append(vertex)
    while(queue):
        v = queue.pop(0)
        for w in graph[v]:
            if not visited[w]:
                visited[w] = True
                queue.append(w)
    return visited
```
Application:
*find a shortest path(one with a minimal number of edges) in a given graph from source vertex to target vertex

Minimum Spanning Tree

Prim’s algorithm
Start with any vertex as a single-vertex tree; then add V-1 edges to it, always taking next the minimum-weight edge that connects a vertex on the tree to a vertex not yet on the tree.

# graph is adjacency matrix representation
def prim(graph):
    start_vertex = 0
    visited = []
    cross_edges = []
    MST = []
    while (len(MST) != (len(graph)-1)):
        visited.append(start_vertex)
        for v in range(len(graph)):
            if graph[start_vertex][v]:
                cross_edges.append([start_vertex, v, graph[start_vertex][v]])
        for e in sorted(cross_edges, key=lambda x: x[2]):
            if e[1] not in visited:
                MST.append(e)
                cross_edges.remove(e)
                start_vertex = e[1]
                break
    return MST

Kruskal’s algorithm
Process the edges in order of their weight values (smallest to largest), taking for the MST each edge that does not form a cycle with edges previously added, stopping after adding V-1 edges have been taken.

# help class to do the union and cycle detection
class union_find:
    def __init__(self, graph):
        self.id = [i for i in range(len(graph))]

    def find(self, e):
        while e != self.id[e]:
            e = self.id[e]
        return e

    def connect(self, u, v):
        return self.find(u) == self.find(v)
        
    def union(self, u, v):
        u_root = self.find(u)
        v_root = self.find(v)
        self.id[u_root] = v_root

# graph is adjacency matrix representation
def kruskal(graph):
    edges = []
    MST = []
    uf = union_find(graph)
    for i in range(len(graph)):
        for j in range(i+1, len(graph[i])):
            if graph[i][j]:
                edges.append([i, j, graph[i][j]])
    for e in sorted(edges, key=lambda x: x[2]):
        if len(MST) != len(graph)-1:
            if not uf.connect(e[0], e[1]):
                MST.append(e)
                uf.union(e[0], e[1])
        else:
            break
    return MST

Shortest Path

Dijkstra’s algorithm
It’s analogous to Prim’s algorithm, we begin by initializing distTo[s] to 0 and all other distTo[] entries to positive infinity, then we relax and add to the tree a non-tree vertex with the lowest distTo[] value, continuing until all vertices are on the tree or no non-tree vertex has a finite distTo value.

# graph is adjacency matrix representation, indicating no connection with value "inf"
def dijkstra(graph, start_vertex):
    edge_to = [None]*len(graph)
    dist_to = [float('inf')]*len(graph)
    queue = []
    dist_to[start_vertex] = 0
    queue.append([start_vertex, 0])
    while queue:
        queue = sorted(queue, key=lambda x: x[1])
        v = queue.pop(0)
        for w in range(len(graph[v[0]])):
            if graph[v[0]][w] != float('inf') and \
            dist_to[w] > dist_to[v[0]] + graph[v[0]][w]: # find a shorter path from v[0] to w
                dist_to[w] = dist_to[v[0]] + graph[v[0]][w] # update
                edge_to[w] = [v[0], w]
                for i in range(len(queue)):
                    if queue[i][0] == w:
                        del queue[i]
                queue.append([w, dist_to[w]])
    return edge_to