fbpx
วิกิพีเดีย

เมตริกซ์ประชิด

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

การแทนที่กราฟด้วยเมตริกซ์

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

กราฟระบุทิศทาง

 
รูปที่ 2

จากรูปที่ 2 หากนำมาแทนที่ด้วยเมตริกซ์จะแทนที่ได้ด้วยจำนวน n x n ซึ่ง n ก็คือ A,B,C,D,E,F เป็น 6 จำนวน โหนดทำให้ได้ค่าเมตริกซ์ จำนวน 6 x 6 = 36 ช่อง และเมื่อพิจารณาตามทิศทางของการเชื่อมต่อ หากโหนดใดมีเส้นเชื่อมต่อไปยังโหนดอื่นให้ระบุตัวเลขลงไปในเมตริกซ์เป็น 1 แต่ถ้าโหนดใดไม่ได้มีการระบุว่าทำการเชื่อมต่อก็ให้ระบุเป็น 0 ดังรูปภาพที่ 3

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

พิจารณาโหนด A มีเส้นเชื่อมต่อระบุไป B ระบุหมายเลข 1 นอกนั้นระบุค่าเป็น 0

พิจารณาโหนด B มีเส้นเชื่อมต่อระบุไป C, E ระบุหมายเลข 1 นอกนั้นระบุค่าเป็น 0

 
รูปที่ 3

พิจารณาโหนด C มีเส้นเชื่อมต่อระบุไป D, E ระบุหมายเลข 1 นอกนั้นระบุค่าเป็น 0

พิจารณาโหนด D ไม่มีเส้นเชื่อมต่อระบุไปยังโหนดอื่นระบุหมายเลข 0 ทุกช่อง

พิจารณาโหนด E มีเส้นเชื่อมต่อระบุไป D, F ระบุหมายเลข 1 นอกนั้นระบุค่าเป็น 0

พิจารณาโหนด F ไม่มีเส้นเชื่อมต่อระบุไปยังโหนดอื่นระบุหมายเลข 0 ทุกช่อง

กราฟไม่ระบุทิศทาง

 
รูปที่ 4

จากรูปภาพที่ 4 กราฟแบบไม่ระบุทิศทางเมื่อนำมาแทนที่ด้วยเมตริกซ์สามารถที่จะกำหนดจำนวนช่องได้เช่นเดียวกับไดกราฟ คือ n x nและระบุตัวเลขสำหรับการเชื่อมต่อ คือ 1 และ 0 แต่ในการวางตำแหน่งโหนดในแนวนอน และแนวตั้งนั้น ระบุเป็นโหนดต้นทางและโหนดปลายทางได้ในตัวเดียวกัน ในรูปภาพที่ 5

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

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

โหนด B มีเส้นเชื่อมต่อ A, C, E ได้ระบุเป็น 1 และ A, C, E ระบุช่องโหนด B เป็น 1 เช่นกัน โหนด C มีเส้นเชื่อมต่อ B, D, E ได้ระบุเป็น 1 และ B, D, E ระบุช่องโหนด C เป็น 1 เช่นกัน

โหนด D มีเส้นเชื่อมต่อ C, E ได้ระบุเป็น 1 และ C, E ระบุช่องโหนด Dเป็น 1 เช่นกัน

 
รูปที่ 5

โหนด E มีเส้นเชื่อมต่อ B, C, D, F ได้ระบุเป็น 1 และ B, C, D, F ระบุช่องโหนด ฎ เป็น 1 เช่นกัน

โหนด F มีเส้นเชื่อมต่อ E ได้ระบุเป็น 1 และ E ระบุช่องโหนด F เป็น 1 เช่นกัน

กรณีที่กราฟมีการวนลูป(Loop)

ในกรณีที่ีกราฟมีการวนลูป ในภาพที่ 6 จะแทนค่าตำแหน่งที่มีการวนลูปเป็นเลข 2

 
รูปที่ 6

การจัดเก็บโครงสร้างกราฟด้วย Adjacency Matrix

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

รูป (ข) แสดงการจัดเก็บโครงสร้างกราฟแบบไม่มีทิศทางของกราฟในรูป (ก) โดยแถวที่ 1 ของอาร์เรย์ X แสดงการเชื่อมโยงจากจุดยอด a ไปยังจุดยอดอื่นๆ ที่เป็นจุดยอดใกล้เคียง เช่น จุดยอด a เชื่อมโยงไปยังจุดยอด b c และ d ดังนั้น ค่า  และ  จะมีค่าเป็น 1 ส่วนแถวที่ 2-4 แสดงการเชื่อมโยงจากจุดยอด b c หรือ d ไปยังจุดยอดอิ่นๆ ตามลำดับ ซึ่งการแทนกราฟแบบไม่มีทิศทาง ลักษณะของอาร์เรย์สองมิติที่ได้จะมีลักษณะสมมาตร (Symmetric) เรียกว่า เมทริกซ์ทแยงมุม (Diagonal Matrix) นั่นคือ ค่าของ   ซึ่งเป็นค่าที่แสดงความสัมพันธ์ระหว่างจุดยอด i และจุดยอด j ว่ามีเส้นเชื่อมโยงถึงกัน ดังนั้น จำนวนช่อง   ที่มีค่าเท่ากับ 1 จะเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ แต่หากเป็นกราฟแบบมีทิศทาง จำนวนช่อง   ที่มีค่าเท่ากับ 1 จะเท่ากับจำนวนเส้นเชื่อมในกราฟ เช่น   และ  จะเก็บค่า 1 หมายถึงมีเส้นเชื่อมโยงระหว่างจุดยอด a และจุดยอด d นั่นเอง

ตัวอย่างโค้ดในภาษา python

class Graph(object): def __init__(self, edge_list): self.edge_list = edge_list def add_edge(self, edge_list): self.edge_list.append(edge_list) def adj_mtx_diect(self): v = 0 counter = set() for src, dest in self.edge_list:  counter.add(src)  counter.add(dest) v = len(counter) mtx = [[0 for y in range(v)]for x in range(v)] for e in self.edge_list:  src, dest = e  src = src - 1  dest = dest - 1  if src == dest:  mtx[src][dest] = 2  else:  mtx[src][dest] = 1 return mtx def adj_mtx_undiect(self): v = 0 counter = set() for src, dest in self.edge_list:  counter.add(src)  counter.add(dest) v = len(counter) mtx = [[0 for y in range(v)]for x in range(v)] for e in self.edge_list:  src, dest = e  src = src - 1  dest = dest - 1  if src == dest:  mtx[src][dest] = 2  mtx[dest][src] = 2  else:  mtx[src][dest] = 1  mtx[dest][src] = 1 return mtx 

อ้างอิง

เมตร, กซ, ประช, แมทร, กซ, ประช, adjacency, matrix, จะใช, เวกเตอร, อาร, เรย, หน, งม, เพ, อจ, ดเก, บเวอร, เท, กซ, และใช, แมทร, กซ, อาร, เรย, สองม, เพ, อจ, ดเก, บเอดจ, าหากเวอร, เท, ฏซ, หน, งอย, ประช, ดก, นและม, เอดจ, เช, อมโยงระหว, างเวอร, เท, กซ, แมทร, กค, นจะม. aemthriksprachid Adjacency Matrix caichewketxr xareryhnungmiti ephuxcdekbewxrethksaelaichaemthriks xarerysxngmiti ephuxcdekbexdc thahakewxrethtskhuhnungxyuprachidknaelamiexdcechuxmoyngrahwangewxrethkskhunn aemthrikkhunncamikhaepn 1 inkhnathihakimmiexdcechuxmoyngnnhmaythungimmiesnthangrahwangkn aemthrikkhunnkcathukkahndih mikhaethakb 0 inkrniepnkrafaebbmithisthanghruxidkraf aemthriksprachidcamiluksrepntwkahndthisthang 1 2 enuxha 1 karaethnthikrafdwyemtriks 1 1 krafrabuthisthang 1 2 krafimrabuthisthang 1 2 1 krnithikrafmikarwnlup Loop 2 karcdekbokhrngsrangkrafdwy Adjacency Matrix 3 twxyangokhdinphasa python 4 xangxingkaraethnthikrafdwyemtriks aekikhokhrngsrangkhxngkrafepnokhrngsrangthiprakxbipdwyohndaelaesnechuxmtxthibxkthungesnthangkhxngkaredinthang hruxkhwamsmphnthinthisthangsungsamarthnamaaethnkhwamsmphnthnndwyemtriksiddwykarkahndemtriks n x n krafrabuthisthang aekikh rupthi 2 3 cakrupthi 2 haknamaaethnthidwyemtrikscaaethnthiiddwycanwn n x n sung n kkhux A B C D E F epn 6 canwn ohndthaihidkhaemtriks canwn 6 x 6 36 chxng aelaemuxphicarnatamthisthangkhxngkarechuxmtx hakohndidmiesnechuxmtxipyngohndxunihrabutwelkhlngipinemtriksepn 1 aetthaohndidimidmikarrabuwathakarechuxmtxkihrabuepn 0 dngrupphaphthi 3aethnthiemtriksdwycanwnohndthngdanaenwtngaelaaenwnxnodykahndihaenwnxnepnohndtnthangaelaaenwtngepnohndplaythang samarthekhiynelkhladbemtriksodyrabukhadngniphicarnaohnd A miesnechuxmtxrabuip B rabuhmayelkh 1 nxknnrabukhaepn 0phicarnaohnd B miesnechuxmtxrabuip C E rabuhmayelkh 1 nxknnrabukhaepn 0 rupthi 3 4 phicarnaohnd C miesnechuxmtxrabuip D E rabuhmayelkh 1 nxknnrabukhaepn 0phicarnaohnd D immiesnechuxmtxrabuipyngohndxunrabuhmayelkh 0 thukchxngphicarnaohnd E miesnechuxmtxrabuip D F rabuhmayelkh 1 nxknnrabukhaepn 0phicarnaohnd F immiesnechuxmtxrabuipyngohndxunrabuhmayelkh 0 thukchxng krafimrabuthisthang aekikh rupthi 4 5 cakrupphaphthi 4 krafaebbimrabuthisthangemuxnamaaethnthidwyemtrikssamarththicakahndcanwnchxngidechnediywkbidkraf khux n x naelarabutwelkhsahrbkarechuxmtx khux 1 aela 0 aetinkarwangtaaehnngohndinaenwnxn aelaaenwtngnn rabuepnohndtnthangaelaohndplaythangidintwediywkn inrupphaphthi 5cakrupthi 5 epnkarkahndekhiynelkhkakbemtriksodyxankhathngaenwtngaelaaenwnxn echnohnd A miesnechuxmtx thirabuipyngohnd B idaelaechnknohnd Bsamarththicaechuxmtxmayngohnd A id cungrabutwelkhinemtriksepn1ohnd B miesnechuxmtx A C E idrabuepn 1 aela A C E rabuchxngohnd B epn 1 echnkn ohnd C miesnechuxmtx B D E idrabuepn 1 aela B D E rabuchxngohnd C epn 1 echnknohnd D miesnechuxmtx C E idrabuepn 1 aela C E rabuchxngohnd Depn 1 echnkn rupthi 5 6 ohnd E miesnechuxmtx B C D F idrabuepn 1 aela B C D F rabuchxngohnd d epn 1 echnknohnd F miesnechuxmtx E idrabuepn 1 aela E rabuchxngohnd F epn 1 echnkn krnithikrafmikarwnlup Loop aekikh inkrnithiikrafmikarwnlup inphaphthi 6 caaethnkhataaehnngthimikarwnlupepnelkh 2 rupthi 6karcdekbokhrngsrangkrafdwy Adjacency Matrix aekikhwithikarxyangngayinkarcdekbokhrngsrangkraf khux xarerysxngmitithiekbkhwamsmphnthrahwangcudyxdiklekhiynginkraf eriykwa aexdcaesnsiemtriks Adjacency Matrix odyhakkrafprakxbdwycudyxd v 1 v 2 v 3 v n displaystyle v 1 v 2 v 3 v n casamarthaesdngkrafinrupkhxngaexdcaesnsiemtriks X khnad n x n ody x i j 1 displaystyle x ij 1 inkrnimiesnechuxmrahwangcudyxd v i displaystyle v i aela v j displaystyle v j aela x i j 0 displaystyle x ij 0 inkrniimmiesnechuxmrahwangcudyxd v i displaystyle v i aela v j displaystyle v j aela i j n displaystyle i j leqslant n 7 rup kh aesdngkarcdekbokhrngsrangkrafaebbimmithisthangkhxngkrafinrup k odyaethwthi 1 khxngxarery X aesdngkarechuxmoyngcakcudyxd a ipyngcudyxdxun thiepncudyxdiklekhiyng echn cudyxd a echuxmoyngipyngcudyxd b c aela d dngnn kha x 12 x 13 displaystyle x 12 x 13 aela x 14 displaystyle x 14 camikhaepn 1 swnaethwthi 2 4 aesdngkarechuxmoyngcakcudyxd b c hrux d ipyngcudyxdxin tamladb sungkaraethnkrafaebbimmithisthang lksnakhxngxarerysxngmitithiidcamilksnasmmatr Symmetric eriykwa emthriksthaeyngmum Diagonal Matrix nnkhux khakhxng x i j x j i displaystyle x ij x ji sungepnkhathiaesdngkhwamsmphnthrahwangcudyxd i aelacudyxd j wamiesnechuxmoyngthungkn dngnn canwnchxng x i j displaystyle x ij thimikhaethakb 1 caethakbsxngethakhxngcanwnesnechuxminkraf aethakepnkrafaebbmithisthang canwnchxng x i j displaystyle x ij thimikhaethakb 1 caethakbcanwnesnechuxminkraf echn x 14 displaystyle x 14 aela x 41 displaystyle x 41 caekbkha 1 hmaythungmiesnechuxmoyngrahwangcudyxd a aelacudyxd d nnexng 8 twxyangokhdinphasa python aekikhclass Graph object def init self edge list self edge list edge list def add edge self edge list self edge list append edge list def adj mtx diect self v 0 counter set for src dest in self edge list counter add src counter add dest v len counter mtx 0 for y in range v for x in range v for e in self edge list src dest e src src 1 dest dest 1 if src dest mtx src dest 2 else mtx src dest 1 return mtx def adj mtx undiect self v 0 counter set for src dest in self edge list counter add src counter add dest v len counter mtx 0 for y in range v for x in range v for e in self edge list src dest e src src 1 dest dest 1 if src dest mtx src dest 2 mtx dest src 2 else mtx src dest 1 mtx dest src 1 return mtxxangxing aekikh http agritech pcru ac th new page e learningdata 7 5Storage php rupthi 1 https www slideshare net tumetr graph 43943214 http piyapan aod blogspot com 2009 03 graph html https stackoverflow com questions 29464252 adjacency matrix in python https algocoding wordpress com 2014 08 24 adjacency list representation of a graph python java https pythonandr com tag adjacency matrix http btechsmartclass com DS U3 T9 html http www cs science cmu ac th 88 course 204251 lib exe fetch php media graph pdfekhathungcak https th wikipedia org w index php title emtriksprachid amp oldid 9211908, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,

บทความ

, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม