Đồ thị #1 Cơ bản

1. Đồ thị

Có thể định nghĩa đồ thị G là một cặp (V, E): G = (V, E). Trong đó V là tập các đỉnh (vertices) biểu diễn các đối tượng và E gọi là tập các cạnh (edges) biểu diễn mối quan hệ giữa các đối tượng. Chúng ta quan tâm tới mối quan hệ hai ngôi (pairwise relations) giữa các đối tượng nên có thể coi E là tập các cặp (u, v) với u và V là hai đỉnh của V biểu diễn hai đối tượng có quan hệ với nhau.

Một số dạng: đơn đồ thị (vô hướng, có hướng), đa đồ thị (có hướng, vô hướng)

2. Biểu diễn đồ thị

  • Ma trận kề (dễ nhất)
  • Danh sách cạnh
  • Danh sách kề
  • Danh sách liên thuộc
VD: Ma trận kề

– Ma trận kích thước nxn, mỗi ô Aij bằng 1 nếu (i, j) là cạnh của đồ thị, ngược lại ô Aij có giá trị bằng 0 nếu không có cạnh nối i và j. Ví dụ: hàng thứ 3, cột thứ 5 là ô A35 có giá trị là 1 có nghĩa trong đồ thị có cạnh 3 à 5.

  + Đối với đồ thị vô hướng thì Aij = Aji

  + Có thể dùng mảng hai chiều để biểu diễn ma trận kề:

var a: array[1..maxN, 1..maxN] of integer;

3. Đọc dữ liệu từ file

Dạng 1: (graph1.inp)

+ Dòng đầu tiên chứa số đỉnh n, đỉnh xuất phát s, đỉnh đích t.

+ n dòng tiếp theo, mỗi dòng i chứa một danh sách các đỉnh j, là đỉnh kề của i. Cuối dòng có số 0 để báo hiệu kết thúc danh sách.

graph1.inp
8 1 5
2 3 0
3 4 0
1 5 0
6 0 0
2 0
8 0
0

Dạng 2: (graph2.inp)

+ Dòng đầu tiên chứa số đỉnh n, số cạnh m, đỉnh xuất phát s, đỉnh đích t.

+ m dòng tiếp theo là m cạnh của đồ thị.

graph2.inp
8 9 1 5
1 2
1 3
2 3
2 4
3 1
3 5
4 6
6 2
7 8

Tên đỉnh cũng có thể sử dụng kí tự

graph2_1.inp
8 9 A E
A B
A C
B C
B D
C A
C E
D F
F B
G H

4. Ma trận dạng mê cung

a. Dạng 1: (mecung1.inp)

  + Dòng đầu tiên chứa kích thước ma trận (m x n), đỉnh xuất phát (sx, sy), đỉnh đích (tx, ty)

  + Các dòng tiếp theo các ô của ma trận (cách biểu diễn tuỳ theo đề), ví dụ: ô ‘O’ là đi được, ‘X’ là không đi được.

Hướng dẫn: có thể tạo mảng 2 chiều có phần tử là ký tự

mecung1.inp
5 6 1 1 2 5
OXXXXO
OOOOOO
XOXOEX
XOOXOX
OXOXXX

b. Dạng 2: (mecung2.inp)

  + Dòng đầu tiên gồm số kích thước của ma trận (m x n), đỉnh xuất phát (sx, sy), đỉnh đích (tx, ty)

  + Các dòng tiếp theo chứa toạ độ (x, y) các ô không đi qua được.

mecung2.inp
5 6 1 1 2 5
1 2
1 3
1 4
1 5
3 1
3 3
3 6
4 1
4 4
4 6
5 2
5 4
5 5
5 6

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *