Yanniyanni

图

2020-12-17 上次更新时间：4/29/2022, 9:34:08 AM 0

# 图的分类

# 存储结构

  • 邻接矩阵（Adjacency Matrix）: 用两个数组表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
  • 邻接表（Adjacency List）：将数组与链表相结合的存储方法。一个一维数组存储图中顶点信息，每个顶点和所有邻接点构成一个线性表(单链表)。
    • 有向图邻接表优化：十字链表（Orthogonal List），邻接表和逆邻接表结合。
    • 无向图邻接表优化：邻接多重表，把边的两个顶点存放在边表结点中，所有依附于同一个顶点的边串联在同一链表中，由于每条边依附于两个顶点，则每个边表结点同时链接在两个表中。
  • 边集数组：由两个一维数组组成。一个是存储顶点信息，另一个存储边信息。边数组每个数据元素由一条边的起点下标，终点下标和权重组成。

# 图的实现

# 抽象数据类型定义

  • ADT 图（Grapth）
    • Data
      • 顶点的有穷且非空集合和边的集合。
    • Operation
      • Create(*G, V, VR): 按照顶点集 V 和边弧集 VR 的定义构造图 G。
      • Destroy(*G): 若图 G 存在，则销毁它。
      • LocateVex(G, u): 若图 G 存在顶点 u，则返回图中位置。
      • GetVex(G, v): 返回图 G 中顶点 v 的值。
      • PutVex(G, v, value): 将图 G 中顶点 v 赋值 value。
      • FirstAdjVex(G, *v): 返回顶点 v 的邻接顶点，无则返回空。
      • NextAdjVex(G, v, *w): 返回顶点 v 相对顶点 w 的下一个邻接顶点，若 w 是 v 的最后一个邻接点，则返回空。
      • InserVex(*G, v): 新增顶点 v。
      • DeleteVex(*G, v): 删除顶点 v，及其相关的弧。
      • InsertArc(*G, v, w): 增添弧[v, w],若 G 是无向图，还需要增添对称弧 [w, v]。
      • DeleteArc(*G, v, w): 删除弧[v, w],若 G 是无向图，还需要删除对称弧 [w, v]。
      • DFSTraverse(G): 对图 G 进行深度遍历，在遍历过程对每个顶点调用。
      • HFSTraverse(G): 对图 G 进行广遍历，在遍历过程对每个顶点调用。
  • endADT
function Graph(v) { 
    this.vertices = v; 
    this.edges = 0; 
    this.adj = []; 
    for (var i = 0; i < this.vertices; ++i) { 
        this.adj[i] = []; 
        // this.adj[i].push(""); 
    }
    this.addEdge = addEdge; 
    this.showGraph = showGraph;
    this.dfs = dfs;
    // 以下是关于遍历有关
    this.marked = []; // 是否已访问过标识
    for (var i = 0; i < this.vertices; ++i) { 
        this.marked[i] = false; 
    }
    this.bfs = bfs;
    this.edgeTo = [];
    this.pathTo = pathTo;
    this.hasPathTo = hasPathTo;
    this.topSort = topSort;
    this.topSortHelper = topSortHelper;
}
function addEdge(v, w) { 
    this.adj[v].push(w); 
    this.adj[w].push(v); 
    this.edges++; 
}
function showGraph() { 
    for (var i = 0; i < this.vertices; ++i) {
        let tmpStr = i + " -> ";
        for (var j = 0; j < this.vertices; ++j ) {
            if (this.adj[i][j] != undefined) {
                tmpStr = tmpStr + this.adj[i][j] + '  '
            }
        }
        console.log(tmpStr); 
    } 
}
// 创建一个具有5个顶点的图
var g = new Graph(5); 
// 给顶点们创建边
g.addEdge(0,1); 
g.addEdge(0,2); 
g.addEdge(1,3); 
g.addEdge(2,4); 
g.showGraph();
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

g 是一个这样的图。

# 图的遍历

图的遍历（Traversing Grapth）：从图中某一顶点触发访遍图中其余顶点，且使每一个顶点仅被访问一次。

# 深度优先遍历

function dfs(v) { 
    this.marked[v] = true; 
    if (this.adj[v] != undefined) {
        console.log("Visited vertex: " + v); 
    }
    for(var i in this.adj[v]) { 
        var w = this.adj[v][i];
        if (!this.marked[w]) { 
            this.dfs(w); 
        }
    } 
}
g.dfs(0); // 0 1 3 2 4
1
2
3
4
5
6
7
8
9
10
11
12
13

# 广度优先遍历

function bfs(s) {
    var queue = []; 
    this.marked[s] = true; 
    queue.push(s); // 添加到队尾 
    while (queue.length > 0) {
        var v = queue.shift(); // 从队首移除 
        if (v !== undefined) {
            console.log("Visisted vertex: " + v); 
        }
        for(var i in this.adj[v]) { 
            var w = this.adj[v][i];
            if (!this.marked[w]) { 
                this.edgeTo[w] = v; 
                this.marked[w] = true; 
                queue.push(w); 
            } 
        } 
    } 
}
g.bfs(1); // 0 1 2 3 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 查找最短路径

查找最短路径: 查找两个顶点间经过的边上权值之和最少的路径。

function pathTo (s, v){
    var source = s; 
    if (!this.hasPathTo(v)) { 
        return undefined; 
    }
    var path = []; 
    for (var i = v; i != source; i = this.edgeTo[i]) { 
        path.push(i); 
    }
    path.push(s); 
    return path;
}
function hasPathTo (v){
    return this.marked[v];
}
// 使用最短路径搜索之前必须使用同一个source对图进行遍历！！！
g.bfs(3);
console.log(g.pathTo(3,2)); // [2, 0, 1, 3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 拓扑排序

拓扑排序：对一个有向图构造拓扑序列的过程。（对有向图的所有顶点进行排序，使有向边从前面的顶点指向后面的顶点。）

function topSort(){
    var r = [],
        visited = [];
    for (var i = 0; i < this.vNum; i++){
        visited[i] = false;
    }
    for (i = 0; i < this.vNum; i++){
        if (visited[i] === false){
            this.topSortHelper(i, visited, r);
        }
    }
    while(r.length > 0){
        var v = r.pop();
        console.log(v);
    }
}
function topSortHelper(v, visited, r){
    visited[v] = true;
    for (var j in this.adj[v]){
        var w = this.adj[v][j];
        if (!visited[w]){
            this.topSortHelper(w,visited,r);
        }
    }
    r.push(v);
}

var h = new Graph(5);
h.addEdge(0,1); 
h.addEdge(0,2); 
h.addEdge(1,3); 
h.addEdge(2,4); 
h.topSort(); // 0 2 4 1 3
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

# 完整示例

function Graph(v) { 
    this.vertices = v; 
    this.edges = 0; 
    this.adj = []; 
    for (var i = 0; i < this.vertices; ++i) { 
        this.adj[i] = []; 
        // this.adj[i].push(""); 
    }
    this.addEdge = addEdge; 
    this.showGraph = showGraph;
    this.dfs = dfs;
    // 以下是关于遍历有关
    this.marked = []; // 是否已访问过标识
    for (var i = 0; i < this.vertices; ++i) { 
        this.marked[i] = false; 
    }
    this.bfs = bfs;
    this.edgeTo = [];
    this.pathTo = pathTo;
    this.hasPathTo = hasPathTo;
    this.topSort = topSort;
    this.topSortHelper = topSortHelper;
}
function addEdge(v, w) { 
    this.adj[v].push(w); 
    this.adj[w].push(v); 
    this.edges++; 
}
function showGraph() { 
    for (var i = 0; i < this.vertices; ++i) {
        let tmpStr = i + " -> ";
        for (var j = 0; j < this.vertices; ++j ) {
            if (this.adj[i][j] != undefined) {
                tmpStr = tmpStr + this.adj[i][j] + '  '
            }
        }
        console.log(tmpStr); 
    } 
}
function dfs(v) { 
    this.marked[v] = true; 
    if (this.adj[v] != undefined) {
        console.log("Visited vertex: " + v); 
    }
    for(var i in this.adj[v]) { 
        var w = this.adj[v][i];
        if (!this.marked[w]) { 
            this.dfs(w); 
        }
    } 
}
function bfs(s) {
    var queue = []; 
    this.marked[s] = true; 
    queue.push(s); // 添加到队尾 
    while (queue.length > 0) {
        var v = queue.shift(); // 从队首移除 
        if (v !== undefined) {
            console.log("Visisted vertex: " + v); 
        }
        for(var i in this.adj[v]) { 
            var w = this.adj[v][i];
            if (!this.marked[w]) { 
                this.edgeTo[w] = v; 
                this.marked[w] = true; 
                queue.push(w); 
            } 
        } 
    } 
}
function pathTo (s, v){
    var source = s; 
    if (!this.hasPathTo(v)) { 
        return undefined; 
    }
    var path = []; 
    for (var i = v; i != source; i = this.edgeTo[i]) { 
        path.push(i); 
    }
    path.push(s); 
    return path;
}
function hasPathTo (v){
    return this.marked[v];
}
function topSort(){
    var r = [],
        visited = [];
    for (var i = 0; i < this.vertices; i++){
        visited[i] = false;
    }
    for (i = 0; i < this.vertices; i++){
        if (visited[i] === false){
            this.topSortHelper(i, visited, r);
        }
    }
    //print
    while(r.length > 0){
        var v = r.pop();
        console.log(v);
    }
}

function topSortHelper(v, visited, r){
    visited[v] = true;
    for (var j in this.adj[v]){
        var w = this.adj[v][j];
        if (!visited[w]){
            this.topSortHelper(w,visited,r);
        }
    }
    r.push(v);
}

// 创建一个具有5个顶点的图
var g = new Graph(5); 
// 给顶点们创建边
g.addEdge(0,1); 
g.addEdge(0,2); 
g.addEdge(1,3); 
g.addEdge(2,3); 
g.addEdge(2,4); 
g.showGraph();

// 深度遍历
g.dfs(0); // 0 1 3 2 4
// 广度遍历
g.bfs(0); // 0 1 2 3 4

// 使用最短路径搜索之前必须使用同一个source对图进行遍历！！！
g.bfs(3);
console.log(g.pathTo(3,2)); // [2, 0, 1, 3]

// 拓扑排序
var h = new Graph(5);
h.addEdge(0,1); 
h.addEdge(0,2); 
h.addEdge(1,3); 
h.addEdge(2,4); 
h.topSort(); // 0 2 4 1 3
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
133
134
135
136
137
138
139
140

# 图的应用

  • 交通系统之类的
上次更新时间: 4/29/2022, 9:34:08 AM

←