Pelaksanaan graf dalam JavaScript

Graf ialah struktur data tak linear yang mewakili satu set bucu (juga dipanggil nod) dan hubungan (atau tepi) antara mereka. Bucu mewakili entiti atau objek, manakala tepi mewakili hubungan atau hubungan antara bucu. Graf boleh digunakan untuk memodelkan pelbagai jenis perhubungan, seperti rangkaian sosial, sistem pengangkutan atau aliran maklumat.

Terdapat dua jenis graf utama: graf terarah (juga dipanggil graf terarah) dan graf tidak terarah. Dalam graf berarah, tepi mempunyai satu arah dan hanya boleh dilalui dalam satu arah, iaitu dari bucu permulaan ke bucu penghujung. Dalam graf tidak berarah, tepi tidak mempunyai arah dan boleh dilalui dalam kedua-dua arah.

Pelaksanaan imej dalam JavaScript

Graf boleh dilaksanakan menggunakan matriks bersebelahan atau senarai bersebelahan. Di sini kami akan melaksanakan graf dalam JavaScript menggunakan senarai bersebelahan.

Buat kelas carta

Di sini kami mencipta rangka tindakan kelas grafik.

class Graph {
   constructor() {
      this.adjacencyList = {};
   }
}

Tambah bucu

Fungsi ini menambah bucu (atau nod) baharu pada graf dengan mencipta kunci baharu dalam objek adjacencyList dan memberikan tatasusunan kosong sebagai nilainya. Puncak baharu akan berfungsi sebagai kunci dan tatasusunan kosong akan digunakan untuk menyimpan jirannya.

addVertex(vertex) {
   if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
}

Tambah tepi

Fungsi ini menambah tepi baharu antara dua bucu. Ia menerima dua parameter: vertex1 dan vertex2, dan menambah vertex2 pada tatasusunan jiran vertex1 dan sebaliknya. Ini mewujudkan hubungan antara dua bucu.

addEdge(vertex1, vertex2) {
   this.adjacencyList[vertex1].push(vertex2);
   this.adjacencyList[vertex2].push(vertex1);
}

Cetak carta

Fungsi ini log carta ke konsol. Ia berulang pada setiap bucu dalam objek adjacencyList dan merekodkan bucu dan jirannya.

print() {
   for (const [vertex, edges] of Object.entries(this.adjacencyList)) {
      console.log(`${vertex} -> ${edges.join(", ")}`);
   }
}

Contoh

Dalam contoh di bawah, kami mentakrifkan graf dan menambah bucu dan tepi pada graf. Akhirnya cetak carta.

class Graph {
   constructor() {
      this.adjacencyList = {};
   }
   addVertex(vertex) {
      if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
   }
   addEdge(vertex1, vertex2) {
      this.adjacencyList[vertex1].push(vertex2);
      this.adjacencyList[vertex2].push(vertex1);
   }
   print() {
      for (const [vertex, edges] of Object.entries(this.adjacencyList)) {
         console.log(`${vertex} -> ${edges.join(", ")}`);
      }
   }
}
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "D");
console.log("Graph:");
graph.print();

Output

Graph:
A -> B, C
B -> A, D
C -> A, D
D -> B, C

Padam tepi

Fungsi ini memadamkan tepi antara dua bucu. Ia memerlukan dua hujah: vertex1 dan vertex2, dan menapis keluar vertex2 daripada tatasusunan jiran vertex1 dan sebaliknya.

removeEdge(vertex1, vertex2) {
   this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
      (v) => v !== vertex2
   );
   this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
      (v) => v !== vertex1
   );
}

Padam bucu

Fungsi ini mengeluarkan bucu daripada graf. Ia memerlukan hujah bucu dan mula-mula mengalih keluar semua tepi yang disambungkan ke bucu itu. Kemudian, ia mengalih keluar kunci daripada objek adjacencyList.

removeVertex(vertex) {
   while (this.adjacencyList[vertex].length) {
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
   }
   delete this.adjacencyList[vertex];
}

Contoh

Dalam contoh di bawah, kami mentakrifkan graf dan menambah bucu dan tepi, kemudian mencetak graf. Kami mengeluarkan AC tepi daripada graf dan akhirnya mencetak graf yang terhasil.

class Graph {
   constructor() {
      this.adjacencyList = {};
   }
   addVertex(vertex) {
      if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
   }
   addEdge(vertex1, vertex2) {
      this.adjacencyList[vertex1].push(vertex2);
      this.adjacencyList[vertex2].push(vertex1);
   }
   removeEdge(vertex1, vertex2) {
      this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
         (v) => v !== vertex2
      );
      this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
         (v) => v !== vertex1
      );
   }
   removeVertex(vertex) {
      while (this.adjacencyList[vertex].length) {
         const adjacentVertex = this.adjacencyList[vertex].pop();
         this.removeEdge(vertex, adjacentVertex);
      }
      delete this.adjacencyList[vertex];
   }
   print() {
      for (const [vertex, edges] of Object.entries(this.adjacencyList)) {
         console.log(`${vertex} -> ${edges.join(", ")}`);
      }
   }
}
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "D");
console.log("Initial Graph:");
graph.print();
console.log("Graph after removal of edge AC:")
graph.removeEdge("A","C");
graph.print();

Output

Initial Graph:
A -> B, C
B -> A, D
C -> A, D
D -> B, C
Graph after removal of edge AC:
A -> B
B -> A, D
C -> D
D -> B, C

Kaedah lintasan graf

Perjalanan graf merujuk kepada proses melawati semua bucu (atau nod) graf dan memproses maklumat yang berkaitan dengannya. Traversal graf ialah operasi penting dalam algoritma graf dan digunakan untuk tugas seperti mencari laluan terpendek antara dua nod, mengesan kitaran dan mencari komponen yang bersambung.

Terdapat dua kaedah utama untuk traversal graf: Breadth First Search (BFS) dan Depth First Search (DFS)

A. Breadth First Search (BFS)

Ia dilaksanakan menggunakan fungsi breadthFirstSearch(). Fungsi ini melaksanakan algoritma carian luas-pertama dan mengambil parameter permulaan, iaitu puncak permulaan. Ia menggunakan baris gilir untuk menjejak bucu yang akan dilawati, tatasusunan hasil untuk menyimpan bucu yang dilawati dan objek lawatan untuk menjejak bucu yang telah dilawati. Fungsi pertama menambah puncak permulaan pada baris gilir dan menandakannya sebagai dilawati. Kemudian, apabila baris gilir tidak kosong, ia mengambil puncak pertama daripada baris gilir, menambahkannya pada tatasusunan hasil dan menandakannya sebagai dilawati. Ia kemudian menambah semua jiran yang tidak dilawati ke baris gilir. Proses ini berterusan sehingga semua bucu telah dilawati dan tatasusunan yang terhasil dikembalikan sebagai hasil daripada BFS.

breadthFirstSearch(start) {
   const queue = [start];
   const result = [];
   const visited = {};
   let currentVertex;
   visited[start] = true;
   while (queue.length) {
      currentVertex = queue.shift();
      result.push(currentVertex);
         this.adjacencyList[currentVertex].forEach((neighbor) => {
            if (!visited[neighbor]) {
               visited[neighbor] = true;
               queue.push(neighbor);
            }
         });
      }
      return result;
   }
}

B. Carian pertama mendalam

Kaedah carian pertama mendalam melaksanakan algoritma DFS dengan menggunakan fungsi dalaman rekursif dfs yang mengambil bucu sebagai parameter. Fungsi ini menggunakan objek yang dilawati untuk menjejaki bucu yang dilawati dan menambah setiap bucu yang dilawati pada tatasusunan hasil. Fungsi pertama menandakan puncak semasa sebagai dilawati dan menambahkannya pada tatasusunan hasil. Ia kemudian melelang ke atas semua jiran puncak semasa dan secara rekursif memanggil fungsi dfs untuk setiap jiran yang tidak dilawati. Proses ini berterusan sehingga semua bucu telah dilawati dan tatasusunan yang terhasil dikembalikan sebagai hasil DFS.

depthFirstSearch(start) {
   const result = [];
   const visited = {};
   const adjacencyList = this.adjacencyList;
   (function dfs(vertex) {
      if (!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);
      adjacencyList[vertex].forEach(neighbor => {
         if (!visited[neighbor]) {
            return dfs(neighbor);
         }
      });
   })(start);
   return result;
}

Contoh

Dalam contoh di bawah, kami menunjukkan Breadth First Search (BFS) dan Depth First Search (DFS).

class Graph {
   constructor() {
      this.adjacencyList = {};
   }
   addVertex(vertex) {
      if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
   }
   addEdge(vertex1, vertex2) {
      this.adjacencyList[vertex1].push(vertex2);
      this.adjacencyList[vertex2].push(vertex1);
   }
   print() {
      for (const [vertex, edges] of Object.entries(this.adjacencyList)) {
         console.log(`${vertex} -> ${edges.join(", ")}`);
      }
   }
   breadthFirstSearch(start) {
      const queue = [start];
      const result = [];
      const visited = {};
      let currentVertex;
      visited[start] = true;
      while (queue.length) {
         currentVertex = queue.shift();
         result.push(currentVertex);
         this.adjacencyList[currentVertex].forEach((neighbor) => {
            if (!visited[neighbor]) {
               visited[neighbor] = true;
               queue.push(neighbor);
            }
         });
      }
      return result;
   }
   depthFirstSearch(start) {
      const result = [];
      const visited = {};
      const adjacencyList = this.adjacencyList;
      (function dfs(vertex) {
         if (!vertex) return null;
         visited[vertex] = true;
         result.push(vertex);
         adjacencyList[vertex].forEach(neighbor => {
            if (!visited[neighbor]) {
               return dfs(neighbor);
            }
         });
      })(start);
      return result;
   }
}
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "D");
console.log("Initial Graph:");
graph.print();
console.log("BFS: "+graph.breadthFirstSearch('A'));
console.log("DFS: "+graph.depthFirstSearch('A'));

Output

Initial Graph:
A -> B, C
B -> A, D
C -> A, D
D -> B, C
BFS: A,B,C,D
DFS: A,B,D,C

Kesimpulan

Graf ialah struktur data berguna yang boleh digunakan untuk mewakili perhubungan dan perkaitan antara objek. Melaksanakan graf dalam JavaScript boleh dilakukan menggunakan pelbagai teknik, termasuk menggunakan senarai bersebelahan atau matriks bersebelahan. Kelas Graf yang ditunjukkan dalam jawapan ini menggunakan perwakilan senarai bersebelahan, di mana setiap bucu disimpan sebagai kunci dalam objek dan kelebihan sepadannya disimpan sebagai nilai kunci itu dalam tatasusunan.

Kelas Graf melaksanakan kaedah untuk menambah bucu dan tepi pada graf, mencetak graf dan melakukan carian mendalam-dahulu dan keluasan carian pertama.

Atas ialah kandungan terperinci Pelaksanaan graf dalam JavaScript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!