โครงสร้างข้อมูล Tree และ Graph แตกต่างกันอย่างไร

ต้นไม้เป็นเพียงรูปแบบจำกัดของกราฟ

ต้นไม้มีทิศทาง (ความสัมพันธ์ระหว่างพ่อแม่/ลูก) และไม่มีวงจร เหมาะกับหมวดหมู่ Directed Acyclic Graphs (หรือ DAG) ดังนั้นต้นไม้จึงเป็น DAG โดยมีข้อจำกัดว่าเด็กจะมีผู้ปกครองได้เพียงคนเดียวเท่านั้น

สิ่งหนึ่งที่สำคัญที่ต้องชี้ให้เห็นคือ Tree ไม่ใช่โครงสร้างข้อมูลแบบเรียกซ้ำ ไม่สามารถนำไปใช้เป็นโครงสร้างข้อมูลแบบเรียกซ้ำได้เนื่องจากข้อจำกัดข้างต้น แต่การใช้งาน DAG ใดๆ ซึ่งโดยทั่วไปแล้วจะไม่เกิดซ้ำก็สามารถใช้ได้เช่นกัน การใช้งาน Tree ที่ฉันชอบคือการแสดงแผนที่แบบรวมศูนย์และไม่เกิดซ้ำ

โดยทั่วไปแล้วกราฟจะค้นหาจากความกว้างก่อนหรือลึกก่อน เช่นเดียวกับต้นไม้

แทนที่จะอธิบาย ฉันชอบแสดงเป็นรูปภาพมากกว่า

ต้นไม้แบบเรียลไทม์

กราฟในการใช้งานจริง

ใช่ สามารถมองเห็นแผนที่เป็นโครงสร้างข้อมูลกราฟได้

การเห็นพวกเขาแบบนี้ทำให้ชีวิตง่ายขึ้น ต้นไม้ถูกใช้ในสถานที่ที่เรารู้ว่าแต่ละโหนดมีพาเรนต์เพียงตัวเดียว แต่กราฟสามารถมีรายการก่อนหน้าได้หลายรายการ (โดยทั่วไปจะใช้คำระดับบนสุดกับกราฟ)

ในโลกแห่งความเป็นจริง คุณสามารถแสดงเกือบทุกอย่างได้โดยใช้กราฟ ฉันใช้แผนที่เป็นต้น หากคุณถือว่าแต่ละเมืองเป็นโหนด คุณสามารถเข้าถึงได้จากหลายจุด จุดที่นำไปสู่โหนดนี้เรียกว่ารุ่นก่อน และจุดที่โหนดนี้จะนำไปสู่เรียกว่าจุดสืบทอด

แผนภาพวงจรไฟฟ้า แผนผังของบ้าน เครือข่ายคอมพิวเตอร์ หรือระบบแม่น้ำ เป็นเพียงตัวอย่างกราฟบางส่วนเท่านั้น ตัวอย่างในโลกแห่งความเป็นจริงจำนวนมากถือได้ว่าเป็นกราฟ

แผนภาพทางเทคนิคอาจเป็นเช่นนี้

ต้นไม้ :

กราฟ :

อย่าลืมอ้างอิงลิงค์ด้านล่าง สิ่งเหล่านั้นจะตอบคำถามของคุณเกือบทั้งหมดเกี่ยวกับต้นไม้และกราฟ

อ้างอิง :

1. http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-17-trees-and-graphs/#_Toc362296541

2. http://www.community-of-knowledge.de/beitrag/data-trees-as-a-means-of-presenting-complex-data-analysis/

3. วิกิพีเดีย

คำตอบอื่น ๆ มีประโยชน์ แต่ไม่มีคุณสมบัติของแต่ละข้อ:

กราฟ

^{กราฟแบบไม่ระบุทิศทาง} แหล่งที่มาของภาพ: Wikipedia

^{กราฟกำกับ} แหล่งที่มาของภาพ: Wikipedia

• ประกอบด้วยชุดของจุดยอด (หรือโหนด) และชุดของขอบที่เชื่อมต่อบางส่วนหรือทั้งหมด
• ขอบใดๆ ก็ตามสามารถเชื่อมต่อจุดยอดสองจุดใดๆ ที่ไม่ได้เชื่อมต่อด้วยขอบที่เหมือนกันอยู่แล้ว (ในทิศทางเดียวกัน ในกรณีของกราฟที่มีการกำหนดทิศทาง)
• ไม่จำเป็นต้องเชื่อมต่อกัน (ขอบไม่จำเป็นต้องเชื่อมต่อจุดยอดทั้งหมดเข้าด้วยกัน): กราฟเดียวสามารถประกอบด้วยจุดยอดที่ตัดการเชื่อมต่อสองสามชุด
• #P6#

  #P7#

ต้นไม้

แหล่งที่มาของภาพ: Wikipedia

• ประเภทของกราฟ
• จุดยอดมักเรียกว่า "โหนด"
• Edges ได้รับการกำกับและแสดงถึงความสัมพันธ์ "เป็นลูกของ" (หรือ "เป็นพาเรนต์ของ")
• แต่ละโหนด (ยกเว้นโหนดรูท) มีพาเรนต์เดียวเท่านั้น (และลูกเป็นศูนย์หรือมากกว่า)
• มีโหนด "รูท" หนึ่งโหนด (หากแผนผังมีอย่างน้อยหนึ่งโหนด) ซึ่งเป็นโหนดที่ไม่มีพาเรนต์
• จะต้องมีการเชื่อมต่อ
• เป็นวงจร หมายความว่าไม่มีรอบ: "วงจรคือเส้นทาง [ลำดับ AKA ] ของขอบและจุดยอดซึ่งจุดยอดสามารถเข้าถึงได้จากตัวมันเอง"

มีการทับซ้อนกันในคุณสมบัติข้างต้น โดยเฉพาะอย่างยิ่ง คุณสมบัติสองรายการสุดท้ายมีความหมายโดยคุณสมบัติที่เหลือ แต่ทั้งหมดก็น่าสังเกต

ต้นไม้เป็นรูปแบบพิเศษของกราฟ กล่าวคือ กราฟที่เชื่อมต่อกันน้อยที่สุดและมีเส้นทางเดียวระหว่างสองจุดยอดใดๆ

ในกราฟ สามารถมีได้มากกว่าหนึ่งเส้นทาง กล่าวคือ กราฟสามารถมีเส้นทาง (ขอบ) ทิศทางเดียวหรือสองทิศทางระหว่างโหนดได้

นอกจากนี้ คุณยังสามารถดูรายละเอียดเพิ่มเติม: http://freefeast.info/difference-between/difference-between-trees-and-graphs-trees-vs-graphs/

ต้นไม้ชัดเจน: เป็นโครงสร้างข้อมูลแบบเรียกซ้ำที่ประกอบด้วยโหนดที่มีลูก

แผนที่ (หรือที่เรียกว่าพจนานุกรม) คือคู่คีย์/ค่า มอบกุญแจให้กับแผนที่และมันจะส่งคืนค่าที่เกี่ยวข้อง

สามารถใช้แผนที่ได้โดยใช้ต้นไม้ ฉันหวังว่าคุณจะไม่พบว่ามันน่าสับสน

อัปเดต: การสร้าง "กราฟ" ที่สับสนสำหรับ "แผนที่" ทำให้เกิดความสับสนมาก

กราฟมีความซับซ้อนมากกว่าต้นไม้ ต้นไม้บ่งบอกถึงความสัมพันธ์ระหว่างพ่อแม่และลูกแบบเรียกซ้ำ มีวิธีธรรมชาติในการสำรวจต้นไม้: ลึกก่อน กว้างก่อน เรียงลำดับระดับ ฯลฯ

กราฟสามารถมีเส้นทางทิศทางเดียวหรือสองทิศทางระหว่างโหนด เป็นแบบวงกลมหรือแบบไม่วน ฯลฯ ฉันจะถือว่ากราฟมีความซับซ้อนมากขึ้น

ฉันคิดว่าการค้นหาคร่าวๆ ในข้อความโครงสร้างข้อมูลที่เหมาะสม (เช่น "คู่มือการออกแบบอัลกอริทึม") จะให้ข้อมูลมากขึ้นและดีกว่าคำตอบ SO จำนวนเท่าใดก็ได้ ฉันอยากจะแนะนำให้คุณอย่าใช้เส้นทางที่ไม่โต้ตอบและเริ่มค้นคว้าด้วยตัวเอง

ในแผนผัง แต่ละโหนด (ยกเว้นโหนดรูท) มีโหนดก่อนหน้าหนึ่งโหนดและโหนดตัวตายตัวแทนหนึ่งหรือสองโหนด สามารถสำรวจได้โดยใช้การแวะชม In-order, Pre-order, Post-order และ Breadth First​ ต้นไม้เป็นกราฟชนิดพิเศษที่ไม่มีวงจร จึงเรียกว่า DAG (Directed Acyclic Graph) ต้นไม้เป็นรูปแบบลำดับชั้น

ในกราฟ แต่ละโหนดจะมีโหนดก่อนหน้าและโหนดที่สืบทอดตั้งแต่หนึ่งโหนดขึ้นไป กราฟถูกสำรวจโดยใช้อัลกอริธึม Depth First Search (DFS) และ Breadth First Search (BFS) กราฟมีวงจรจึงซับซ้อนกว่าต้นไม้ กราฟเป็นรูปแบบเครือข่าย กราฟมีสองประเภท: กราฟกำกับและกราฟไม่ระบุทิศทาง

โดยพื้นฐานแล้วต้นไม้นั้นเป็นกราฟที่ไม่มีทิศทางซึ่งไม่มีวงจร ดังนั้นเราสามารถพูดได้ว่าต้นไม้นั้นเป็นกราฟที่มีรูปแบบจำกัดมากกว่า อย่างไรก็ตาม แผนภูมิและกราฟมีแอปพลิเคชันที่แตกต่างกันเพื่อใช้อัลกอริทึมต่างๆ ในการเขียนโปรแกรม ตัวอย่างเช่น กราฟสามารถใช้สำหรับแผนผังถนนแบบจำลอง และต้นไม้สามารถใช้สำหรับการนำโครงสร้างข้อมูลแบบลำดับชั้นไปใช้

ต้นไม้เป็นกราฟที่:

ก) เมื่อนำทิศทางขอบออกแล้ว จะเชื่อมต่อกันและเป็นวงกลม

1. คุณสามารถลบสมมติฐานที่ว่าเป็นแบบอะไซเคิลออกได้
2. หากมีขอบเขตจำกัด คุณสามารถลบสมมติฐานที่เชื่อมโยงกันออกได้

b) ทุกจุดยอด ยกเว้นหนึ่งจุด ซึ่งเป็นราก มีระดับ 1

c) รูตมีอยู่ในระดับ 0

1. หากมีโหนดจำนวนมากเท่านั้น คุณสามารถลบสมมติฐานที่ว่ารูทมีระดับ 0 หรือสมมติฐานที่ว่าโหนดอื่นที่ไม่ใช่รูทมีระดับ 1

อ้างอิง: http://www.cs.cornell.edu/courses/cs2800/2016sp/lectures/lec27-29-graphtheory.pdf

ในทางคณิตศาสตร์ กราฟคือการแสดงชุดของวัตถุที่คู่ของวัตถุบางคู่เชื่อมต่อกันด้วยลิงก์ วัตถุที่เชื่อมต่อถึงกันจะแสดงด้วยนามธรรมทางคณิตศาสตร์ที่เรียกว่าจุดยอด และจุดเชื่อมต่อที่เชื่อมต่อจุดยอดบางคู่เรียกว่าขอบ (edge) โดยทั่วไปแล้ว กราฟจะแสดงในรูปแบบไดอะแกรมเป็นชุดของจุดสำหรับจุดยอด เชื่อมกันด้วยเส้นหรือเส้นโค้งสำหรับขอบ กราฟเป็นหนึ่งในเป้าหมายของการศึกษาวิชาคณิตศาสตร์แยกส่วน

หนึ่งโหนดรูทในแผนผังและมีเพียงพาเรนต์เดียวสำหรับลูกหนึ่งคน อย่างไรก็ตาม ไม่มีแนวคิดเกี่ยวกับโหนดรูท ความแตกต่างอีกประการหนึ่งคือ ต้นไม้เป็นแบบจำลองลำดับชั้น แต่กราฟเป็นแบบจำลองเครือข่าย

แนวคิดง่ายๆ คือ ต้นไม้ไม่มีการก่อตัวของวงจรและมีทิศทางเดียว ในขณะที่กราฟสร้างวงจรและมันจะเป็นแบบสองทิศทางในบางกรณี และทิศทางเดียวในอีกทิศทางหนึ่ง