图
图的存储结构常见的有两种：邻接矩阵和邻接表。
邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。
本章用无向邻接表来创建图：
邻接表
首先创建一个 dictionary.js 创建字典存储邻接表：
function defaultToString(item) {
if (item === null) {
return 'NULL';
} if (item === undefined) {
return 'UNDEFINED';
} if (typeof item === 'string' || item instanceof String) {
return `${item}`;
}
return item.toString();
}
class ValuePair {
constructor(key, value) {
this.key = key;
this.value = value;
}
toString() {
return `[#${this.key}: ${this.value}]`;
}
}
export default class Dictionary {
constructor(toStrFn = defaultToString) {
this.toStrFn = toStrFn;
this.table = {};
}
set(key, value) {
if (key != null && value != null) {
const tableKey = this.toStrFn(key);
this.table[tableKey] = new ValuePair(key, value);
return true;
}
return false;
}
get(key) {
const valuePair = this.table[this.toStrFn(key)];
return valuePair == null ? undefined : valuePair.value;
}
hasKey(key) {
return this.table[this.toStrFn(key)] != null;
}
remove(key) {
if (this.hasKey(key)) {
delete this.table[this.toStrFn(key)];
return true;
}
return false;
}
values() {
return this.keyValues().map(valuePair => valuePair.value);
}
keys() {
return this.keyValues().map(valuePair => valuePair.key);
}
keyValues() {
return Object.values(this.table);
}
forEach(callbackFn) {
const valuePairs = this.keyValues();
for (let i = 0; i < valuePairs.length; i++) {
const result = callbackFn(valuePairs[i].key, valuePairs[i].value);
if (result === false) {
break;
}
}
}
isEmpty() {
return this.size() === 0;
}
size() {
return Object.keys(this.table).length;
}
clear() {
this.table = {};
}
toString() {
if (this.isEmpty()) {
return '';
}
const valuePairs = this.keyValues();
let objString = `${valuePairs[0].toString()}`;
for (let i = 1; i < valuePairs.length; i++) {
objString = `${objString},${valuePairs[i].toString()}`;
}
return objString;
}
}
创建图类，graph.js
// 引入字典实例存储邻接表
import Dictionary from './dictionary';
export default class Graph {
constructor(isDirected = false) {
this.isDirected = isDirected;
this.vertices = [];
this.adjList = new Dictionary();
}
// 添加顶点
addVertex(v) {
if (!this.vertices.includes(v)) {
this.vertices.push(v);
this.adjList.set(v, []); // initialize adjacency list with array as well;
}
}
// 添加边
addEdge(a, b) {
if (!this.adjList.get(a)) {
this.addVertex(a);
}
if (!this.adjList.get(b)) {
this.addVertex(b);
}
this.adjList.get(a).push(b);
if (this.isDirected !== true) {
this.adjList.get(b).push(a);
}
}
getVertices() {
return this.vertices;
}
getAdjList() {
return this.adjList;
}
toString() {
let s = '';
for (let i = 0; i < this.vertices.length; i++) {
s += `${this.vertices[i]} -> `;
const neighbors = this.adjList.get(this.vertices[i]);
for (let j = 0; j < neighbors.length; j++) {
s += `${neighbors[j]} `;
}
s += '\n';
}
return s;
}
}
// test
const myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];
for (let i = 0; i < myVertices.length; i++) {
graph.addVertex(myVertices[i]);
}
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');
console.log(graph.toString());
// result
A -> B C D
B -> A E F
C -> A D G
D -> A C G H
E -> B I
F -> B
G -> C D
H -> D
I -> E
图的遍历分为两种：深度优先遍历和广度优先遍历。
图的遍历可视化展示
深度优先遍历代码实现：
const Colors = {
WHITE: 0,
GREY: 1,
BLACK: 2
};
const initializeColor = vertices => {
const color = {};
for (let i = 0; i < vertices.length; i++) {
color[vertices[i]] = Colors.WHITE;
}
return color;
};
const depthFirstSearchVisit = (u, color, adjList, callback) => {
color[u] = Colors.GREY;
if (callback) {
callback(u);
}
// console.log('Discovered ' + u);
const neighbors = adjList.get(u);
for (let i = 0; i < neighbors.length; i++) {
const w = neighbors[i];
if (color[w] === Colors.WHITE) {
depthFirstSearchVisit(w, color, adjList, callback);
}
}
color[u] = Colors.BLACK;
// console.log('explored ' + u);
};
export const depthFirstSearch = (graph, callback) => {
const vertices = graph.getVertices();
const adjList = graph.getAdjList();
const color = initializeColor(vertices);
for (let i = 0; i < vertices.length; i++) {
if (color[vertices[i]] === Colors.WHITE) {
depthFirstSearchVisit(vertices[i], color, adjList, callback);
}
}
};
const DFSVisit = (u, color, d, f, p, time, adjList) => {
// console.log('discovered ' + u);
color[u] = Colors.GREY;
d[u] = ++time.count;
const neighbors = adjList.get(u);
for (let i = 0; i < neighbors.length; i++) {
const w = neighbors[i];
if (color[w] === Colors.WHITE) {
p[w] = u;
DFSVisit(w, color, d, f, p, time, adjList);
}
}
color[u] = Colors.BLACK;
f[u] = ++time.count;
// console.log('explored ' + u);
};
export const DFS = graph => {
const vertices = graph.getVertices();
const adjList = graph.getAdjList();
const color = initializeColor(vertices);
const d = {};
const f = {};
const p = {};
const time = { count: 0 };
for (let i = 0; i < vertices.length; i++) {
f[vertices[i]] = 0;
d[vertices[i]] = 0;
p[vertices[i]] = null;
}
for (let i = 0; i < vertices.length; i++) {
if (color[vertices[i]] === Colors.WHITE) {
DFSVisit(vertices[i], color, d, f, p, time, adjList);
}
}
return {
discovery: d,
finished: f,
predecessors: p
};
};
深度优先--递归
深度优先--数组
图的广度优先遍历：
先穿创建一个 队列类：queue.js：
class Queue {
constructor() {
this.count = 0;
this.lowestCount = 0;
this.items = {};
}
enqueue(element) {
this.items[this.count] = element;
this.count++;
}
dequeue() {
if (this.isEmpty()) {
return undefined;
}
const result = this.items[this.lowestCount];
delete this.items[this.lowestCount];
this.lowestCount++;
return result;
}
isEmpty() {
return this.size() === 0;
}
clear() {
this.items = {};
this.count = 0;
this.lowestCount = 0;
}
size() {
return this.count - this.lowestCount;
}
toString() {
if (this.isEmpty()) {
return '';
}
let objString = `${this.items[this.lowestCount]}`;
for (let i = this.lowestCount + 1; i < this.count; i++) {
objString = `${objString},${this.items[i]}`;
}
return objString;
}
}
const Colors = {
WHITE: 0,
GREY: 1,
BLACK: 2
};
const initializeColor = vertices => {
const color = {};
for (let i = 0; i < vertices.length; i++) {
color[vertices[i]] = Colors.WHITE;
}
return color;
};
export const breadthFirstSearch = (graph, startVertex, callback) => {
const vertices = graph.getVertices();
const adjList = graph.getAdjList();
const color = initializeColor(vertices);
// 引入 queue.js 创建队列类
const queue = new Queue();
queue.enqueue(startVertex);
while (!queue.isEmpty()) {
const u = queue.dequeue();
const neighbors = adjList.get(u);
color[u] = Colors.GREY;
for (let i = 0; i < neighbors.length; i++) {
const w = neighbors[i];
if (color[w] === Colors.WHITE) {
color[w] = Colors.GREY;
queue.enqueue(w);
}
}
color[u] = Colors.BLACK;
if (callback) {
callback(u);
}
}
};
export const BFS = (graph, startVertex) => {
const vertices = graph.getVertices();
const adjList = graph.getAdjList();
const color = initializeColor(vertices);
const queue = new Queue();
const distances = {};
const predecessors = {};
queue.enqueue(startVertex);
for (let i = 0; i < vertices.length; i++) {
distances[vertices[i]] = 0;
predecessors[vertices[i]] = null;
}
while (!queue.isEmpty()) {
const u = queue.dequeue();
const neighbors = adjList.get(u);
color[u] = Colors.GREY;
for (let i = 0; i < neighbors.length; i++) {
const w = neighbors[i];
if (color[w] === Colors.WHITE) {
color[w] = Colors.GREY;
distances[w] = distances[u] + 1;
predecessors[w] = u;
queue.enqueue(w);
}
}
color[u] = Colors.BLACK;
}
return {
distances,
predecessors
};
};
广度优先搜索--集合队列
广度优先搜索--数组队列
网友评论