Data Structure

Graph

Definition: A graph G consists of two sets

a finite, nonempty set of vertices V(G)

a finite, possible empty set of edges E(G)

G(V,E) represents a graph

The number of vertices is written $|V|(n)$, and the number of edges is written $|E|(e)$

General graphs differ from trees

1. need not have a root node
2. no implicit parent-child relationship
3. may be several (or no) paths from one vertex to another

Definition

For a Directed graph

$if\ u, v\ are\ two\ vertices,then\ <u, v> is\ an\ arc(edge), u\ is\ called\ as\ tail, v\ is\ called\ head$

$Example:$

$[u]\rightarrow[v]\ is\ called <u, v>, and\ [v]\rightarrow[u] is\ called <v, u>$

$$ [u]\rightarrow[v] $$

$$ [v]\rightarrow[u] $$

A directed graph is one in which each edge is a directed pair of vertices, $< u,v > \neq < v,u >$

For an undirected graph

An undirected graph is one in which the pair of vertices in an edge is unordered, $（u,v）= （v,u）$ $$ (u, v)=(v, u) $$

Complete graph

A complete graph is a graph that has the $maximum\ number\ of\ edges$; A complete graph is a graph in which $there\ is\ an\ edge\ between\ every\ pair\ of\ vertices$.

for a $undirected\ graph$ with $n\ vertices$, the maximum number of edges is $\frac {n(n-1)}{2}(C_n^2)$

for a $directed\ graph$ with n vertices, the maximum number of edges is $n(n-1)$

Sparse Graph and Dense Graph

If the edges of a graph is $e<n\log n$, the graph is called Sparse Graph ,otherwise, it is called as Dense Graph

Examples for Graph

Undirected graph

$$ V(G_1)={0,1,2,3}\ and\ E(G_1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)} $$

$$ Graph \rightarrow G_1 $$

Directed graph

$$ V(G_2)={0,1,2}\ and\ E(G_2)={<0, 1>,<1, 0>,<1, 2>} $$

$$ Graph\rightarrow G_2 $$

Adjacent and Incident

If $(v_0 ,v_1 )$ is an edge in an $undirected\ graph$

$v_0$ and $v_1$ are $adjacent$

The edge $(v_0 , v_1)$ is $incident$ on vertices $v_0\ and\ v_1$

If $<v_0 , v_1>$ is an edge in a $directed\ graph$

$v_0$ is $adjacent\ to$ $v_1$ , and $v_1$ is $adjacent\ from$ $v_0$ .

The edge $<v_0 , v_1>$ is $incident$ on $v_0$ and $v_1$

Weighted graph(network)

There is some cost or weight associated with each edge

Subgraph

A subgraph of $G$ is a graph $G’$ such that $V(G’)$ is a subset of $V(G)$ and $E(G’)$ is a subset of $E(G)$ $$ V(G)\supseteq V(G’) $$

$$ E(G)\supseteq E(G’) $$

Degree

The degree of a vertex (TD: Total Degree) is the number of edges incident to that vertex

In-degree and Out-degree(for a directed graph)

The in-degree of a vertex v (ID) is the number of edges that have v as the head

The out-degree of a vertex v (OD) is the number of edges that have v as the tail

Conclusion:

if $d_i$ is the degree of a vertex $i$ in a graph $G$ with $n$ vertices and $e$ edges, the number of edges is $$ e=\frac{\sum_{i=1}^n d_i}{2} $$

Examples for degree

directed graph:

$$ 0\rightarrow in=1\ and\ out=1 $$

$$ 1\rightarrow in=1\ and\ out=2 $$

$$ 2\rightarrow in=1\ and\ out=0 $$

Undirected graph:

$$ 0\rightarrow 2 $$

$$ [1,2]\rightarrow 3 $$

$$ [3, 4, 5, 6] \rightarrow 1 $$

Path

Definition

$A\ path\ from\ vertex\ v_p\ to\ v_q\ in\ a\ graph\ G\ is\ a\ sequence\ of\ vertices,$

$\rightarrow v_p , v_{i_1} , v_{i_2} , …, v_{i_n}, v_{q}\ such\ that (v_p , v_{i_1}), (v_{i_1} ,v_{i_2} ), …, (v_{i_n}, v_q) are\ edges\ in\ a\ graph$

Length of a path

The length of a path is the number of edges on it

Simple path

A simple path is a path in which all vertices are distinct

Simple Circle

A simple cycle is a path in which all vertices,except the first and the last, are distinct. The first and the last vertices are the same

Example of Graph

Traffic flow can be modeled by a graph

Each street intersection represents a vertex, each street is an edge

Edge costs could represent, among other things, a speed limit or capacity

We could ask for the shortest route or use this information to find the most likely location for bottleneck

ADT

Graph

1
2
3
4
5
6
7
8
9

Objects: a nonempty set of vertices and a set of edges

Functions: for all graph in Graph, v, v1 and v2 in Vertices

Graph Create(): return an empty graph

Graph DeleteEdge(graph, v1, v2): return a graph in which the edge (v1, v2) is removed

......

Graph Implementation

Adjacency Matrix (Array)

Definition

The adjacency matrix of G is a two-dimensional n by n array, say $A[n] [n]$ $$ A[i][j]=\begin{cases} 1\ if\ <V_i,V_j> \in E\ or\ (V_i,V_j)\in E\newline 0\ otherwise \end{cases} $$

For a weighted graph

$$ A[i][j]=\begin{cases} W(i, j)\ when\ i\neq j\ and\ <V_i,V_j> \in E\ or\ (V_i,V_j)\in E\newline \infty\ otherwise \end{cases} $$

Example

For a graph

$$ \begin{pmatrix} 0& 1& 0\newline 1& 0& 1\newline 0& 0& 0 \end{pmatrix} $$

For a weight graph

The weight of the edge from vertex i to vertex j is used instead of 1 in the adjacency matrix $$ \begin{pmatrix} \infty& 1& \infty& 4\newline \infty& \infty& 9& 2\newline 3& 5& \infty& 8\newline \infty& \infty& 6& \infty \end{pmatrix} $$

Notice

The adjacency matrix for an undirected graph is symmetric

The adjacency matrix for a digraph need not be symmetric

Merits of Adjacency Matrix

From the adjacency matrix, to determine the connection of vertices is easy

For a undirected graph, the degree of a vertex i is $\sum_{j=1}^n A[i][j]$

For a directed graph

The sum of 1 in row i of the adjacency matrix is yields the out-degree of the $i^{th}$ vertex $$ \begin{bmatrix} a_1&a_2&a_3&\dots&a_n \end{bmatrix} $$ The sum of the entries in the $i^{th}$ column is its in degree $$ \begin{bmatrix} a_1\newline a_2\newline a_3\newline \vdots\newline a_n \end{bmatrix} $$

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

constexpr const int MaxVNum = 500;
typedef XXX VertexType;

typedef struct ArcCell {
    /*Type of vertex relationship. For unauthorized graph, use 1 or 0 to indicate adjacent no;
	*For weighted graphs, is the weight value
	*/
    VRType adj;
    InfoType *Info;//Pointer to the arc related information (may not be available)
} ArcCell, AdjMatrix[MaxVNum][MaxVNum];

typedef struct { 
    VertexType vexs[MaxVNum]; /* Vertex table */
	AdjMatrix arcs; /* The adjacency matrix, i.e. the edge table */
	int vexnum, arcnum; /* The number of vertices and edges in the graph */
} Mgraph; /* Mgraph is a graph stored in an adjacency matrix */

Create a graph

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

CreateGraph (Mgraph &ga) {
    int i, j, k; 
    float w;
	std::cin >> ga.vexnum >> ga.arcnum;
	for (i = 0; i < ga.vexnum; i++)
		ga->vexs[i] ＝ getchar(); /*Read into the vertex information and establish the vertex table*/
	for (i = 0; i < ga.vexnum; i++)
		for (j = 0; j < ga.vexnum; j++)
			ga->arcs[i][j] ＝ ∝; /*The Adjacency matrix is initialized*/
	for (k = 0; k < ga.arcnum; k++) {
        std::cin >> v1 >> v2 >> w; /*Read in the vertices and weights of an edge*/
		i = LocateVex(ga,v1); 
        j = LocateVex(ga,v2); 
		ga.arcs[i][j].adj ＝ w; 
        ga.arcs[j][i].adj ＝ w;
	}
}

Adjacency List

If a graph does not have many edges, the adjacency matrix will be sparse

such representation is a waste of space

use an array of pointers to linked row-lists

adjacency-list representation for graphs

Description of Adjacency List

Each row in adjacency matrix is represented as an adjacency list

The graph is represented by an array or vector v[1],v[2],…,v[n], one element for each vertex in the graph

Each v[i] stores the data stored in vertex i together with a linked list of the numbers of all vertices adjacent from vertex i

Example:

Merits and Demerits of Adjacency List

degree of a vertex in an undirected graph – # of nodes in adjacency list

out-degree of a vertex in a directed graph – # of nodes in its adjacency list

in-degree of a vertex in a directed graph – traverse the whole data structure

Inverse adjacency list

Linked table is entry edge

code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

constexpr const int MaxVerNum = 100; /*Maximum verx 100*/

/*Adjacent table edge junction type*/
typedef struct ArcNode { 
    int adjvex; /*Neighborhood domain*/
	InfoType *Info; /*Domain info, for edge information*/
	struct ArcNode * next; /*Pointer domain to the next neighbor*/
}ArcNode;

/*Table header node type*/
typedef struct Vnode { 
    VertexType vertex; /*Vertex Domains*/
	ArcNode *firstedge; /*Side table head pointer*/
}Vnode, AdjList [MaxVertexNum];

/*The type of figure*/
typedef struct { 
    AdjList vertices; /*adjacency list*/
	int vexnum, arcnum; /*Vertices and edges*/
} ALGraph;

Traversing Graph

Some applications require visiting every vertex in a graph exactly once.

The application may require that vertices should be visited in some special order based on graph topology

DFS: Depth-First Search

BFS: Breadth-First Search

Depth-First Search(DFS)

Basic idea

1. Start from a given vertex v and visit it.

2. Visit the first neighbor w of v. Then visit the first neighbor of w that has not already been visited, etc.

3. If a node with no unexamined neighbors, then backup to the last visited node and examine its remaining neighbors.

4. The search continues until all nodes of the graph have been examined.

Example

$$ \begin{bmatrix} V1 &V2 &V4 &V8 &V3 &V6 &V7 &V5 \end{bmatrix} $$

Algorithm

Difficulties：

1. How to determine whether v has been visited?

2. How to search the neighbor of v？

Solutions：

1. Using an array visited[n]. When i th vertex has been visited, visited[i]=TRUE.

2. Varying by different data structure:

• Adjacency Matrix

• Adjacency List

DFS uses backtracking. Recursion is a natural technique for such problems

a stack is automatically maintained to make backtracking possible

DFS

1. Visit the start vertex v.

2. For each vertex w adjacent to v do:

• If w has not been visited, apply the Depth-First Search (DFS) algorithm with w as the start vertex.

Code

 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

constexpr auto MAX{ 500 };
std::array<bool,MAX> visited{};

void DFSTraverse(Graph G) { 
    for (std::size_t k = 1; k <= G.vexnum; k++) 
        visited[k] = false;
	for (std::size_t k = 1; k <= G.vexnum; k++)
		if(!visited[ k ]) 
            DFS(G, k);
}

void DFS(Graph G, int v) { 
    visited[v] = TRUE; 
	VISIT(v); // access to the v_th vertex in graph G
	for(int w = FirstAdjVex(G,v); w > 0; w = NextAdjVex(G, v, w))
		if (!visited[w]) 
            DFS(G, w);
}

int FirstAdjVex(ALGraph G, int v) { 
    /*
    *returns the serial number of the first neighbor of the v th vertex in G. 
    *If v has no neighbors, it returns 0
    */
    return G.vertices[v].firstarc ? G.vertices[v].firstarc->adjvex : 0;
}

int NextAdjVex(ALGraph G, int v, int w) { 
    /*
    *returns the serial number of the next neighbor of the v th vertex in G relative to the vertex w.
    *Returns 0 if v has no next neighbor relative to the vertex w
    */
	ArcNode *p;
	p = G.vetrices[v].firstarc;
	while(p && p->adjvex != w) 
        p = p->nextarc;
	if (p->adjvex == w && p->nextarc) 
        return p->nextarc->adjvex;
	else 
        return 0;
}

Algorithm Analysis

Let G=(V,E) be a graph with n vertices and e edges

$Adjacency\ list:\ O(n+e)$

$Adjacency\ matrix:\ O(n^2)$

Bread-First Search(BFS)

Basic idea

1. Start from a given vertex v and visit it.

2. Visit all neighbors of v.

3. Then visit all neighbors of first neighbor w of v.

4. Then visit all neighbors of second neighbor x of v, etc

Example

$$ \begin{bmatrix} V1 &V2 &V3 &V4 &V6 &V7 &V8 &V5 \end{bmatrix} $$

Algorithm

BFS visits nodes level by level

While visiting each node on a given level

store it

so that, we can return to it after completing this level

so that nodes adjacent from it can be visited

Because the first node visited on a given level should be the first one to which we return, a queue is an appropriate data structure for storing the nodes

BFS

1. Visit the start vertex v.

2. Initialize a queue to contain only the start vertex.

3. While the queue is not empty do:

• Remove a vertex v from the queue.

• For all vertices w adjacent to v do:

– If w has not been visited then

i. Visit w. ii. Add w to the queue.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

void BFSTraverse(Graph G) { 
    for(int v = 1; v <= G.vexnum; v++) 
        visited[v] = false;
	InitQueue(Q);
	for(int v = 1; v <= G.vexnum; v++) {
		if ( !visited[v] ) { 
            visited[v] = true;
            VISIT(v);
            EnQueue(Q, v);
			while (!EmptyQueue(Q)) { 
                DeQueue(Q,u); 
				for(int w = FirstAdjVex(G, u); w>0; w = NextAdjVex(G, u, w))
					if(!visited[w]) { 
                        visited[w] = true; 
                        VISIT(w); 
                        EnQueue(Q, w); 
                    }
			} // end while
		} // end if
    }
}

Algorithm Analysis

Let G=(V,E) be a graph with n vertices and e edges

$Adjacency\ list:\ O(n+e)$

$Adjacency\ matrix:\ O(n^2)$

For adjacency matrix unweighted directed Graph in C++

$$ A[i][j]=\begin{cases} 1\ if\ <V_i,V_j> \in E\ or\ (V_i,V_j)\in E\newline 0\ otherwise \end{cases} $$

Graph

 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

#pragma once

#include <exception>

template<typename T>
class Graph {
protected:
    T *_data;
    std::size_t **matrix;
    std::size_t _size;
public:
    Graph() = delete;

    Graph(T data[], std::size_t size);

    void setConnect(std::size_t **args, std::size_t size);

    [[nodiscard]] std::size_t size() const;

    T &operator[](std::size_t index);

    std::size_t *getOutDegree(std::size_t index);

    ~Graph();
};

template<typename T>
Graph<T>::Graph(T *data, std::size_t size) :_data{new T[size]{}}, _size{size} {
    matrix = new std::size_t *[_size];
    for (std::size_t i = 0; i < _size; i++)
        matrix[i] = new std::size_t[_size]{};
    for (std::size_t i = 0; i < _size; i++)
        _data[i] = data[i];
}

template<typename T>
void Graph<T>::setConnect(std::size_t **args, std::size_t size) {
    if (size != _size) throw std::exception{};
    for (std::size_t i = 0; i < _size; i++)
        for (std::size_t j = 0; j < _size; j++)
            matrix[i][j] = args[i][j];
}

template<typename T>
std::size_t Graph<T>::size() const {
    return _size;
}

template<typename T>
T &Graph<T>::operator[](std::size_t index) {
    return _data[index];
}

template<typename T>
std::size_t *Graph<T>::getOutDegree(std::size_t index) {
    return matrix[index];
}

template<typename T>
Graph<T>::~Graph() {
    delete[] _data;
    for (std::size_t i = 0; i < _size; i++)
        delete[] matrix[i];
    delete[] matrix;
}

DFS

 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

template<typename T, typename VST>
void DFS(Graph<T> &graph, VST &visit, std::size_t index) {
    bool *statue = new bool[graph.size()];
    for (std::size_t i = 0; i < graph.size(); i++)
        statue[i] = false;

    std::stack<std::size_t> stack{};

    for (std::size_t i = index; i < graph.size(); i++) {
        if (!statue[i])
            stack.push(i);

        while (!stack.empty()) {
            std::size_t x = stack.top();
            stack.pop();

            if (!statue[x]) {
                visit(graph[x]);
                statue[x] = true;
                for (std::size_t j = 0; j < graph.size(); j++)
                    if (graph.getOutDegree(x)[j] != 0 && !statue[j])
                        stack.push(j);
            }
        }
    }

    for (std::size_t i = 0; i < index; i++) {
        if (!statue[i])
            stack.push(i);

        while (!stack.empty()) {
            std::size_t x = stack.top();
            stack.pop();

            if (!statue[x]) {
                visit(graph[x]);
                statue[x] = true;
                for (std::size_t j = 0; j < graph.size(); j++)
                    if (graph.getOutDegree(x)[j] != 0 && !statue[j])
                        stack.push(j);
            }
        }
    }

    delete[] statue;
}

BFS

 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

template<typename T, typename VST>
void BFS(Graph<T> &graph, VST &visit, std::size_t index) {
    bool *statue = new bool[graph.size()];
    for (std::size_t i = 0; i < graph.size(); i++)
        statue[i] = false;
    std::queue<std::size_t> queue{};

    for (std::size_t i = index; i < graph.size(); i++) {
        if (!statue[i])
            queue.push(i);

        while (!queue.empty()) {
            std::size_t x = queue.front();
            queue.pop();

            if (!statue[x]) {
                visit(graph[x]);
                statue[x] = true;
                for (std::size_t j = 0; j < graph.size(); j++)
                    if (graph.getOutDegree(x)[j] != 0 && !statue[j])
                        queue.push(j);
            }
        }
    }

    for (std::size_t i = 0; i < index; i++) {
        if (!statue[i])
            queue.push(i);

        while (!queue.empty()) {
            std::size_t x = queue.front();
            queue.pop();

            if (!statue[x]) {
                visit(graph[x]);
                statue[x] = true;
                for (std::size_t j = 0; j < graph.size(); j++)
                    if (graph.getOutDegree(x)[j] != 0 && !statue[j])
                        queue.push(j);
            }
        }
    }

    delete[] statue;
}

Connectivity

Definition

Connected

An undirected graph is connected if there is a path from every vertex to every other vertex

Strongly connected

A directed graph with this property is called strongly connected

Weakly connected

If a directed graph is not strongly connected, but the underlying graph(without direction to the arcs)is connected, then the graph is said to be weakly connected.

Minimal Cost Spanning Trees

Spanning Trees

Definition

A spanning tree is any tree that consists solely of edges in G and that includes all the vertices(Contains all the vertices in the graph, but only enough n-1 edges to form a tree)

$$ E(G):T(tree\ edges)+N(nontree\ edges)\newline T:set\ of\ edges\ used\ during\ search\newline N:set\ of\ remaining\ edges\newline $$ A spanning tree is a minimal connected subgraph, G’, of G such that V(G’)=V(G) and G’ is connected

Example

Possible spanning trees

DFS and BFS

Either DFS or BFS can be used to create a spanning tree

When DFS is used, the resulting spanning tree is known as a depth first spanning tree

When BFS is used, the resulting spanning tree is known as a breadth first spanning tree

Nontree edge

While adding a nontree edge into any spanning tree, this will create a cycle

Minimal Cost Spanning Trees

Definition

The cost of a spanning tree of a weighted undirected graph is the sum of the costs of the edges in the spanning tree

A Minimal Cost Spanning Tree (MST) is a spanning tree of least cost

Algorithm for Minimal Cost Spanning Tree

$Prim$

$Kruskal$

Prim algorithm

Let Graph $G = {V, E}$, the minimum cost spanning tree be $T={U, T_E }$ and $U=V, T_E\subseteq E\newline$.

$Initially\rightarrow U={u_0 }, T_E=\empty$

Adding edges and vertices to T one at a time

1. Select the least cost edge $(u,v)$ that $u\in U\ and\ v\notin U$. Adding $v\ to\ U\ and\ (u,v)\ to\ T_E$

2. It continues, until n-1 edges have been selected and U=V

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

The minimum cost spanning tree T = {U,TE};
U = {u0}; 
TE = {};
while (T contains fewer than n-1 edges) { 
    let (u,v) be a least cost edge such that u in U and v notin U
	if (there is no such edge ) 
        break;
	add v to U;
	add (u,v) to TE;
}
if (T contains fewer than n-1 edges)//fail
	printf(“No spanning tree\n”);

Kruskal algorithm

Build a Minimum cost Spanning Tree (MST) T by adding edges to T one at a time

Select the edges for inclusion in T in non-decreasing order of the cost

An edge is added to T if it does not form a cycle

Since G is connected and has $n > 0$ vertices, exactly n-1 edges will be selected

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

TE= {};

while ((T contains less than n-1 edges) && (E is not empty)) { 
    choose a least cost edge (v,w) from E;
	delete (v,w) from E;
	if ((v,w) does not create a cycle in T)
		add (v,w) to T
	else 
        discard (v,w);
}

if (T contains fewer than n-1 edges)//fail
	printf (“No spanning tree\n”);

Code

  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
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

import math

import matplotlib.pyplot as plt
import numpy as np


class Point:
    __dict__ = ['x', 'y']

    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y

    def __str__(self):
        return f"({self.x}, {self.y})"

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __hash__(self):
        return hash((self.x, self.y))


class Line:
    __dict__ = ['Point1', 'Point2', 'length']

    def __init__(self, Point1: Point, Point2: Point):
        self.Point1 = Point1
        self.Point2 = Point2
        self.length = (Point1.x - Point2.x) ** 2 + (Point1.y - Point2.y) ** 2

    def __str__(self):
        return f"[{self.Point1}, {self.Point2}, {self.length}]"

    def GetLength(self):
        return math.sqrt(self.length)


class Graph:
    __dict__ = ['length', 'height', 'data', 'node', 'lines']

    def __init__(self, length: int, height: int, data: np.ndarray):
        self.length = length
        self.height = height
        assert data.shape[0] == height and data.shape[1] == length
        self.data = data
        self.node = []
        self.lines = []

        for i in range(height):
            for j in range(length):
                if data[i][j] != 0:
                    self.node.append(Point(i, j))

        assert len(self.node) > 1

        for i in range(len(self.node)):
            for j in range(i, len(self.node)):
                if self.node[i] != self.node[j]:
                    self.lines.append(Line(self.node[i], self.node[j]))

        self.lines.sort(key=lambda lines: lines.length)
        for i in self.lines:
            print(i)

        print()


def find(parent, node):
    if parent[node] == node:
        return node
    parent[node] = find(parent, parent[node])
    return parent[node]


def kruskal(graph: Graph):
    distance = 0.0
    Orderliness = []
    parent = {node: node for node in graph.node}

    for i in graph.lines:
        root1 = find(parent, i.Point1)
        root2 = find(parent, i.Point2)
        if root1 == root2:
            continue
        parent[root1] = root2
        Orderliness.append(i)
        distance += i.GetLength()

    return Orderliness, distance


def Draw(graph: Graph, Lines: list):
    Maxlength = max(graph.length, graph.height)
    x = np.zeros(Maxlength)
    y = np.zeros(Maxlength)

    print(x, y)

    plt.plot(x, y)
    plt.grid(axis='both')

    k = []
    l = []
    for i in graph.node:
        k.append(i.x)
        l.append(i.y)

    plt.scatter(k, l, edgecolors='b')

    for i in Lines:
        plt.plot([i.Point1.x, i.Point2.x], [i.Point1.y, i.Point2.y])

    plt.show()


if __name__ == '__main__':
    matrix = np.array([[0, 0, 1, 0],
                       [1, 0, 0, 0],
                       [1, 0, 1, 1],
                       [1, 0, 0, 1]])

    graph = Graph(matrix.shape[1], matrix.shape[0], matrix)

    OrdLines, Distance = kruskal(graph)

    for i in OrdLines:
        print(i)

    print(f"The distance is {Distance}")

    Draw(graph, OrdLines)

Time Complexity Analysis

$Prim’s\ algorithm:O(n^2)\newline$

Regardless of the number of edges in the graph, it is suitable to find the minimum spanning tree of dense nets

$Kruskal’s\ algorithm:O(e\log e)\ (Merge\ Sort\ for\ edges)\newline$

Regardless of the number of vertices in the graph, it is suitable to find the minimum spanning tree of sparse nets

Application of Graph

Application of Directed Acyclic (Acycline) Graph

1. Topological Sort

2. Critical Path

Shortest-Path Algorithms

Topological Sort

Definition

An ordering of vertices in a Directed Acyclic Graph, such that if there is a path from $v_i$ to $v_j$ , then $v_j$ appears after $v_i$ in the ordering

Example

An advanced placement course in a college training program

Activity on Vertex(AOV)—Network

Vertices represent activity, and arcs represent directed graphs of priority relations between activities

Notice

Topological ordering is not possible if there is a cycle in the graph

A simple algorithm

steps

1. Compute the in-degree of all vertices from the adjacency information of the graph

2. Find any vertex with no incoming edges

3. Print this vertex, and remove it and its edges

4. Apply this strategy to the rest of the graph

Time Complexity Analysis

$O(n^2)$

code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

void Topsort (Graph G) { 
    int Counter;
	Vertex V, W;
    
	for(Counter = 0; Counter < NumVertex; counter++) {
        V = FindNewVertexOfInDegreeZero ();
        
        if (V == NotAVertex) {//exit a circle
            printf("Graph has a cycle");
			break;
        }
        
        TopNum [V] = Counter;//The order of print
        for (each W adjacent from V)
			Indegree[W]--;
    }
}

An improved algorithm

steps

1. Keep all the unassigned vertices of indegree 0 in a queue.

2. While queue is not empty

   • Remove a vertex in the queue.

   • Decrement the indegree of all adjacent vertices.

   • If the indegree of an adjacent vertex becomes 0, enqueue the vertex

3. The topological ordering is the order in which the vertices dequeue

Time Complexity Analysis

$O(n+e)\newline$

code

 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

void Topsort (Graph G) { 
    Queue Q;
	int Counter = 0;
	Vertex V, W;
	Q = CreateQueue (NumVertex);
	MakeEmpty (Q);
    
	for each vertex V {
		if (Indegree [V] == 0)
            Enqueue(V,Q);
        
        while(!IsEmpty(Q)) {
            V = Dequeue(Q);
            TopNum[V] = ++Counter;
            //The topological ordering is the order in which the vertices dequeue
            
            for each W adjacent from V
                if (--Indegree[W] == 0)
                    Enqueue(W,Q);
        }
    }
    
    if(Counter != NumBertex)
        printf("Graph has a cycle\n"); //fail
    DisposeQueue(Q);
}

Critical Path

AOE (Activity on Edge) Network

Vertex: Represents an event or a status

Edge: represents an activity. An edge (v, w) means that event v must be done before w may begin

Weight: Duration time of an activity

~There is only one vertex whose in-degree is 0, and only one vertex whose out-degree is 0

~No cycle

~This type of a graph could be (and frequently) used to model projects

Questions

What is the earliest completion time for the project?

$\rightarrow The\ longest\ path\newline$

Which activities can be delayed, and by how long, without affecting the minimum completion time?

$\rightarrow Not\ critical\ activities\newline$

Elements

e(i): earliest start time of $a_i\newline$

l(i): latest start time of $a_i$ (without affecting the minimum completion time)

e(i)=l(i): $a_i$ is a critical activity, all the activities on the critical path are critical activities

ve(j): the earliest occurring time of $v_j\newline$

vl(j): the latest occurring time of $v_j$ (without affecting the minimum completion time)

$$ V_j\stackrel{a_i}{\longrightarrow}V_k\newline $$

If $a_i$ is represented by $<j,k>$, its duration time is $dut(<j,k>)\newline$

then $e(i) = ve(j), l(i) = vl(k) - dut(<j,k>)\newline$

Calculate

1. $From\ ve(0)=0: ve(j) = max(ve(i) + dut(<i,j>))\newline$

2. $vl(n-1)=ve(n-1), from\ the\ last\ one:vl(i) = min(vl(j) - dut(<i,j>))\newline$

Time Complexity Analysis

Suppose there are n events and e activities in AOE

$The\ Time\ Complexity\ of\ whole\ algorithm\ is\ O(n+e)\newline$

Shortest Paths Problems

Input: A graph with weights or costs associated with each edge

Output: The list of edges forming the shortest path

Sample problems:

Find shortest path between two named vertices

Find shortest path from S to all other vertices——Single-Source Shortest Paths

Find shortest path between all pairs of vertices——All-Pairs Shortest Paths

Dijkstra idea

step

All vertexes are divided into 2 groups

S : the vertexes that have found the shortest path from $V_0$ to them

V-S=T: The vertexes that have not calculated the distances

Adding vertex in T to S in non-decreasing order of distances

The distances from $V_0$ to vertexes in S is not longer than the distances from $V_0$ to any vertexes in T

algorithm

For G(V,E) is expressed in Adjacency Matrix

1. Initially, $S={v_0}$; An array D[n] to store the distance and D[i] is the shortest distance from $v_0\ to\ v_i$

   If exist an edge $(v_0,v_i),D[i] = w(v_0 ,v_i)\newline$ If there is no such edge, then D[i]= +$\infty\newline$

2. Select the minimal D[j] from V-S, then vertex $v_j$ is the destination of the currently shortest path, and D[j] is the shortest distance

3. Adding $v_j$ to S,and for all vertexes $v_k\in V-S\newline$

$if\ D[j]+arcs[j][k]<D[k]\newline then\ D[k]=D[j]+arcs[j][k]\newline$

4. Repeat processing (2),(3), until all vertexes are added into S

code

 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

typedef int PathMatrix[MAX][MAX];
typedef int ShortPathTable[MAX];

void ShortestPath(MGraph G, int v0, PathMatrix &P, ShortPathTable &D) {
	for (int v = 0; v < G.vexnum; v++) {
		final[v] = false;
		D[v] = G.Edge[v0][v];
		for (int w = 0; w < G.vexnum; w++)
			P[v][w] = false;
		if (D[v] < ∞) {
			P[v][v0] = true;
			P[v][v] = true;
		}
	}
	D[v0] = 0; final[v0] = true;
	for (int i = 1; i < G.vexnum; i++) {
		min = ∞;
		for (int w = 0; w < G.vexnum; w++)
			if (!final[w])
				if (D[w] < min) {
					v = w;
					min = D[w];
				}
		final[v] = true;
		for (int w = 0; w < G.vexnum; w++)
			if (!final[w] && (min + G.Edge[v][w] < D[w])) {
				D[w] = min + G.Edge[v][w];
				for (int j = 0; j < G.vexnum; j++)
					P[w][j] = P[v][j];
				P[w][w] = true;
			}
	}
}

Time Complexity Analysis

For Dijkstra’s Algorithm, the Time complexity is $O(n^2)\newline$

For every vertex $u, v\in V, calculate\ d(u, v)\newline$

Time complexity is $O(n^3)\newline$