Dalam tutorial ini, Anda akan mempelajari apa itu matriks ketetanggaan. Juga, Anda akan menemukan contoh kerja matriks adjacency di C, C ++, Java dan Python.
Matriks ketetanggaan adalah cara merepresentasikan grafik G = (V, E) sebagai matriks boolean.
Representasi matriks kedekatan
Ukuran matriks adalah di VxVmana Vjumlah simpul pada grafik dan nilai entri Aijadalah 1 atau 0 tergantung apakah ada sisi dari simpul i ke simpul j.
Contoh Adjacency Matrix
Gambar di bawah menunjukkan grafik dan matriks ketetanggaan ekuivalennya.
Matriks kedekatan dari grafik
Dalam kasus graf tidak berarah, matriks tersebut simetris terhadap diagonal karena setiap sisi (i,j)juga ada sisi (j,i).
Kelebihan matriks kedekatan
Operasi dasar seperti menambahkan sebuah sisi, menghilangkan sebuah sisi dan memeriksa apakah ada sebuah sisi dari simpul i ke simpul j sangat efisien waktu, operasi waktu konstan.
Jika grafnya padat dan jumlah rusuknya besar, matriks kedekatan harus menjadi pilihan pertama. Meskipun grafik dan matriks ketetanggaan jarang, kita dapat merepresentasikannya menggunakan struktur data untuk matriks renggang.
Keuntungan terbesar bagaimanapun, berasal dari penggunaan matriks. Kemajuan terbaru dalam perangkat keras memungkinkan kami untuk melakukan operasi matriks yang bahkan mahal pada GPU.
Dengan melakukan operasi pada matriks yang berdekatan, kita bisa mendapatkan wawasan penting tentang sifat grafik dan hubungan antara simpulnya.
Kontra matriks kedekatan
The VxVkebutuhan ruang dari matriks adjacency membuat babi memori. Grafik di alam liar biasanya tidak memiliki terlalu banyak koneksi dan inilah alasan utama mengapa daftar kedekatan adalah pilihan yang lebih baik untuk sebagian besar tugas.
Meskipun operasi dasarnya mudah, operasi suka inEdgesdan outEdgesmahal jika menggunakan representasi matriks ketetanggaan.
Contoh Python, Java dan C / C ++
Jika Anda tahu cara membuat array dua dimensi, Anda juga tahu cara membuat matriks ketetanggaan.
Python Java C C + # Adjacency Matrix representation in 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()
// Adjacency Matrix representation in 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(""); ) 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()); ) )
// 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(""); ) ) 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; )
// Adjacency Matrix representation in 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 << ""; ) ) ~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(); )
Aplikasi Adjacency Matrix
- Membuat tabel routing dalam jaringan
- Tugas navigasi
