Dalam tutorial ini, anda akan mengetahui apa itu matriks adjacency. Anda juga akan mendapat contoh matriks adjacency yang berfungsi di C, C ++, Java dan Python.
Matriks adjacency adalah cara mewakili graf G = (V, E) sebagai matriks booleans.
Perwakilan matriks kecukupan
Ukuran matriks adalah VxVdi mana Vbilangan bucu dalam grafik dan nilai entri Aijsama ada 1 atau 0 bergantung pada sama ada terdapat tepi dari bucu i ke bucu j.
Contoh Matriks Adjacency
Gambar di bawah menunjukkan graf dan matriks sepadannya.
Matriks kecocokan dari graf
Sekiranya graf tidak diarahkan, matriks adalah simetri mengenai pepenjuru kerana setiap sisi (i,j), terdapat juga sisi (j,i).
Kelebihan matriks adjacency
Operasi asas seperti menambahkan pinggir, membuang pinggir dan memeriksa sama ada terdapat tepi dari bucu i ke bucu j adalah operasi masa yang sangat efisien dan tetap.
Sekiranya grafnya padat dan bilangan pinggirnya besar, matriks adjacency harus menjadi pilihan pertama. Walaupun graf dan matriks adjacency jarang, kita dapat merepresentasikannya menggunakan struktur data untuk matriks jarang.
Walau bagaimanapun, kelebihan terbesar adalah dari penggunaan matriks. Kemajuan perkakasan baru-baru ini membolehkan kita melakukan operasi matriks yang lebih mahal pada GPU.
Dengan melakukan operasi pada matriks bersebelahan, kita dapat memperoleh gambaran penting mengenai sifat grafik dan hubungan antara bucunya.
Kekurangan matriks adjacency
The VxVkeperluan ruang matriks bersebelahan menjadikannya babi memori. Grafik di luar biasanya tidak mempunyai terlalu banyak hubungan dan ini adalah sebab utama mengapa senarai bersebelahan adalah pilihan yang lebih baik untuk kebanyakan tugas.
Walaupun operasi asas mudah, operasi suka inEdgesdan outEdgesmahal ketika menggunakan perwakilan matriks adjacency.
Contoh Python, Java dan C / C ++
Sekiranya anda tahu bagaimana membuat susunan dua dimensi, anda juga tahu bagaimana membuat matriks adjacency.
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 Matriks Adjacency
- Membuat jadual penghalaan dalam rangkaian
- Tugas navigasi
