ในวิทยาการคอมพิวเตอร์กราฟเป็นชนิดข้อมูลนามธรรมที่ออกแบบมาเพื่อนำ แนวคิด ของกราฟแบบไม่มีทิศทางและกราฟแบบมีทิศทาง จาก ทฤษฎีกราฟในสาขาคณิตศาสตร์มาใช้

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

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

การดำเนินการพื้นฐานที่โครงสร้างข้อมูลกราฟG จัดเตรียมไว้ มักจะรวมถึง: ^{[ 1 ]}

• adjacent( G , x , y ) : ทดสอบว่ามีเส้นเชื่อมจากจุดยอดxไปยังจุดยอดy หรือ ไม่ ;
• neighbors( G , x ) : แสดงรายการจุดยอด yทั้งหมดที่มีเส้นเชื่อมจากจุดยอดxไปยังจุดยอดy ;
• add_vertex( G , x ) : เพิ่มจุดยอดxหากยังไม่มีอยู่
• remove_vertex( G , x ) : ลบจุดยอดx ออก หากมีอยู่
• add_edge( G , x , y , z ) : เพิ่มขอบzจากจุดยอดxไปยังจุดยอดyหากยังไม่มีอยู่
• remove_edge( G , x , y ) : ลบเส้นเชื่อมจากจุดยอดxไปยังจุดยอดyหากมีอยู่
• get_vertex_value( G , x ) : ส่งคืนค่าที่เกี่ยวข้องกับจุดยอดx ;
• set_vertex_value( G , x , v ) : กำหนดค่าที่เชื่อมโยงกับจุดยอดxให้เป็นv

โครงสร้างที่เชื่อมโยงค่ากับขอบมักจะให้สิ่งต่อไปนี้ด้วย: ^{[ 1 ]}

• get_edge_value( G , x , y ) : ส่งคืนค่าที่เกี่ยวข้องกับขอบ ( x , y );
• set_edge_value( G , x , y , v ) : กำหนดค่าที่เชื่อมโยงกับขอบ ( x , y ) ให้เป็นv

รายการที่อยู่ติดกัน^{[ 2 ]}

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

เมทริกซ์ประชิด^{[ 3 ]}

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

เมทริกซ์เหตุการณ์^{[ 4 ]}

เมทริกซ์สองมิติ ซึ่งแถวแทนจุดยอด และคอลัมน์แทนเส้นเชื่อม ค่าในเมทริกซ์แสดงถึงความสัมพันธ์ระหว่างจุดยอดในแถวหนึ่งกับเส้นเชื่อมในคอลัมน์หนึ่ง

ตารางต่อไปนี้แสดง ต้นทุน ความซับซ้อนของเวลาในการดำเนินการต่างๆ บนกราฟ สำหรับแต่ละรูปแบบการแสดงผล โดยที่ | V | คือจำนวนจุดยอด และ | E | คือจำนวนขอบ ในรูปแบบเมทริกซ์ ค่าต่างๆ จะเข้ารหัสต้นทุนของการติดตามขอบแต่ละเส้น ต้นทุนของขอบที่ไม่มีอยู่จะถือว่ามีค่าเป็น ∞

	รายการที่อยู่ติดกัน	เมทริกซ์ประชิด	เมทริกซ์อุบัติการณ์
กราฟร้านค้า	${\displaystyle O(|V|+|E|)}$	${\displaystyle O(|V|^{2})}$	${\displaystyle O(|V|\cdot |E|)}$
เพิ่มจุดยอด	${\displaystyle O(1)}$	${\displaystyle O(|V|^{2})}$	${\displaystyle O(|V|\cdot |E|)}$
เพิ่มขอบ	${\displaystyle O(1)}$	${\displaystyle O(1)}$	${\displaystyle O(|V|\cdot |E|)}$
ลบจุดยอด	${\displaystyle O(|E|)}$	${\displaystyle O(|V|^{2})}$	${\displaystyle O(|V|\cdot |E|)}$
เอาขอบออก	${\displaystyle O(|V|)}$	${\displaystyle O(1)}$	${\displaystyle O(|V|\cdot |E|)}$
จุดยอดxและyอยู่ติดกันหรือไม่ (โดยสมมติว่าทราบตำแหน่งการจัดเก็บของจุดยอดเหล่านั้นแล้ว)?	${\displaystyle O(|V|)}$	${\displaystyle O(1)}$	${\displaystyle O(|E|)}$
หมายเหตุ	การลบจุดยอดและเส้นเชื่อมทำได้ช้า เนื่องจากต้องค้นหาจุดยอดหรือเส้นเชื่อมทั้งหมดก่อน	การเพิ่มหรือลบจุดยอดทำได้ช้า เนื่องจากต้องปรับขนาด/คัดลอกเมทริกซ์ก่อน	การเพิ่มหรือลบจุดยอดและเส้นขอบทำได้ช้า เนื่องจากต้องปรับขนาด/คัดลอกเมทริกซ์ก่อน

โดยทั่วไปแล้ว รายการประชิดจะเหมาะสมกว่าสำหรับการแสดงกราฟแบบเบาบางในขณะที่เมทริกซ์ประชิดจะเหมาะสมกว่าหากกราฟมีความหนาแน่น กล่าวคือ จำนวนขอบใกล้เคียงกับจำนวนจุดยอดกำลังสองหรือหากจำเป็นต้องตรวจสอบอย่างรวดเร็วว่ามีขอบที่เชื่อมต่อจุดยอดสองจุดหรือไม่^{[ 5 ] [ 6 ]}${\displaystyle |E|}$${\displaystyle |V|^{2}}$

ความซับซ้อนของเวลาในการดำเนินการในการแสดงรายการความสัมพันธ์สามารถปรับปรุงได้โดยการจัดเก็บชุดของจุดยอดที่อยู่ติดกันในโครงสร้างข้อมูลที่มีประสิทธิภาพมากขึ้น เช่นตารางแฮชหรือต้นไม้ค้นหาไบนารีแบบสมดุล (การแสดงแบบหลังนี้ต้องการให้จุดยอดถูกระบุด้วยองค์ประกอบของชุดที่เรียงลำดับเชิงเส้น เช่น จำนวนเต็มหรือสตริงอักขระ) การแสดงจุดยอดที่อยู่ติดกันผ่านตารางแฮชทำให้ความซับซ้อนของเวลาเฉลี่ยแบบถัวเฉลี่ย ใน การทดสอบความสัมพันธ์ของจุดยอดสองจุดที่กำหนดและการลบขอบ และความซับซ้อนของเวลาเฉลี่ยแบบถัวเฉลี่ย^{[ 7 ]}ในการลบจุดยอดxที่ กำหนดที่ มีดีกรี ความซับซ้อนของเวลาของการดำเนินการอื่นๆ และข้อกำหนดพื้นที่เชิงอะซิมโทติกไม่เปลี่ยนแปลง ${\displaystyle O(1)}$${\displaystyle O(\deg(x))}$${\displaystyle \deg(x)}$

การประมวลผลแบบขนานของปัญหากราฟเผชิญกับความท้าทายที่สำคัญ ได้แก่ การคำนวณที่ขับเคลื่อนด้วยข้อมูล ปัญหาที่ไม่มีโครงสร้าง การเข้าถึงข้อมูลที่ไม่ดี และอัตราส่วนการเข้าถึงข้อมูลต่อการคำนวณที่สูง^{[ 8 ] [ 9 ]}การแสดงกราฟที่ใช้สำหรับสถาปัตยกรรมแบบขนานมีบทบาทสำคัญในการรับมือกับความท้าทายเหล่านี้ การเลือกการแสดงกราฟที่ไม่เหมาะสมอาจทำให้ต้นทุนการสื่อสารของอัลกอริทึมสูงขึ้นโดยไม่จำเป็น ซึ่งจะลดความสามารถในการปรับขนาดในส่วนต่อไปนี้ จะพิจารณาสถาปัตยกรรมหน่วยความจำร่วมและแบบกระจาย

ในกรณีของ โมเดล หน่วยความจำร่วมการแสดงกราฟที่ใช้สำหรับการประมวลผลแบบขนานจะเหมือนกับในกรณีลำดับ^{[ 10 ]}เนื่องจากการเข้าถึงแบบอ่านอย่างเดียวแบบขนานไปยังการแสดงกราฟ (เช่นรายการความสัมพันธ์ ) มีประสิทธิภาพในหน่วยความจำร่วม

ใน แบบจำลอง หน่วยความจำแบบกระจายวิธีการทั่วไปคือการแบ่งเซตจุดยอดของกราฟออกเป็นเซตโดยที่คือจำนวนหน่วยประมวลผล (PE) ที่พร้อมใช้งาน จากนั้นจึงกระจายการแบ่งเซตจุดยอดไปยัง PE ที่มีดัชนีตรงกัน รวมถึงขอบที่เกี่ยวข้องด้วย PE แต่ละตัวจะมี กราฟ ย่อย ของตัวเอง ซึ่งขอบที่มีจุดปลายอยู่ในพาร์ติชันอื่นต้องได้รับการดูแลเป็นพิเศษ สำหรับอินเทอร์เฟซการสื่อสารมาตรฐาน เช่นMPIจะต้องสามารถระบุ ID ของ PE ที่เป็นเจ้าของจุดปลายอีกด้านได้ ในระหว่างการคำนวณในอัลกอริทึมกราฟแบบกระจาย การส่งข้อมูลไปตามขอบเหล่านี้หมายถึงการสื่อสาร^{[ 10 ]}${\displaystyle V}$${\displaystyle p}$${\displaystyle V_{0},\dots ,V_{p-1}}$${\displaystyle p}$

การแบ่งกราฟต้องทำอย่างระมัดระวัง - มีการแลกเปลี่ยนระหว่างการสื่อสารที่ต่ำและการแบ่งขนาดที่เท่ากัน^{[ 11 ]}แต่การแบ่งกราฟเป็นปัญหา NP-hard ดังนั้นจึงไม่สามารถคำนวณได้ จึงใช้ฮิวริสติกส์ต่อไปนี้แทน

การแบ่งพาร์ติชัน 1 มิติ: โปรเซสเซอร์แต่ละตัวจะได้รับจุดยอดและขอบขาออกที่สอดคล้องกัน ซึ่งสามารถเข้าใจได้ว่าเป็นการแยกเมทริกซ์ความประชิดตามแถวหรือตามคอลัมน์ สำหรับอัลกอริธึมที่ทำงานบนการแสดงแทนนี้ จำเป็นต้องมีขั้นตอนการสื่อสารแบบ All-to-All รวมถึงขนาดบัฟเฟอร์ข้อความ เนื่องจาก PE แต่ละตัวอาจมีขอบขาออกไปยัง PE อื่นๆ ทุกตัว^{[ 12 ]}${\displaystyle n/p}$${\displaystyle {\คณิตศาสตร์ {O}}(m)}$

การแบ่งพาร์ติชัน 2 มิติ: โปรเซสเซอร์แต่ละตัวจะได้รับเมทริกซ์ย่อยของเมทริกซ์ความประชิด สมมติว่าโปรเซสเซอร์เรียงตัวเป็นรูปสี่เหลี่ยมผืนผ้าโดยที่และคือจำนวนองค์ประกอบการประมวลผลในแต่ละแถวและคอลัมน์ตามลำดับ จากนั้นโปรเซสเซอร์แต่ละตัวจะได้รับเมทริกซ์ย่อยของเมทริกซ์ความประชิดที่มีมิติซึ่งสามารถมองเห็นได้ใน รูปแบบ ตารางหมากรุกในเมทริกซ์^{[ 12 ]}ดังนั้น หน่วยประมวลผลแต่ละหน่วยจึงสามารถมีขอบขาออกไปยัง PE ในแถวและคอลัมน์เดียวกันเท่านั้น ซึ่งจำกัดจำนวนคู่ค้าการสื่อสารสำหรับ PE แต่ละตัวไว้ที่ จากจำนวนที่เป็นไปได้ทั้งหมด ${\displaystyle p=p_{r}\times p_{c}}$${\displaystyle p_{r}}$${\displaystyle p_{c}}$${\displaystyle (n/p_{r})\times (n/p_{c})}$${\displaystyle p_{r}+p_{c}-1}$${\displaystyle p=p_{r}\times p_{c}}$

กราฟที่มีขอบหลายล้านล้านเส้นเกิดขึ้นใน การเรียนรู้ ของเครื่องการวิเคราะห์เครือข่ายสังคมและสาขาอื่นๆ มีการพัฒนารูปแบบกราฟ แบบบีบอัดเพื่อลดความต้องการ I/O และหน่วยความจำ เทคนิคทั่วไป เช่นการเข้ารหัส Huffmanสามารถนำมาใช้ได้ แต่รายการความสัมพันธ์หรือเมทริกซ์ความสัมพันธ์สามารถประมวลผลได้ด้วยวิธีเฉพาะเพื่อเพิ่มประสิทธิภาพ^{[ 13 ]}

การค้นหาแบบกว้าง (BFS) และการค้นหาแบบลึก (DFS) เป็นสองแนวทางที่เกี่ยวข้องกันอย่างใกล้ชิดซึ่งใช้ในการสำรวจโหนดทั้งหมดในส่วนประกอบที่เชื่อมต่อ กันที่กำหนด ทั้งสองเริ่มต้นด้วยโหนดที่กำหนด ซึ่งก็คือ " ราก " ^{[ 14 ]}ส่วนประกอบที่เชื่อมต่อกันอย่างแน่นหนายังสามารถค้นพบได้โดยใช้การสำรวจกราฟโดยใช้อัลกอริทึม เช่นอัลกอริทึมของ Kosarajuซึ่งเป็น DFS ที่ได้รับการดัดแปลง

อัลกอริทึมของไดจ์กสตรา (Dijkstra's Algorithm)เป็นอัลกอริทึมการค้นหาเส้นทางที่สามารถใช้ได้กับกราฟที่มีน้ำหนักเป็นบวก (หมายความว่าน้ำหนักของขอบทั้งหมดต้องมากกว่าหรือเท่ากับ 0) และ/หรือกราฟแบบมีทิศทาง สามารถใช้เพื่อค้นหาเส้นทางที่สั้นที่สุดระหว่างโหนดสองโหนดที่เลือกไว้โดยพลการ ซึ่งมักใช้ในปัญหาการกำหนดเส้นทาง

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

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับกราฟ (ประเภทข้อมูลนามธรรม )

• Boost Graph Library: ไลบรารีสำหรับสร้างกราฟที่มีประสิทธิภาพสูงในภาษา C++ sa Boost (ไลบรารี C++)
• Networkx: ไลบรารีสำหรับสร้างกราฟด้วยภาษา Python
• GraphMatcherเป็นโปรแกรม Java สำหรับจัดเรียงกราฟแบบมีทิศทางและไม่มีทิศทาง
• GraphBLASคือข้อกำหนดสำหรับอินเทอร์เฟซไลบรารีสำหรับการดำเนินการบนกราฟ โดยเน้นเป็นพิเศษที่กราฟแบบเบาบาง