Cetak nod dalam graf terarah yang bukan milik mana-mana kitaran

Dalam rajah penyelarasan, mengenal pasti hab yang tidak tergolong dalam mana-mana kitaran adalah penting untuk aplikasi yang berbeza. Pusat-pusat ini membentuk asas subgraf asiklik dan memainkan peranan penting dalam memahami struktur graf umum. Dengan menggunakan pengiraan persilangan graf yang cekap, seperti Profundity First Hunt (DFS) atau pengiraan Tarjan bagi bahagian yang berkait rapat, kami boleh dengan mudah memutuskan dan mencetak hab yang tidak mengambil bahagian dalam sebarang gelung. Kaedah ini memastikan pencirian pusat tanpa kerjasama bulat, menyediakan pengetahuan penting untuk bahagian bukan bulatan rajah, dan menyokong situasi pemikiran kritikal yang berbeza yang berkaitan dengan rajah.

Kaedah penggunaan

• Carian pertama mendalam (DFS) dengan pengesanan gelung

• Algoritma komponen Tarjan yang bersambung kuat

Carian pertama mendalam (DFS) dengan pengesanan gelung

Dalam pendekatan ini, kami menggunakan penjejakan pertama mendalam (DFS) untuk menavigasi carta koordinasi dan membezakan kitaran dalam perjalanan. Kami menandai pusat yang dilawati dan menyimpan senarai supaya pusat boleh dijejaki dengan cara DFS yang berterusan. Jika kita menghadapi kelebihan mengekor (mencapai tepi hab dengan cara DFS yang berterusan), kita membezakan kitaran. Pada penghujung DFS, pusat dalam cara DFS yang berterusan akan menjadi penting untuk kitaran. Hab yang tidak menggunakan DFS berterusan bukan sebahagian daripada sebarang gelung dan boleh dicetak.

Algoritma

• Mulakan Deep First Hunt (DFS) dari setiap pusat yang belum dilawati pada carta.

• Semasa DFS, hab yang dilawati ditanda dan ditambahkan pada senarai laluan DFS yang sedang berjalan.

• Jika kami menemui pinggir mengekor (tepi ke hab dalam mod DFS semasa), kami membezakan kitaran dan menandakan semua hab dalam mod DFS semasa sebagai sebahagian daripada kitaran.

• Apabila DFS hab selesai, alih keluarnya daripada senarai laluan DFS yang sedang berjalan.

• Selepas melengkapkan DFS semua hab, hab yang tidak tergolong dalam mana-mana kitaran akan kekal tidak berubah dan kami boleh mencetaknya.

Contoh

#include <iostream>
#include <vector>

class Graph {
public:
   Graph(int numVertices);
   void addEdge(int src, int dest);
   void DFS();
private:
   void DFSUtil(int v, std::vector<bool>& visited, std::vector<int>& dfsPath);
   int numVertices;
   std::vector<std::vector<int>> adjList;
};

Graph::Graph(int numVertices) : numVertices(numVertices) {
   adjList.resize(numVertices);
}

void Graph::addEdge(int src, int dest) {
   adjList[src].push_back(dest);
}

void Graph::DFSUtil(int v, std::vector<bool>& visited, std::vector<int>& dfsPath) {
   visited[v] = true;
   dfsPath.push_back(v);

   for (int neighbor : adjList[v]) {
      if (!visited[neighbor]) {
         DFSUtil(neighbor, visited, dfsPath);
      }
      else {
         std::cout << "Cycle found: ";
         for (size_t i = 0; i < dfsPath.size(); ++i) {
            if (dfsPath[i] == neighbor) {
               while (i < dfsPath.size()) {
                  std::cout << dfsPath[i] << " ";
                  ++i;
               }
               break;
            }
         }
         std::cout << std::endl;
      }
   }

   dfsPath.pop_back();
}

void Graph::DFS() {
   std::vector<bool> visited(numVertices, false);
   std::vector<int> dfsPath;

   for (int i = 0; i < numVertices; ++i) {
      if (!visited[i]) {
         DFSUtil(i, visited, dfsPath);
      }
   }
}

int main() {
   Graph graph(6);
   graph.addEdge(0, 1);
   graph.addEdge(1, 2);
   graph.addEdge(2, 3);
   graph.addEdge(3, 4);
   graph.addEdge(4, 1);
   graph.addEdge(4, 5);
   
   std::cout << "DFS traversal with cycle detection:\n";
   graph.DFS();

   return 0;
}

Output

DFS traversal with cycle detection:
Cycle found: 1 2 3 4 

Algoritma komponen Tarjan yang bersambung kuat

Pengiraan Tarjan ialah pengiraan berkuasa yang digunakan untuk menjejaki semua bahagian penting berkaitan rajah koordinasi. Bahagian yang berkaitan secara jelas ialah subset hab yang mana penyelarasan wujud antara mana-mana dua hab dalam subset. Hab yang bukan sebahagian daripada mana-mana komponen yang berkait rapat bukanlah sebahagian daripada mana-mana kitaran. Dengan mencari bahagian penting yang berkaitan, kami boleh mengenal pasti hab yang bukan milik mana-mana kitaran dan mencetaknya

Algoritma

• Gunakan pengiraan Tarjan pada peta panduan anda untuk menjejaki semua bahagian penting yang berkaitan.

• Selepas mengesan semua bahagian penting yang berkaitan, bezakan pusat yang penting untuk bahagian yang berkait rapat.

• Hab yang bukan sebahagian daripada mana-mana widget yang dikaitkan secara eksplisit tidak tergolong dalam mana-mana gelung dan boleh dicetak.

• Kedua-dua kaedah ini membezakan dan mencetak pusat yang tidak tergolong dalam mana-mana kitaran dalam carta koordinasi. Kaedah DFS menyediakan pelaksanaan yang lebih mudah dan lebih mudah, manakala pengiraan Tarjan lebih kompleks tetapi menyediakan data tambahan pada bahagian korelasi yang difokuskan, yang boleh membantu untuk tugasan berkaitan carta tertentu. Keputusan mengenai pendekatan bergantung pada keperluan khusus dan konteks isu utama yang mendesak.

Contoh

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

class Graph {
   int V;
   vector<vector<int>> adj;
   vector<bool> visited;
   vector<int> disc, low;
   stack<int> st;
   vector<vector<int>> SCCs;
   vector<bool> essentialNodes;

public:
   Graph(int V) : V(V) {
      adj.resize(V);
      visited.resize(V, false);
      disc.resize(V, -1);
      low.resize(V, -1);
      essentialNodes.resize(V, true);
   }

   void addEdge(int u, int v) {
      adj[u].push_back(v);
   }

   void tarjanDFS(int u) {
      static int time = 0;
      disc[u] = low[u] = ++time;
      st.push(u);
      visited[u] = true;

      for (int v : adj[u]) {
         if (disc[v] == -1) {
            tarjanDFS(v);
            low[u] = min(low[u], low[v]);
         } else if (visited[v]) {
            low[u] = min(low[u], disc[v]);
         }
      }

      if (low[u] == disc[u]) {
         vector<int> SCC;
         int v;
         do {
            v = st.top();
            st.pop();
            SCC.push_back(v);
            visited[v] = false;
         } while (v != u);

         SCCs.push_back(SCC);
      }
   }

   void tarjan() {
      for (int i = 0; i < V; ++i) {
         if (disc[i] == -1) {
            tarjanDFS(i);
         }
      }
   }

   void identifyEssentialNodes() {
      for (const vector<int>& SCC : SCCs) {
         for (int v : SCC) {
            for (int u : adj[v]) {
               if (find(SCC.begin(), SCC.end(), u) == SCC.end()) {
                  essentialNodes[u] = false;
               }
            }
         }
      }
   }

   void printEssentialNodes() {
      cout << "Essential Nodes for Each SCC:\n";
      for (int i = 0; i < V; ++i) {
         if (essentialNodes[i]) {
            cout << i << " ";
         }
      }
      cout << endl;
   }
};

int main() {
   Graph g(6);
   g.addEdge(0, 1);
   g.addEdge(1, 2);
   g.addEdge(2, 0);
   g.addEdge(1, 3);
   g.addEdge(3, 4);
   g.addEdge(4, 5);
   g.addEdge(5, 3);

   g.tarjan();
   g.identifyEssentialNodes();
   g.printEssentialNodes();

   return 0;
}

Output

Essential Nodes for Each SCC:
0 1 2 4 5

Kesimpulan

Dua kaedah ini memang menyelesaikan masalah mengenal pasti pusat yang tidak tergolong dalam mana-mana kitaran dalam carta koordinasi. Kaedah DFS mudah dilaksanakan dan tidak memerlukan banyak struktur maklumat tambahan. Pengiraan Tarjan, sebaliknya, menyediakan data tambahan pada bahagian korelasi utama, yang mungkin membantu dalam situasi tertentu.

Keputusan antara dua kaedah bergantung pada prasyarat khusus masalah dan keperluan untuk data tambahan yang melalui pusat pembezaan bebas tempoh. Secara umum, jika satu-satunya matlamat adalah untuk mencari hab yang tidak tergolong dalam mana-mana kitaran, pendekatan DFS mungkin diutamakan kerana kesederhanaannya. Walau bagaimanapun, pengiraan Tarjan mungkin menjadi alat penting jika pemeriksaan lanjut ke atas bahagian penting yang berkaitan diperlukan. Kedua-dua kaedah menyediakan susunan yang cekap dan boleh disesuaikan dengan sifat carta koordinasi dan keputusan peperiksaan yang dikehendaki

Atas ialah kandungan terperinci Cetak nod dalam graf terarah yang bukan milik mana-mana kitaran. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!