Graphtheory
图论基础知识
了解图论的基本概念、术语和基础理论
图论基础知识
图论是数学的一个分支，研究由顶点和边组成的图结构。它在计算机科学、网络分析、社交网络等领域有广泛应用。
什么是图？
图（Graph）是由一组顶点（Vertex）和一组边（Edge）组成的数学结构，用于表示对象之间的关系。
图 = 顶点集合 + 边集合
G = (V, E)基本概念
- 顶点（Vertex/Node）：图中的基本元素，表示对象
- 边（Edge）：连接两个顶点的线，表示关系
- 度（Degree）：与顶点相连的边的数量
- 路径（Path）：从一个顶点到另一个顶点的边序列
- 连通性（Connectivity）：图中顶点之间的可达性
图的分类
1. 按边的方向分类
无向图（Undirected Graph）
边没有方向，表示双向关系。
// 无向图示例
const undirectedGraph = {
vertices: ['A', 'B', 'C', 'D'],
edges: [
['A', 'B'], // A 和 B 相连
['B', 'C'], // B 和 C 相连
['C', 'D'], // C 和 D 相连
['A', 'D'] // A 和 D 相连
]
};有向图（Directed Graph）
边有方向，表示单向关系。
// 有向图示例
const directedGraph = {
vertices: ['A', 'B', 'C', 'D'],
edges: [
['A', 'B'], // A 指向 B
['B', 'C'], // B 指向 C
['C', 'D'], // C 指向 D
['D', 'A'] // D 指向 A
]
};2. 按边的权重分类
无权图（Unweighted Graph）
边没有权重，只表示连接关系。
// 无权图
const unweightedGraph = {
vertices: ['A', 'B', 'C'],
edges: [
['A', 'B'],
['B', 'C'],
['A', 'C']
]
};加权图（Weighted Graph）
边有权重，表示距离、成本等数值。
// 加权图
const weightedGraph = {
vertices: ['A', 'B', 'C'],
edges: [
{ from: 'A', to: 'B', weight: 5 },
{ from: 'B', to: 'C', weight: 3 },
{ from: 'A', to: 'C', weight: 8 }
]
};3. 特殊图类型
完全图（Complete Graph）
任意两个顶点之间都有边相连。
// 完全图 K4
const completeGraph = {
vertices: ['A', 'B', 'C', 'D'],
edges: [
['A', 'B'], ['A', 'C'], ['A', 'D'],
['B', 'C'], ['B', 'D'],
['C', 'D']
]
};二分图（Bipartite Graph）
顶点可以分为两个独立集合，所有边都连接不同集合的顶点。
// 二分图示例
const bipartiteGraph = {
leftVertices: ['A', 'B', 'C'],
rightVertices: ['X', 'Y', 'Z'],
edges: [
['A', 'X'], ['A', 'Y'],
['B', 'Y'], ['B', 'Z'],
['C', 'X'], ['C', 'Z']
]
};图的表示方法
1. 邻接矩阵（Adjacency Matrix）
使用二维数组表示图的连接关系。
// 邻接矩阵表示
class AdjacencyMatrix {
constructor(vertices) {
this.vertices = vertices;
this.matrix = Array(vertices.length).fill().map(() =>
Array(vertices.length).fill(0)
);
}
// 添加边
addEdge(from, to, weight = 1) {
const fromIndex = this.vertices.indexOf(from);
const toIndex = this.vertices.indexOf(to);
if (fromIndex !== -1 && toIndex !== -1) {
this.matrix[fromIndex][toIndex] = weight;
this.matrix[toIndex][fromIndex] = weight; // 无向图
}
}
// 检查是否有边
hasEdge(from, to) {
const fromIndex = this.vertices.indexOf(from);
const toIndex = this.vertices.indexOf(to);
return this.matrix[fromIndex][toIndex] > 0;
}
// 获取顶点的邻居
getNeighbors(vertex) {
const index = this.vertices.indexOf(vertex);
const neighbors = [];
for (let i = 0; i < this.vertices.length; i++) {
if (this.matrix[index][i] > 0) {
neighbors.push(this.vertices[i]);
}
}
return neighbors;
}
// 打印矩阵
print() {
console.log(' ' + this.vertices.join(' '));
for (let i = 0; i < this.matrix.length; i++) {
console.log(this.vertices[i] + ' ' + this.matrix[i].join(' '));
}
}
}
// 使用示例
const graph = new AdjacencyMatrix(['A', 'B', 'C', 'D']);
graph.addEdge('A', 'B');
graph.addEdge('B', 'C');
graph.addEdge('C', 'D');
graph.addEdge('A', 'D');
console.log('邻接矩阵:');
graph.print();
console.log('A的邻居:', graph.getNeighbors('A'));2. 邻接表（Adjacency List）
使用数组或哈希表存储每个顶点的邻居。
// 邻接表表示
class AdjacencyList {
constructor() {
this.vertices = new Map();
}
// 添加顶点
addVertex(vertex) {
if (!this.vertices.has(vertex)) {
this.vertices.set(vertex, []);
}
}
// 添加边
addEdge(from, to, weight = 1) {
this.addVertex(from);
this.addVertex(to);
this.vertices.get(from).push({ to, weight });
this.vertices.get(to).push({ to: from, weight }); // 无向图
}
// 获取顶点的邻居
getNeighbors(vertex) {
return this.vertices.get(vertex) || [];
}
// 获取所有顶点
getVertices() {
return Array.from(this.vertices.keys());
}
// 打印图
print() {
for (const [vertex, neighbors] of this.vertices) {
console.log(`${vertex} -> ${neighbors.map(n => n.to).join(', ')}`);
}
}
}
// 使用示例
const graph = new AdjacencyList();
graph.addEdge('A', 'B', 5);
graph.addEdge('B', 'C', 3);
graph.addEdge('C', 'D', 2);
graph.addEdge('A', 'D', 8);
console.log('邻接表:');
graph.print();
console.log('A的邻居:', graph.getNeighbors('A'));3. 边列表（Edge List）
直接存储所有边的列表。
// 边列表表示
class EdgeList {
constructor() {
this.edges = [];
this.vertices = new Set();
}
// 添加边
addEdge(from, to, weight = 1) {
this.edges.push({ from, to, weight });
this.vertices.add(from);
this.vertices.add(to);
}
// 获取顶点的邻居
getNeighbors(vertex) {
const neighbors = [];
for (const edge of this.edges) {
if (edge.from === vertex) {
neighbors.push({ to: edge.to, weight: edge.weight });
} else if (edge.to === vertex) {
neighbors.push({ to: edge.from, weight: edge.weight });
}
}
return neighbors;
}
// 获取所有顶点
getVertices() {
return Array.from(this.vertices);
}
// 打印图
print() {
for (const edge of this.edges) {
console.log(`${edge.from} --${edge.weight}--> ${edge.to}`);
}
}
}图的基本性质
1. 度（Degree）
顶点的度是与该顶点相连的边的数量。
// 计算顶点的度
function calculateDegree(graph, vertex) {
if (graph instanceof AdjacencyMatrix) {
const index = graph.vertices.indexOf(vertex);
return graph.matrix[index].reduce((sum, weight) => sum + (weight > 0 ? 1 : 0), 0);
} else if (graph instanceof AdjacencyList) {
return graph.getNeighbors(vertex).length;
}
}
// 计算所有顶点的度
function calculateAllDegrees(graph) {
const degrees = {};
const vertices = graph.getVertices ? graph.getVertices() : graph.vertices;
for (const vertex of vertices) {
degrees[vertex] = calculateDegree(graph, vertex);
}
return degrees;
}2. 路径和连通性
路径（Path）
从一个顶点到另一个顶点的边序列。
// 检查是否存在路径
function hasPath(graph, start, end, visited = new Set()) {
if (start === end) return true;
visited.add(start);
const neighbors = graph.getNeighbors(start);
for (const neighbor of neighbors) {
const neighborVertex = neighbor.to || neighbor;
if (!visited.has(neighborVertex)) {
if (hasPath(graph, neighborVertex, end, visited)) {
return true;
}
}
}
return false;
}
// 查找所有路径
function findAllPaths(graph, start, end, path = [], visited = new Set()) {
path.push(start);
visited.add(start);
if (start === end) {
return [path.slice()];
}
const paths = [];
const neighbors = graph.getNeighbors(start);
for (const neighbor of neighbors) {
const neighborVertex = neighbor.to || neighbor;
if (!visited.has(neighborVertex)) {
const newPaths = findAllPaths(graph, neighborVertex, end, path, visited);
paths.push(...newPaths);
}
}
path.pop();
visited.delete(start);
return paths;
}连通性（Connectivity）
图中顶点之间的可达性。
// 检查图的连通性
function isConnected(graph) {
const vertices = graph.getVertices ? graph.getVertices() : graph.vertices;
if (vertices.length <= 1) return true;
const start = vertices[0];
const visited = new Set();
// 从起始顶点开始DFS
dfs(graph, start, visited);
// 检查是否所有顶点都被访问
return visited.size === vertices.length;
}
// 深度优先搜索
function dfs(graph, vertex, visited) {
visited.add(vertex);
const neighbors = graph.getNeighbors(vertex);
for (const neighbor of neighbors) {
const neighborVertex = neighbor.to || neighbor;
if (!visited.has(neighborVertex)) {
dfs(graph, neighborVertex, visited);
}
}
}3. 环（Cycle）
图中包含重复顶点的路径。
// 检测环
function hasCycle(graph) {
const visited = new Set();
const recStack = new Set();
const vertices = graph.getVertices ? graph.getVertices() : graph.vertices;
for (const vertex of vertices) {
if (!visited.has(vertex)) {
if (dfsCycle(graph, vertex, visited, recStack)) {
return true;
}
}
}
return false;
}
// DFS检测环
function dfsCycle(graph, vertex, visited, recStack) {
visited.add(vertex);
recStack.add(vertex);
const neighbors = graph.getNeighbors(vertex);
for (const neighbor of neighbors) {
const neighborVertex = neighbor.to || neighbor;
if (!visited.has(neighborVertex)) {
if (dfsCycle(graph, neighborVertex, visited, recStack)) {
return true;
}
} else if (recStack.has(neighborVertex)) {
return true;
}
}
recStack.delete(vertex);
return false;
}图的应用场景
1. 社交网络
// 社交网络图
class SocialNetwork {
constructor() {
this.users = new Map();
}
// 添加用户
addUser(userId, name) {
this.users.set(userId, {
id: userId,
name: name,
friends: new Set(),
posts: []
});
}
// 添加好友关系
addFriendship(user1, user2) {
if (this.users.has(user1) && this.users.has(user2)) {
this.users.get(user1).friends.add(user2);
this.users.get(user2).friends.add(user1);
}
}
// 获取好友列表
getFriends(userId) {
const user = this.users.get(userId);
return user ? Array.from(user.friends) : [];
}
// 获取共同好友
getCommonFriends(user1, user2) {
const friends1 = new Set(this.getFriends(user1));
const friends2 = new Set(this.getFriends(user2));
return Array.from(friends1).filter(friend => friends2.has(friend));
}
// 计算社交距离
getSocialDistance(user1, user2) {
const visited = new Set();
const queue = [{ userId: user1, distance: 0 }];
while (queue.length > 0) {
const { userId, distance } = queue.shift();
if (userId === user2) {
return distance;
}
if (!visited.has(userId)) {
visited.add(userId);
const friends = this.getFriends(userId);
for (const friend of friends) {
if (!visited.has(friend)) {
queue.push({ userId: friend, distance: distance + 1 });
}
}
}
}
return -1; // 不可达
}
}2. 网络拓扑
// 网络拓扑图
class NetworkTopology {
constructor() {
this.nodes = new Map();
this.connections = [];
}
// 添加网络节点
addNode(nodeId, type, capacity) {
this.nodes.set(nodeId, {
id: nodeId,
type: type, // router, switch, server, client
capacity: capacity,
status: 'active'
});
}
// 添加连接
addConnection(from, to, bandwidth) {
this.connections.push({
from: from,
to: to,
bandwidth: bandwidth,
status: 'active'
});
}
// 检查网络连通性
isNetworkConnected() {
const nodes = Array.from(this.nodes.keys());
if (nodes.length <= 1) return true;
const visited = new Set();
this.dfsNetwork(nodes[0], visited);
return visited.size === nodes.length;
}
// 网络DFS
dfsNetwork(nodeId, visited) {
visited.add(nodeId);
for (const connection of this.connections) {
if (connection.status === 'active') {
const nextNode = connection.from === nodeId ? connection.to :
connection.to === nodeId ? connection.from : null;
if (nextNode && !visited.has(nextNode)) {
this.dfsNetwork(nextNode, visited);
}
}
}
}
// 查找关键节点（割点）
findCriticalNodes() {
const criticalNodes = [];
const nodes = Array.from(this.nodes.keys());
for (const node of nodes) {
// 临时移除节点
const tempConnections = this.connections.filter(c =>
c.from !== node && c.to !== node
);
// 检查连通性
if (tempConnections.length > 0) {
const visited = new Set();
const remainingNodes = nodes.filter(n => n !== node);
if (remainingNodes.length > 0) {
this.dfsNetworkWithConnections(remainingNodes[0], visited, tempConnections);
if (visited.size < remainingNodes.length) {
criticalNodes.push(node);
}
}
}
}
return criticalNodes;
}
}3. 地图导航
// 地图导航图
class NavigationGraph {
constructor() {
this.locations = new Map();
this.roads = [];
}
// 添加地点
addLocation(id, name, coordinates) {
this.locations.set(id, {
id: id,
name: name,
coordinates: coordinates
});
}
// 添加道路
addRoad(from, to, distance, time) {
this.roads.push({
from: from,
to: to,
distance: distance,
time: time
});
}
// 查找最短路径（按距离）
findShortestPath(start, end) {
const distances = new Map();
const previous = new Map();
const unvisited = new Set();
// 初始化
for (const location of this.locations.keys()) {
distances.set(location, Infinity);
unvisited.add(location);
}
distances.set(start, 0);
while (unvisited.size > 0) {
// 找到距离最小的未访问节点
let current = null;
let minDistance = Infinity;
for (const location of unvisited) {
if (distances.get(location) < minDistance) {
minDistance = distances.get(location);
current = location;
}
}
if (current === null) break;
unvisited.delete(current);
if (current === end) break;
// 更新邻居距离
for (const road of this.roads) {
if (road.from === current && unvisited.has(road.to)) {
const newDistance = distances.get(current) + road.distance;
if (newDistance < distances.get(road.to)) {
distances.set(road.to, newDistance);
previous.set(road.to, current);
}
}
}
}
// 重建路径
const path = [];
let current = end;
while (current !== null) {
path.unshift(current);
current = previous.get(current);
}
return {
path: path,
distance: distances.get(end)
};
}
}图论的重要定理
1. 握手定理（Handshaking Lemma）
在任何图中，所有顶点的度数之和等于边数的两倍。
// 验证握手定理
function verifyHandshakingLemma(graph) {
const degrees = calculateAllDegrees(graph);
const totalDegree = Object.values(degrees).reduce((sum, degree) => sum + degree, 0);
const edgeCount = graph.edges ? graph.edges.length :
graph.vertices ? graph.vertices.reduce((sum, neighbors) => sum + neighbors.length, 0) / 2 : 0;
console.log(`总度数: ${totalDegree}`);
console.log(`边数: ${edgeCount}`);
console.log(`边数的两倍: ${edgeCount * 2}`);
console.log(`握手定理成立: ${totalDegree === edgeCount * 2}`);
return totalDegree === edgeCount * 2;
}2. 欧拉路径定理
图中存在欧拉路径当且仅当图是连通的且恰好有0个或2个奇数度顶点。
// 检查是否存在欧拉路径
function hasEulerPath(graph) {
if (!isConnected(graph)) return false;
const degrees = calculateAllDegrees(graph);
const oddDegreeCount = Object.values(degrees).filter(degree => degree % 2 === 1).length;
return oddDegreeCount === 0 || oddDegreeCount === 2;
}学习建议
- 掌握基本概念：理解顶点、边、度、路径等基本术语
- 熟悉表示方法：掌握邻接矩阵、邻接表、边列表的优缺点
- 实践算法：动手实现图的遍历、搜索算法
- 应用导向：结合实际问题学习图论的应用
- 数学基础：学习相关的数学理论，如组合数学、线性代数
图论是计算机科学的重要基础，掌握图论知识对于解决复杂问题非常有帮助。