# 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$$

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

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

##### 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

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; } } 

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

The graph is represented by an array or vector v,v,…,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

##### 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

##### 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

#### 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:

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 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)$

##### 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 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 template 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 Graph::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 void Graph::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 std::size_t Graph::size() const { return _size; } template T &Graph::operator[](std::size_t index) { return _data[index]; } template std::size_t *Graph::getOutDegree(std::size_t index) { return matrix[index]; } template Graph::~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 void DFS(Graph &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 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 void BFS(Graph &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 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 == height and data.shape == 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, matrix.shape, 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$

1. 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$