Các vấn đề phổ biến nhất có thể được giải quyết với cả hai cấu trúc dữ liệu này là gì?Có thể giải quyết vấn đề gì hoặc giải quyết dễ dàng hơn bằng cách sử dụng biểu đồ và cây cối?
Nó sẽ là tốt cho tôi để có cũng khuyến nghị về cuốn sách:
Điều đầu tiên tôi nghĩ đến khi đọc câu hỏi này là: loại đồ vật nào sử dụng biểu đồ/cây? và sau đó tôi nghĩ ngược lại cách tôi có thể sử dụng chúng.
Ví dụ, có hai công dụng phổ biến của một cây:
DOM, XML và cho rằng vấn đề, giống cấu trúc cây.
Điều này cũng có ý nghĩa. Điều đó có ý nghĩa vì cách dữ liệu này cần được sắp xếp. Một hệ thống tập tin cũng vậy. Trên một hệ thống UNIX có một nút gốc, và phân nhánh xuống dưới đây. Khi bạn gắn một thiết bị mới, bạn đang gắn nó vào cây.
Bạn cũng nên tự hỏi: liệu dữ liệu có rơi vào loại cấu trúc này không? Tạo cấu trúc dữ liệu có ý nghĩa với vấn đề và phần còn lại sẽ theo sau.
Theo như dễ dàng hơn, tôi nghĩ điều đó tương đối. Bạn có tốt với chức năng đệ quy để đi qua một cây/đồ thị? Nếu bạn cần cân bằng cây thì sao?
Hãy nghĩ về một chương trình giải quyết một câu đố tìm kiếm từ. Bạn có thể vạch ra tất cả các chữ cái của từ tìm kiếm vào một đồ thị và kiểm tra các nút xung quanh để xem chuỗi đó có khớp với bất kỳ từ nào không. Nhưng bạn không thể làm điều tương tự với một mảng đơn lẻ? Tất cả những gì bạn thực sự cần làm là di chuyển một chỉ mục để kiểm tra các chữ cái ở bên trái và bên phải, và theo chiều rộng để kiểm tra các chữ cái bên trên và bên dưới. Giải quyết vấn đề này với đồ thị không khó, nhưng nó có thể tạo ra nhiều công việc và khó khăn hơn nếu bạn không cảm thấy thoải mái khi sử dụng chúng - tất nhiên điều đó sẽ không khuyến khích bạn thực hiện nó, đặc biệt nếu bạn đang học chúng.
Tôi hy vọng điều đó sẽ giúp bạn suy nghĩ về những cấu trúc này. Đối với một đề xuất về sách, tôi phải đi với Introduction to Algorithms.
Có một khóa học cho những thứ như vậy tại trường đại học của tôi: CSE 326. Tôi không nghĩ cuốn sách quá hữu ích, nhưng các dự án rất vui và dạy cho bạn một chút công bằng về việc triển khai một số cấu trúc đơn giản hơn.
Ví dụ, một trong những vấn đề phổ biến nhất (theo số người sử dụng nó) được giải quyết bằng cây là mục nhập văn bản điện thoại di động. Bạn có thể sử dụng cây, không nhất thiết là nhị phân, để đại diện cho không gian của các từ có thể có thể xuất hiện từ bất kỳ danh sách số nào mà người dùng nhấn vào rất nhanh.
Algorithms for Java: Part 5 bởi Robert Sedgewick là tất cả về thuật toán đồ thị và cơ sở dữ liệu. Đây sẽ là một cuốn sách đầu tiên tốt để làm việc thông qua nếu bạn muốn thực hiện một số thuật toán đồ thị.
Đồ thị cảnh để vẽ đồ họa trong trò chơi và ứng dụng đa phương tiện sử dụng nhiều cây cối và đồ thị. Các nút biểu thị các đối tượng được hiển thị, biến đổi, điều khiển, nhóm, ...
Đồ thị cảnh thường có nhiều lớp và thuộc tính có nghĩa là bạn chỉ có thể vẽ một số nút của biểu đồ (thuộc tính) theo thứ tự được chỉ định (lớp) . Tùy thuộc vào loại đồ thị cảnh bạn có nó có thể có hai cấu trúc parralel: khai báo và instantiation. Th
The Algorithm Design Manual chứa một số nghiên cứu điển hình thú vị với việc sử dụng đồ thị sáng tạo. Mặc dù tên của nó, cuốn sách là rất dễ đọc và thậm chí giải trí ở lần.
@DavidJoiner/all:
FWIW: Một phiên bản mới của Algorithm Design Manual dự kiến trình làng bất kỳ ngày nào bây giờ.
Toàn bộ khóa học mà ông Giáo sư Skiena phát triển cuốn sách này cho cũng có sẵn trên web:
http://www.cs.sunysb.edu/~algorith/video-lectures/2007-1.html
sơ đồ mạch.
Biên dịch (Đồ thị tuần hoàn được chỉ định)
Bản đồ. Rất nhỏ gọn như đồ thị.
Sự cố về luồng mạng.
Quyết định cây cho các hệ thống chuyên gia (sic)
sơ đồ xương cá cho việc tìm kiếm lỗi, quá trình improvment, phân tích an toàn. Đối với điểm thưởng, hãy triển khai mã khôi phục lỗi của bạn làm đối tượng mà là biểu đồ xương cá.
Cây được sử dụng nhiều hơn trong các ngôn ngữ lập trình chức năng vì tính chất đệ quy của chúng.
Ngoài ra, đồ thị và cây cối là một cách hay để mô hình hóa nhiều vấn đề về AI.
Chỉ cần về mọi vấn đề có thể được viết lại theo lý thuyết đồ thị. Tôi không đùa, nhìn vào bất kỳ cuốn sách nào về vấn đề NP hoàn chỉnh, có một số vấn đề khá lập dị mà trở thành lý thuyết đồ thị bởi vì chúng tôi có các công cụ tốt để làm việc với đồ thị ...
Trò chơi thường sử dụng biểu đồ để thuận tiện cho việc tìm kiếm đường dẫn trong thế giới trò chơi. Biểu diễn biểu đồ của thế giới có thể có các thuật toán như tìm kiếm theo chiều rộng đầu tiên hoặc A * để tìm tuyến đường trên đó.
Họ cũng thường sử dụng cây để đại diện cho các thực thể trên thế giới. Nếu bạn có hàng nghìn thực thể và cần phải tìm một thực thể tại một vị trí nhất định thì việc lặp lại tuyến tính thông qua một danh sách có thể không hiệu quả, đặc biệt nếu bạn cần thực hiện nó thường xuyên. Do đó, khu vực này có thể được chia nhỏ thành một cây để cho phép nó được tìm kiếm nhanh hơn. Cũng giống như một không gian tuyến tính có thể được tìm kiếm một cách hiệu quả với tìm kiếm nhị phân (và do đó được chia thành một cây nhị phân), không gian 2D có thể được chia thành một không gian quadtree và 3D thành octree.