Kiểm tra đồ thị đầy đủ

algorithm

(Tuấn) #1


Chuyện là em gặp bài tập của môn trí tuệ nhân tạo như này ạ, em loay hoay tìm cách mãi vẫn không nghĩ ra được cách làm với cách cài đặt các cấu trúc dữ liệu phù hơp. Anh nào có thể giúp em với được không ạ? Em xin cảm ơn ạ


(Huy Nguyễn) #2

Input k lớn thì cứ brute force thôi :v. Từ dữ liệu tìm đc các đỉnh, từ đó tạo ra tất cả các cạnh r kiểm tra thôi


(Hung) #3

Complete digraph Kn, có |V| = n và |E| = n(n-1). Trong đó, mỗi vertex có in degree = n-1 và out degree = n-1.

Bước 1: Precondition
Tạo hash map có key là vertex, value là tuple 2 giá trị thể hiện in degreeout degree của vertex. Một biến V lưu số đỉnh, cũng là số key-value pair trong map. Một biến E lưu số cạnh nhập từ input file.

Sau đó kiểm tra tất cả điều kiện của complete digraph:

  • V(V-1) = E
  • Mỗi key đều có in degree = out degree = V-1

Nếu thoả mãn hết thì chuyển sang bước 2, ngược lại xuất output false. Độ phức tạp O(n).

Bước 2:
Sử dụng adjancent matrix để kiểm tra graph có chính xác là complete digraph. Độ phức tạp O(n2)


(Gió) #4

Lập 1 ma trận n x n, ánh xạ 1 đỉnh sang 1 số: Cạnh i,j sẽ tăng M[i,j] lên 1
Nếu là đơn đồ thị đầy đủ thì tất cả các ô đều là 1, trừ đường chéo chính


(Tuấn) #5
#include"iostream"
#include"algorithm"
#include "string"
#include "map"
#include "set"
using namespace std;
int main()
{
	string u, v;
	int e;
	cin >> e;
	map<string, set<string>> A;
	map<string, set<string>>::iterator it;
	set <string> ::iterator it1;
	for (int i = 0; i < e; i++)
	{
		cin.ignore();
		getline(cin, u);
		getline(cin, v);
		A[u].insert(v);
	}
	for (it = A.begin(); it != A.end(); it++)
	{
	}
	return 0;
	system("pause");

Cảm ơn mọi người nhiều ạ, em làm đến đây thì bí ạ, không biết làm sao để truy cập dữ liệu trong map ạ? :frowning:


(Hung) #6

Mình xoá comment rồi mà. Lý do vì cách của mình sai.
Ví dụ dưới là graph không phải Kn nhưng vẫn thoả điều kiện mình đưa ra.

0 1 2 0
1 0 1 1
1 0 0 2
1 2 0 0

Giờ chỉ có cách kiểm tra mảng như Gió, chạy O(n2). Mình thử tối ưu xuống O(n) nhưng không thành công.

Bạn có thể tham khảo cách của mình như là precondition, nếu thoả mãn thì phải kiểm tra thêm O(n2) bằng ma trận để ra kết quả chính xác. Code chạy nhanh hơn tí xíu.


(rogp10) #7

Dùng ma trận kề thôi bạn :slight_smile: như @Gio đã nêu, do đồ thị sẽ kín hết cạnh :smiley:

Đầu tiên số dòng dữ liệu không thể dưới N*(N-1), nếu có thì false ngay. Hoặc là O(1) hoặc o(N^2) :smiley:


(Tuấn) #8

Cảm ơn bạn nhiều, nhưng đề yêu cầu nhập đỉnh là một chuỗi, Bạn có cách nào để ánh xạ từ chuỗi sang sô không, chỉ mình với


83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?