The Greedy Approach

Dijkstra’s Algorithm

We define λ[y]\lambda [y] as the shortest known distance from the source vertex (vertex 1) to vertex yy. Initially, λ[y]\lambda [y] is set to the weight of the edge connecting vertex 1 to vertex yy if such an edge exists. If no such edge exists, λ[y]\lambda [y] is set to infinity (∞\infty), indicating that vertex yy is not yet reachable from the source.

\begin{algorithm}
\caption{DIJKSTRA}
\begin{algorithmic}
\Input A weight directed graph $G = (V,E)$, where $V = \{ 1,2,\dots ,n \}$.
\Output The distance from vertex 1 to every other vertex in $G$.
\State $X = \{ 1 \}; \quad Y \gets V - \{ 1 \}; \quad \lambda [1] \gets 0$
\For{$y \gets 2$ \To $n$}
	\If{$y$ is adjacent to $1$ then $\lambda[y] \gets length[1,y]$}
    \Else
        \State $\lambda [y] \gets \infty$
    \EndIf
\EndFor
\For{$j \gets 1$ \To $n - 1$}
    \State Let $y \in Y$ be such that $\lambda[y]$ is minimum
    \State $X \gets X \cup \{y\}$ \Comment{add vertex $y$ to $X$}
    \State $Y \gets Y - \{y\}$ \Comment{delete vertex $y$ from $Y$}
    \For{each edge $(y, w)$}
        \If{$w \in Y$ and $\lambda[y] + length[y, w] < \lambda[w]$}
            \State $\lambda[w] \gets \lambda[y] + length[y, w]$
        \EndIf
    \EndFor
\EndFor
\end{algorithmic}
\end{algorithm}
An example of Dijkstra’s algorithm.

In the figure , those vertices to the left of the dashed line belong to XX, and the others belong to YY.
The time complexity of Dijkstra’s algorithm is Θ(n2)\Theta (n^2).
Below is the implementation of the pseudocode in Python(Adjacency matrix):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def Dijkstra(length):
    n = len(length)
    X = [0]
    Y = [i for i in range(1,n)]
    Lambda = [0 for i in range(0,n)]

    for y in range(1,n):
        if length[0][y]:
            Lambda[y] = length[0][y]
        else:
            Lambda[y] = float("inf")
        
    for j in range(0, n-1):
        min_value = float("inf")
        y_min = -1
        
        # Linear scan through Y to find vertex with smallest distance estimate
        for vertex in Y:
            if Lambda[vertex] < min_value:
                min_value = Lambda[vertex]
                y_min = vertex

        # If no valid vertex found, remaining vertices are unreachable
        if y_min == -1:
            break

        X.append(y_min)
        Y.remove(y_min)

        for w in range(n):
            if w in Y and length[y_min][w] != 0:
                if Lambda[y_min] + length[y_min][w] < Lambda[w]:
                    Lambda[w] = Lambda[y_min] + length[y_min][w]
    
    return Lambda

Minimum Cost Spanning Trees

Let G=(V,E)G = (V, E) be a connected undirected graph with weights on its edges. A spanning tree (V,T)(V, T) of GG is a subgraph of GG that is a tree. If GG is weighted and the sum of the weights of the edges in TT is minimum, then (V,T)(V, T) is called a minimum cost spanning tree or simply a minimum spanning tree.

Kruskal’s Algorithm

An example of Kruskal's Algorithm. 
\begin{algorithm}
\caption{KRUSKAL}
\begin{algorithmic}
\Input A weighted connected undirected graph $G = (V,E)$ with $n$ vertices.
\Output The set of edges $T$ of a minimum cost spanning tree for $G$.
\State Sort the edges in $E$ by nondecreasing weight.
\For{each vertex $v \in V$}
    \State \Call{makeset}{$\{v\}$}
\EndFor
\State $T \gets \{\}$
\While{$|T| < n - 1$}
    \State Let $(x, y)$ be the next edge in $E$.
    \If{\Call{find}{$x$} $\neq$ \Call{find}{$y$}}
        \State \Call{add}{$x, y$} to $T$
        \State \Call{union}{$x, y$}
    \EndIf
\EndWhile
\end{algorithmic}
\end{algorithm}

Prim’s Algorithm

An example of Prim's Algorithm. 
\begin{algorithm}
\caption{PRIM}
\begin{algorithmic}
\Input A weighted connected undirected graph $G = (V, E)$, where $V = \{1, 2, \dots, n\}$.
\Output The set of edges $T$ of a minimum cost spanning tree for $G$.
\State $T \gets \{\}; \quad X \gets \{1\}; \quad Y \gets V - \{1\}$
\For{$y \gets 2$ \To $n$}
    \If{$y$ is adjacent to $1$}
        \State $N[y] \gets 1$
        \State $C[y] \gets c[1, y]$
    \Else
        \State $C[y] \gets \infty$
    \EndIf
\EndFor
\For{$j \gets 1$ \To $n - 1$} \Comment{find $n - 1$ edges}
    \State Let $y \in Y$ be such that $C[y]$ is minimum
    \State $T \gets T \cup \{(y, N[y])\}$ \Comment{add edge $(y, N[y])$ to $T$}
    \State $X \gets X \cup \{y\}$ \Comment{add vertex $y$ to $X$}
    \State $Y \gets Y - \{y\}$ \Comment{delete vertex $y$ from $Y$}
    \For{each vertex $w \in Y$ that is adjacent to $y$}
        \If{$c[y, w] < C[w]$}
            \State $N[w] \gets y$
            \State $C[w] \gets c[y, w]$
        \EndIf
    \EndFor
\EndFor
\end{algorithmic}
\end{algorithm}

Huffman tree

\begin{algorithm}
\caption{HUFFMAN}
\begin{algorithmic}
\Input A set $C = \{c_1, c_2, \dots, c_n\}$ of $n$ characters and their frequencies $\{f(c_1), f(c_2), \dots, f(c_n)\}$.
\Output A Huffman tree $(V, T)$ for $C$.
\State Insert all characters into a min-heap $H$ according to their frequencies.
\State $V \gets C; \quad T \gets \{\}$
\For{$j \gets 1$ \To $n - 1$}
    \State $c \gets $\Call{deletemin}{H}
    \State $c' \gets $\Call{deletemin}{H}
    \State $f(v) \gets f(c) + f(c')$ \Comment{$v$ is a new node}
    \State \Call{insert}{$H, v$}
    \State $V \gets V \cup \{v\}$ \Comment{Add $v$ to $V$}
    \State $T \gets T \cup \{(v, c), (v, c')\}$ \Comment{Make $c$ and $c'$ children of $v$ in $T$}
\EndFor
\end{algorithmic}
\end{algorithm}

The time complexity of the algorithm is O(nlog⁡n)O(n \log n).

Graph Traversal

\begin{algorithm}
\caption{DFS}
\begin{algorithmic}
\Input A (directed or undirected) graph $G = (V, E)$.
\Output Preordering and postordering of the vertices in the corresponding depth-first search tree.
\State $predfn \gets 0; \quad postdfn \gets 0$
\For{each vertex $v \in V$}
    \State mark $v$ unvisited
\EndFor
\For{each vertex $v \in V$}
    \If{$v$ is marked unvisited}
        \State \Call{dfs}{$v$}
    \EndIf
\EndFor
\Procedure{dfs}{$v$}
    \State mark $v$ visited
    \State $predfn \gets predfn + 1$
    \For{each edge $(v, w) \in E$}
        \If{$w$ is marked unvisited}
            \State \Call{dfs}{$w$}
        \EndIf
    \EndFor
    \State $postdfn \gets postdfn + 1$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{BFS}
\begin{algorithmic}
\Input A (directed or undirected) graph $G = (V, E)$.
\Output Numbering of the vertices in breadth-first search order.
\State $bfn \gets 0$
\For{each vertex $v \in V$}
    \State mark $v$ unvisited
\EndFor
\For{each vertex $v \in V$}
    \If{$v$ is marked unvisited}
        \State \Call{bfs}{$v$}
    \EndIf
\EndFor
\Procedure{bfs}{$v$}
    \State $Q \gets \{v\}$
    \State mark $v$ visited
    \While{$Q \neq \{\}$}
        \State $v \gets$ \Call{Pop}{$Q$}
        \State $bfn \gets bfn + 1$
        \For{each edge $(v, w) \in E$}
            \If{$w$ is marked unvisited}
                \State \Call{Push}{$w, Q$}
                \State mark $w$ visited
            \EndIf
        \EndFor
    \EndWhile
\EndProcedure
\end{algorithmic}
\end{algorithm}

Finding Articulation Points in a Graph

A vertex vv in an undirected graph GG with more than two vertices is called an articulation point if there exist two vertices uu and ww different from vv such that any path between uu and ww must pass through vv. Thus, if GG is connected, the removal of vv and its incident edges will result in a disconnected subgraph of GG. A graph is called biconnected if it is connected and has no articulation points.
To find the set of articulation points, we perform a depth-first search traversal on GG. During the traversal, we maintain two labels with each vertex v∈Vv \in V: α[v]\alpha[v] and β[v]\beta[v]. α[v]\alpha[v] is simply predfn in the depth-first search algorithm, which is incremented at each call to the depth-first search procedure. β[v]\beta[v] is initialized to α[v]\alpha[v], but may change later on during the traversal. For each vertex vv visited, we let β[v]\beta[v] be the minimum of the following:

  • α[v]\alpha[v].
  • α[u]\alpha[u] for each vertex uu such that (v,u)(v, u) is a back edge.
  • β[w]\beta[w] for each edge (v,w)(v, w) in the depth-first search tree.
    The articulation points are determined as follows:
  • The root is an articulation point if and only if it has two or more children in the depth-first search tree.
  • A vertex vv other than the root is an articulation point if and only if vv has a child ww with β[w]≥α[v]\beta[w] \geq \alpha[v].
    The formal algorithm for finding the articulation points is given as Algorithm ARTICPOINTS.
\begin{algorithm}
\caption{ARTICPOINTS}
\begin{algorithmic}
\Input A connected undirected graph $G = (V, E)$.
\Output Array $A[1..count]$ containing the articulation points of $G$, if any.
\State Let $s$ be the start vertex.
\For{each vertex $v \in V$}
    \State mark $v$ unvisited
\EndFor
\State $predfn \gets 0; \quad count \gets 0; \quad rootdegree \gets 0$
\State \Call{dfs}{$s$}
\Procedure{dfs}{$v$}
    \State mark $v$ visited; $artpoint \gets \textbf{false}$; $predfn \gets predfn + 1$
    \State $\alpha[v] \gets predfn; \quad \beta[v] \gets predfn$ \Comment{Initialize $\alpha[v]$ and $\beta[v]$}
    \For{each edge $(v, w) \in E$}
        \If{$(v, w)$ is a tree edge}
            \State \Call{dfs}{$w$}
            \If{$v = s$}
                \State $rootdegree \gets rootdegree + 1$
                \If{$rootdegree = 2$}
                    \State $artpoint \gets \textbf{true}$
                \EndIf
            \Else
                \State $\beta[v] \gets \min\{\beta[v], \beta[w]\}$
                \If{$\beta[w] \geq \alpha[v]$}
                    \State $artpoint \gets \textbf{true}$
                \EndIf
            \EndIf
        \ElsIf{$(v, w)$ is a back edge}
            \State $\beta[v] \gets \min\{\beta[v], \alpha[w]\}$
        \Else
            \State \textbf{do nothing} \Comment{$w$ is the parent of $v$}
        \EndIf
    \EndFor
    \If{$artpoint$}
        \State $count \gets count + 1$
        \State $A[count] \gets v$
    \EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}
An example of finding the articulation points in a graph.

We illustrate the action of Algorithm ARTICPOINTS by finding the articulation points of the graph shown in the figure. See the figure. Each vertex vv in the depth-first search tree is labeled with α[v]\alpha[v] and β[v]\beta[v]. The depth-first search starts at vertex aa and proceeds to vertex ee. A back edge (e,c)(e, c) is discovered, and hence β[e]\beta[e] is assigned the value α[c]=3\alpha[c] = 3. Now, when the search backs up to vertex dd, β[d]\beta[d] is assigned β[e]=3\beta[e] = 3. Similarly, when the search backs up to vertex cc, its label β[c]\beta[c] is assigned the value β[d]=3\beta[d] = 3. Now, since β[d]≥α[c]\beta[d] \geq \alpha[c], vertex cc is marked as an articulation point. When the search backs up to bb, it is also found that β[c]≥α[b]\beta[c] \geq \alpha[b], and hence bb is also marked as an articulation point. At vertex bb, the search branches to a new vertex ff and proceeds, as illustrated in the figure, until it reaches vertex jj. The back edge (j,h)(j, h) is detected and hence β[j]\beta[j] is set to α[h]=8\alpha[h] = 8. Now, as described before, the search backs up to ii and then hh and sets β[i]\beta[i] and β[h]\beta[h] to β[j]=8\beta[j] = 8. Again, since β[i]≥α[h]\beta[i] \geq \alpha[h], vertex hh is marked as an articulation point. For the same reason, vertex gg is marked as an articulation point. At vertex gg, the back edge (g,a)(g, a) is detected, and hence β[g]\beta[g] is set to α[a]=1\alpha[a] = 1. Finally, β[f]\beta[f] and then β[b]\beta[b] are set to 11 and the search terminates at the start vertex. The root aa is not an articulation point since it has only one child in the depth-first search tree.
Below is the implementation of the pseudocode in Python(Adjacency list):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
graph = {
    'a': ['b','g'],
    'b': ['a','c','f'],
    'c': ['b','d','e'],
    'd': ['c','e'],
    'e': ['c','d'],
    'f': ['b','g'],
    'g': ['a','f','h'],
    'h': ['g','i','j'],
    'i': ['h','j'],
    'j': ['h','i']
}

V = list(graph.keys())

is_visit = {v: False for v in V}

predfn = 0
count = 0
rootdegree = 0

alpha = {v: 0 for v in V}
beta = {v: 0 for v in V}

# 节点的父节点，判断是否为“回边”
parent = {v: None for v in V}

root = V[0]  # 转换为列表再取第一个元素

A = []

def dfs(v):
    global predfn,count, rootdegree
    is_visit[v] = True
    artpoint = False
    predfn = predfn + 1

    alpha[v] = predfn
    beta[v] = predfn

    for w in graph[v]:
        if not is_visit[w]:
            # 标注为树边
            parent[w] = v
            dfs(w)

            if v == root:
                rootdegree += 1
                if rootdegree == 2:
                    artpoint = True
            else:
                beta[v] = min(beta[v],beta[w])
                if beta[w] >= alpha[v]:
                    artpoint = True
        
        elif w != parent[v] and is_visit[w]:
            beta[v] = min(beta[v],alpha[w])

        else:
            pass # do nothing
        

    if artpoint:
        count += 1
        A.append(v)

dfs(root)
print(A)