II. GRAPH REPRESENTATIONS USING COM

II. GRAPH REPRESENTATIONS USING
COMPUTER SYSTEMS
In general, there are four ways to represent a
graph in a computer system: The incidence list
representation, the incidence matrix representation,
adjacency list representation, and the adjacency
matrix representation.
Incidence List - This representation uses an
array. Each element in the array corresponds with a
single edge. Each edge contains a list of size two
which corresponds to the endpoints of the edge.
This can also apply to directed graphs by ensuring
the first vertex be defined as the source or
destination while the second should be defined as
the opposite.
Incidence matrix - This representation uses a
matrix of M edges by N vertices. If the vertex is an
endpoint to the edge, a value of 1 is assigned to
their crossing, otherwise, a value of 0 is assigned.
This is a terrible waste of space as every column or
row represented by the edge can only have two
values of 1 while the rest are labelled 0.

These two representations are most useful when
information about edges is more desirable than
information about vertices.
Adjacency list - Much like the incidence list,
each node has a list of which nodes it is adjacent
to. This can sometimes result in "overkill" in an
undirected graph as vertex 3 may be in the list for
node 2, then node 2 must be in the list for node 3.
Either the programmer may choose to use the
unneeded space anyway, or he/she may choose to
list the adjacency once. This representation is
easier to find all the nodes which are connected to
a single node, since these are explicitly listed.
Adjacency matrix - there is an N by N matrix,
where N is the total number of vertices in the
graph. If there is an edge from some vertex x to
some vertex y, then the element Mx,y would be 1,
otherwise it would be 0. This makes it easier to
find sub graphs, and to reverse graphs if needed.
[6].
These two representations are most useful when
information about the vertices is more desirable
than information about the edges. Also these two
representations are also most popular since
information about the vertices is often more
desirable than edges in most applications. [7].

ผลลัพธ์ (ไทย) 1:

ii แสดงกราฟการใช้ระบบคอมพิวเตอร์

โดยทั่วไปมีสี่วิธีที่จะเป็นตัวแทนของกราฟ
ในระบบคอมพิวเตอร์ที่อยู่: รายการอุบัติการณ์การเป็นตัวแทน
แทนเมทริกซ์อุบัติการณ์
แทนรายการถ้อยคำและถ้อยคำ
แทนเมทริกซ์ รายการอุบัติ
- การแสดงนี้ใช้อาร์เรย์
องค์ประกอบในอาร์เรย์แต่ละสอดคล้องกับขอบเดียว
ขอบแต่ละรายการมีขนาดสอง
ซึ่งสอดคล้องกับจุดสิ้นสุดของขอบ
นี้ยังสามารถนำไปใช้กับกราฟกำกับโดยมั่นใจ
จุดยอดแรกถูกกำหนดเป็นแหล่งที่มาหรือปลายทาง
ขณะที่สองควรจะกำหนดเป็น
ตรงข้าม เมทริกซ์อุบัติ
- การแสดงนี้ใช้เมทริกซ์
ของขอบ m ด้วย n จุด ถ้าจุดยอดเป็นจุดสิ้นสุด
ไปที่ขอบ,ค่า 1 ได้รับมอบหมายให้
ข้ามของพวกเขามิฉะนั้นค่าเป็น 0 ได้รับมอบหมาย
นี้เป็นของเสียที่แย่มากของพื้นที่เป็นทุกคอลัมน์หรือแถว
ตัวแทนจากขอบสามารถมีสองค่า
จาก 1 ในขณะที่ส่วนที่เหลือจะมีป้ายกำกับ 0.

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

รายการถ้อยคำ - มากเช่นรายการอุบัติการณ์,
แต่ละโหนดมีรายชื่อของโหนดซึ่งมันเป็น
ที่อยู่ติดกับ นี้บางครั้งอาจทำให้ "overkill" ในกราฟไม่มีทิศทาง
เป็นจุดสุดยอด 3 พฤษภาคมจะอยู่ในรายการสำหรับโหนด
2 แล้วโหนด 2 จะต้องอยู่ในรายการสำหรับโหนด 3
ทั้งโปรแกรมเมอร์อาจเลือกที่จะใช้
พื้นที่ที่ไม่จำเป็นแล้วหรือเขา / เธออาจเลือกที่จะรายการ
ถ้อยคำอีกครั้งการแสดงนี้เป็น
ง่ายต่อการค้นหาโหนดทั้งหมดที่เชื่อมต่อกับ
โหนดเดียวตั้งแต่เหล่านี้จะปรากฏอย่างชัดเจน เมทริกซ์ถ้อยคำ
- มี n โดย n เมทริกซ์คือ
ที่ n คือจำนวนของจุดในกราฟ
ถ้ามีขอบ x จากจุดสุดยอดบางอย่างเพื่อให้ y
บางจุดสุดยอดแล้ว MX องค์ประกอบ y จะเป็น 1,
มิฉะนั้นก็จะเป็น 0 นี้จะทำให้ง่ายต่อ
หากราฟย่อยและจะย้อนกลับกราฟถ้าจำเป็น
[6]
สองคนนี้เป็นตัวแทนที่มีประโยชน์มากที่สุดเมื่อข้อมูลเกี่ยวกับจุด

เป็นที่ต้องการมากขึ้นกว่าข้อมูลเกี่ยวกับขอบ นอกจากนี้ยังมีสองคนนี้เป็นตัวแทน
ยังเป็นที่นิยมมากที่สุดนับตั้งแต่ข้อมูลเกี่ยวกับจุด

มักจะเป็นที่น่าพอใจมากขึ้นกว่าขอบในการใช้งานมากที่สุด [7]

ผลลัพธ์ (ไทย) 2:

ใช้แทน II กราฟ
ระบบคอมพิวเตอร์
มีสี่วิธีถึงทั่วไป การ
กราฟในระบบคอมพิวเตอร์: รายอุบัติการณ์
แสดง แสดงเมตริกซ์อุบัติการณ์,
adjacency แสดงรายการ และแบบ adjacency
แสดงเมตริกซ์
เกิดรายการ - แสดงนี้ใช้การ
เรย์ แต่ละสมาชิกในอาร์เรย์ที่ตรงกับ
เดี่ยวขอบ ขอบแต่ละประกอบด้วยรายการของขนาดสอง
ซึ่งตรงกับปลายของขอบ
นี้ยังสามารถใช้กับกราฟโดยตรง โดยใจ
กำหนดจุดแรกเป็นแหล่ง หรือ
ปลายทางในขณะที่สองควรจะเป็น
ตรงข้ามได้
เกิดเมทริกซ์ - แสดงนี้ใช้กับ
เมตริกซ์ M edges โดยจุดยอด N ถ้าจุดผิด
ปลายขอบ มีกำหนดค่า 1
การข้าม อื่น ค่า 0 ไว้
เป็นของพื้นที่ที่เป็นคอลัมน์ทุกเสียน่ากลัว หรือ
แทน ด้วยขอบแถวได้เพียงสอง
ค่า 1 ขณะเหลือถูก labelled 0 ได้

แทนสองเหล่านี้มีประโยชน์มากที่สุดเมื่อ
ข้อมูลเกี่ยวกับขอบจะเหมาะกว่า
ข้อมูลเกี่ยวกับจุดยอดได้
รายการ adjacency - เหมือนรายอุบัติการณ์,
แต่ละโหนมีรายการของโหนดที่อยู่ติดกับ
จะ นี้ผลใน "overkill" การ
undirected กราฟเป็นจุดยอด 3 อาจจะในรายการ
โหน 2 แล้วโหน 2 ต้องอยู่ในรายการของโหนด 3
ทั้งโปรแกรมเมอร์อาจเลือกใช้การ
จำพื้นที่ต่อไป หรือเขาอาจเลือกที่จะ
รายการแบบ adjacency ครั้ง การแสดงนี้เป็น
ง่ายต่อการค้นหาโหนทั้งหมดที่เชื่อมต่อกับ
โหนเดียว เนื่องจากนี้มีการระบุไว้อย่างชัดเจน
Adjacency เมทริกซ์ - มีเมทริกซ์การ N โดย N,
โดยที่ N คือ จำนวนของจุดยอดในการ
กราฟ ถ้ามีขอบจากบางจุดยอด x เพื่อ
y บางจุด แล้ว Mx องค์ประกอบ y จะ 1,
มิฉะนั้น มันจะเป็น 0 นี้ช่วยให้
ค้นหากราฟย่อย และกลับกราฟถ้าจำเป็น
[6].
นำเสนอสองเหล่านี้มีประโยชน์มากที่สุดเมื่อ
เป็นมากขึ้นต้องการข้อมูลเกี่ยวกับจุดยอด
กว่าข้อมูลเกี่ยวกับขอบ ยังสอง
แทนยังเป็นที่นิยมมากที่สุดตั้งแต่
ข้อมูลเกี่ยวกับจุดยอดมักมีมากกว่า
เหมาะกว่าขอบในโปรแกรมส่วนใหญ่ [7]

ผลลัพธ์ (ไทย) 3:

II กราฟการรับรองโดยใช้

ในระบบคอมพิวเตอร์โดยทั่วไปมีสี่วิธีในการเป็นตัวแทน
กราฟที่อยู่ในระบบคอมพิวเตอร์ที่รายการการตกที่
การเป็นตัวแทนการแสดงตารางการแสดงรายการ
อยู่ใกล้ชิดและเป็นตัวแทนอยู่ใกล้ชิด
matrix . รายการ
อุบัติการณ์ - การแสดงนี้ใช้
ที่หลากหลาย แต่ละองค์ประกอบในความหลากหลายที่ตรงกับขอบตัวเดียว
ขอบแต่ละชุดประกอบด้วยรายการที่มีขนาดสอง
ซึ่งตรงกับอุปกรณ์ปลายทางที่มีลักษณะเป็นเส้นขอบที่ต่อกันได้
นี้สามารถใช้กับกราฟโดยตรงโดยมั่นใจได้ว่า
ยอดเป็นครั้งแรกที่ได้รับการกำหนดไว้เป็นแหล่งที่มาหรือ
ปลายทางในขณะที่ที่สองที่จะได้รับการกำหนดไว้เป็นทางฝั่งด้านตรงข้ามกับ
ยัง
การตก Matrix Storage - การแสดงนี้ใช้
Matrix Storage ของขอบม.โดยยอด n หากยอดที่มี
อุปกรณ์ปลายทางที่ไปยังขอบค่าของ 1 ถูกกำหนดให้กับ
ของพวกเขาข้ามผ่านมิฉะนั้นค่าที่ 0 มีการมอบหมาย
นี้เป็นที่น่าสยดสยองขยะของพื้นที่เป็นทุกคอลัมน์หรือแถว
แสดงโดยขอบสามารถมีเพียงสอง
ค่าของ 1 ในขณะที่ส่วนที่เหลือจะมีป้าย 0 .

สองคนนี้รับรองมีประโยชน์มากที่สุดเมื่อ
ข้อมูลเกี่ยวกับขอบเป็นที่พึงปรารถนามากกว่า
ข้อมูลเกี่ยวกับยอด.
อยู่ใกล้ชิดรายการ - เหมือนกับรายการปัญหา
โหนดแต่ละห้องมีรายการที่โหนดนั้นอยู่ใกล้
เพื่อ โรงแรมแห่งนี้สามารถส่งผลให้ใน" overkill "ในกราฟ
Darwin เป็นยอด 3 อาจจะอยู่ในรายการนี้สำหรับ 2
โหนดในบางครั้งแล้วโหนด 2 ต้องอยู่ในรายการสำหรับโหนด 3
ทั้งเครื่องตั้งโปรแกรมที่อาจเลือกที่จะใช้พื้นที่
ไม่จำเป็นหรือไม่หรือเขา/เธออาจเลือกที่จะ
รายการอยู่ใกล้ชิดเมื่อการแสดงนี้คือ
ง่ายต่อการค้นหาโหนดทั้งหมดซึ่งมีการเชื่อมต่อไปยังโหนดเดียว
เนื่องจากเหล่านี้มีอยู่ในรายการอย่างชัดเจน
อยู่ใกล้ชิด Matrix Storage - มี Matrix Storage n โดย n ที่
โดยที่ n คือจำนวนรวมของยอดใน
กราฟแสดงให้ หากมีลักษณะเป็นเส้นขอบที่ต่อกันจากลักษณะพิเศษ Vertex X เพื่อ
บาง Y ยอดบางส่วนแล้ว MX Y องค์ประกอบที่จะอยู่ที่ 1
หรือมิเช่นนั้นแล้วจะเป็น 0 โรงแรมแห่งนี้จะทำให้ง่ายขึ้นกราฟการย่อย
ค้นหาและเพื่อการย้อนกลับกราฟหากจำเป็น.
[ 6 ].
สองการรับรองนี้มีประโยชน์มากที่สุดเมื่อ
ข้อมูลเกี่ยวกับยอดที่เป็นที่พึงปรารถนา
กว่าข้อมูลเกี่ยวกับขอบ ทั้งสอง
รับรองเหล่านี้ยังได้รับความนิยมมากที่สุดนับตั้งแต่
ข้อมูลเกี่ยวกับยอดที่มักมี
ที่พึงปรารถนามากกว่าขอบในแอปพลิเคชันส่วนใหญ่ [ 7 ].