Graph
Tags:
Hard
Skills:
Graph
June 24, 2025
04:32 AM
Loading content...
Related Posts
Theory Data Structure And Algorithms
Related Posts
Theory Data Structure And Algorithms
Đồ thị được tạo thành từ hai thành phần chính:
(u,v) biểu diễn một mũi tên đi từ đỉnh u đến vĐặc điểm đồ thị có hướng
u đến v nếu co cạnh (u,v)v, ký hiệu là deg+(v)v ký hiệu là deg−(v)(u,v) và (v,u) là như nhauỨng dụng
Đồ thị có hướng được sử dụng nhiều trong mô hình hóa các hệ thống có quan hệ một chiều như: mạng xã hội (theo dõi, kết bạn một chiều), mô hình luồng công việc, mô hình hóa các trạng thái chuyển đổi, v.v
Đồ thị được tạo thành từ hai thành phần chính:
Đặc điểm đồ thị vô hướng
Một số tính chất
Ứng dụng
Đồ thị vô hướng được sử dụng để mô hình hóa các quan hệ hai chiều, ví dụ: mạng lưới bạn bè, mạng máy tính, hệ thống giao thông, v.v.
1function convertToAdjacencyList(edges: [number, number][], num_vertices): Map<number, number[]> {
2 const adjacency_list: Map<number, number[]> = new Map();
3
4 // Init
5 for(let i =0 ; i < num_vertices; i++) {
6 adjacency_list.set(i, []);
7 }
8
9 // Add adjacency vertices to list
10 for(const [source, destination] of edges) {
11 adjacency_list.get(source)?.push(destination);
12 adjacency_list.get(destination)?.push(source);
13 }
14
15 return adjacency_list
16}1function dfs(adjacency_list: Map<number, number[]>, start: number): number[] {
2 const stack: number[] = [];
3 const visited: Set<number> = new Set();
4 const result: number[] = [];
5
6 while(stack.length > 0) {
7 const node = stack.pop();
8 if(!visited.has(node)) {
9 visited.add(node);
10 result.push(node);
11
12 const neighbors = adjacency_list.get(node) || [];
13
14 for(const neighbor of neighbors) {
15 if(!visited.has(neighbor)) {
16 stack.push(neighbor);
17 }
18 }
19 }
20 }
21
22 return result;
23}1function bfs(adjacency_list: Map<number, number[]>, start: number): number[] {
2 const queue: number[] = [start];
3 const visited: Set<number> = new Set();
4 const result: number[] = [];
5
6 while(queue.length > 0) {
7 const node = queue.shift()!;
8 if(!visited.has(node)) {
9 visited.add(node);
10 result.push(node);
11
12 const neighbors = adjacency_list.get(node) || [];
13 for(const neighbor fo neighbors) {
14 if(!visited.has(neighbor)) {
15 queue.push(neighbor)
16 }
17 }
18 }
19 }
20
21 return result;
22}