در نظریه گراف، ماتریس مجاورت روشی برای توصیف ساختار گراف متناهی است. این ماتریس، دو بعدی است و برای ترسیم ارتباط بین گره‌های گراف استفاده می‌شود.
نمایش گراف
در حالت کلی دو روش رایج برای نشان دادن یک گراف وجود دارد:
ماتریس مجاورت
یک ماتریس مجاورت یک گراف را به عنوان ماتریس بولی (0 و 1) نشان می‌دهد.
لیست مجاورت
در این روش، آرایه ای از لیست ها برای ذخیره یال‌های بین دو راس استفاده می‌شود. اندازه آرایه برابر با تعداد رئوس (یعنی n) است. هر شاخص در این آرایه نشان‌دهنده یک راس خاص در نمودار است. ورودی در فهرست i آرایه حاوی یک لیست پیوندی حاوی رئوس مجاور راس i است. در این مقاله ما به نحوه نمایش گراف با ماتریس مجاورت می‌پردازیم.
ساختار ماتریس مجاورت
یک ماتریس مجاورت، یک گراف را به عنوان ماتریسی از مقادیر بولی (0 و 1) نشان می‌دهد. یک گراف متناهی را می‌توان به شکل یک ماتریس مربعی در کامپیوتر نشان داد، جایی که مقدار بولی ماتریس نشان می‌دهد که آیا یک مسیر مستقیم بین دو راس وجود دارد یا خیر.
به عنوان مثال، گراف زیر را در نظر بگیرید:
ما می‌توانیم این گراف را به شکل ماتریسی مانند زیر نمایش دهیم:
هر سلول در جدول/ماتریس بالا به صورت Aij نشان داده می‌شود که i و j رئوس هستند. مقدار Aij یا 1 یا 0 است، بسته به اینکه آیا یک یال از راس i تا راس j وجود دارد.
اگر یالی از i به j وجود داشته باشد، مقدار Aij یک است؛ درغیراین صورت صفر است. برای مثال، یک یال از راس 1 به راس 2 وجود دارد، بنابراین A12 یک است و هیچ یالی از راس 1 تا 3 وجود ندارد، همچنین A13 صفر است. در گراف‌های بدون جهت، ماتریس نسبت به قطر متقارن است.
پیاده سازی
در ادامه به پیاده سازی ماتریس مجاورت با زبان های برنامه نویسی مانند پایتون، جاوا ،سی پلاس پلاس و C می‌پردازیم:
Python
class Graph(object):
# Initialize the matrix
def __init__(self, size):
self.adjMatrix = []
for i in range(size):
self.adjMatrix.append([0 for i in range(size)])
self.size = size
# Add edges
def add_edge(self, v1, v2):
if v1 == v2:
print("Same vertex %d and %d" % (v1, v2))
self.adjMatrix[v1][v2] = 1
self.adjMatrix[v2][v1] = 1
# Remove edges
def remove_edge(self, v1, v2):
if self.adjMatrix[v1][v2] == 0:
print("No edge between %d and %d" % (v1, v2))
return
self.adjMatrix[v1][v2] = 0
self.adjMatrix[v2][v1] = 0
def __len__(self):
return self.size
# Print the matrix
def print_matrix(self):
for row in self.adjMatrix:
for val in row:
print("{:4}".format(val)),
print
def main():
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.print_matrix()
if __name__ == "__main__":
main()
Java
public class Graph {
private boolean adjMatrix[][];
private int numVertices;
// Initialize the matrix
public Graph(int numVertices) {
this.numVertices = numVertices;
adjMatrix = new boolean[numVertices][numVertices];
}
// Add edges
public void addEdge(int i, int j) {
adjMatrix[i][j] = true;
adjMatrix[j][i] = true;
}
// Remove edges
public void removeEdge(int i, int j) {
adjMatrix[i][j] = false;
adjMatrix[j][i] = false;
}
// Print the matrix
public String toString() {
StringBuilder s = new StringBuilder();
for (int i = 0; i numVertices; i++) {
s.append(i + ": ");
for (boolean j : adjMatrix[i]) {
s.append((j ? 1 : 0) + " ");
}
s.append("\n");
}
return s.toString();
}
public static void main(String args[]) {
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
System.out.print(g.toString());
}
}
C++
#include
using namespace std;
class Graph
{
private:
bool **adjMatrix;
int numVertices;
public:
// Initialize the matrix to zero
Graph(int numVertices)
{
this->numVertices = numVertices;
adjMatrix = new bool *[numVertices];
for (int i = 0; i numVertices; i++)
{
adjMatrix[i] = new bool[numVertices];
for (int j = 0; j numVertices; j++)
adjMatrix[i][j] = false;
}
}
// Add edges
void addEdge(int i, int j)
{
adjMatrix[i][j] = true;
adjMatrix[j][i] = true;
}
// Remove edges
void removeEdge(int i, int j)
{
adjMatrix[i][j] = false;
adjMatrix[j][i] = false;
}
// Print the martix
void toString()
{
for (int i = 0; i numVertices; i++)
{
cout i " : ";
for (int j = 0; j numVertices; j++)
cout adjMatrix[i][j] " ";
cout "\n";
}
}
~Graph()
{
for (int i = 0; i numVertices; i++)
delete[] adjMatrix[i];
delete[] adjMatrix;
}
};
int main()
{
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.toString();
}
C
// Adjacency Matrix representation in C
#include
#define V 4
// Initialize the matrix to zero
void init(int arr[][V])
{
int i, j;
for (i = 0; i V; i++)
for (j = 0; j V; j++)
arr[i][j] = 0;
}
// Add edges
void addEdge(int arr[][V], int i, int j)
{
arr[i][j] = 1;
arr[j][i] = 1;
}
// Print the matrix
void printAdjMatrix(int arr[][V])
{
int i, j;
for (i = 0; i V; i++)
{
printf("%d: ", i);
for (j = 0; j V; j++)
{
printf("%d ", arr[i][j]);
}
printf("\n");
}
}
int main()
{
int adjMatrix[V][V];
init(adjMatrix);
addEdge(adjMatrix, 0, 1);
addEdge(adjMatrix, 0, 2);
addEdge(adjMatrix, 1, 2);
addEdge(adjMatrix, 2, 0);
addEdge(adjMatrix, 2, 3);
printAdjMatrix(adjMatrix);
return 0;
}
مزایا و معایب ماتریس مجاورت
حال که با ماتریس مجاورت و پیاده‌سازی آن آشنا شدیم، به بررسی مزایا و معایب این شیوه نمایش گراف می‌پردازیم.
مزایا
- عملیات اساسی مانند اضافه کردن یک یال، حذف یک یال و بررسی اینکه آیا یک یال از راس i به راس j وجود دارد، از مرتبه زمانی ثابت و بسیار بهینه است.
- اگر گراف متراکم و تعداد یال‌ها زیاد باشد، یک ماتریس مجاورت باید اولین انتخاب باشد حتی اگر گراف و ماتریس مجاورت پراکنده باشند، می‌توانیم آنها را با استفاده از ساختمان داده هایی که برای ماتریس‌های پراکنده مناسب‌اند نشان دهیم.
- پیشرفت‌های اخیر در سخت افزار ما را قادر می‌سازد تا عملیات‌های ماتریسی زمانبر را بر روی پردازنده گرافیکی (GPU) انجام دهیم.
- با انجام عملیات روی ماتریس مجاورت، می‌توانیم بینش‌های مهمی در مورد ماهیت گراف و رابطه بین رئوس آن بدست آوریم.
معایب
- فضای مورد نیاز VxV ماتریس مجاورت، باعث می‌شود که از نظر حافظه بهینه نباشد. گراف‌های موجود در طبیعت معمولاً اتصالات زیادی ندارند، به همین دلیل است که لیست های مجاورت برای اکثر موارد انتخاب بهتری هستند.
- در مورد استفاده از فضا برای گراف‌های پراکنده ناکارآمد است زیرا فضای O(N2) را اشغال می‌کند.
- محاسبه همه همسایگان یک راس، زمان O(N) دارد.
کاربردها
از کاربرد های ماتریس مجاورت می‌توان به موارد زیر اشاره کرد:
- الگوریتم های گراف: بسیاری از الگوریتم‌های گراف، مانند الگوریتم الگوریتم فلوید وارشال و الگوریتم کروسکال، از ماتریس های مجاورت برای نمایش نمودارها استفاده می‌کنند.
- پردازش تصویر: ماتریس های مجاورت نشان‌دهنده رابطه مجاورت بین پیکسل‌ها در یک تصویر هستند.
- یافتن کوتاه‌ترین مسیر بین دو گره: با انجام ضرب ماتریس بر روی ماتریس مجاورت، می‌توان کوتاه‌ترین مسیر را بین هر دو گره در یک نمودار دید.
جمع‌بندی
ماتریس مجاورت یکی از راه‌های نمایش گراف است. در این مقاله به معرفی این روش پرداختیم و پیاده‌سازی این روش در زبان های برنامه نویسی مختلف را دیدیم؛ همچنین با برخی از مزایا و معایب آن و همینطور کاربردهای آن آشنا شدیم.
ماتریس مجاورت چیست؟
در نظریه گراف و علوم کامپیوتر، ماتریس مجاورت یک ماتریس مربعی است که یک گراف متناهی را نشان می‌دهد. عناصر ماتریس نشان می‌دهد که آیا جفت رئوس در گراف مجاور هستند یا نه. در یک گراف ساده متناهی، ماتریس مجاورت یک ماتریس (0،1) با صفر در قطر آن است.
چه زمانی باید از ماتریس مجاورت استفاده کرد؟
برای نمایش گراف‌های متراکم باید از ماتریس مجاورت و برای نمایش گراف‌های پراکنده از لیست مجاورت استفاده کنیم.(گراف متراکم به آن‌هایی گفته می‌شود که تعداد یال آنها زیاد است و گراف پراکنده آن‌هایی هستند که تعداد یال آنها کم است.)
مهم‌ترین عیب ماتریس مجاورت چیست؟
مهم‌ترین نقطه ضعف نمایش ماتریس مجاورت این است که به ذخیره‌سازی از مرتبه زمانی n2 نیاز دارد، حتی اگر گراف به اندازه O(n) یال داشته باشد.
مطالب مرتبط
همه مقالات
