Voimakkaasti liitetyt komponentit

Tässä opetusohjelmassa opit kuinka vahvasti kytketyt komponentit muodostuvat. Lisäksi löydät toimivia esimerkkejä kosararjun algoritmista C, C ++, Java ja Python.

Voimakkaasti yhdistetty komponentti on suunnatun kuvaajan osa, jossa jokaisesta kärjestä on polku toiseen kärkeen. Sitä voidaan käyttää vain suunnatussa kuvaajassa .

Esimerkiksi:

Otetaan alla oleva kaavio.

Alkuperäinen kaavio

Edellä olevan kaavion vahvasti liitetyt komponentit ovat:

Voimakkaasti liitetyt komponentit

Voit havaita, että ensimmäisessä vahvasti kytketyssä komponentissa jokainen kärki voi saavuttaa toisen kärjen suunnatun polun kautta.

Nämä komponentit löytyvät Kosarajun algoritmista .

Kosarajun algoritmi

Kosarajun algoritmi perustuu kahdesti toteutettuun syvyyslähtöiseen hakualgoritmiin.

Kolme vaihetta on mukana.

  1. Suorita ensimmäinen syvyyshaku koko kaaviosta.
    Aloitetaan pisteestä 0, vierailemme kaikissa sen alipisteissä ja merkitään vierailut pisteet valmiiksi. Jos kärkipiste johtaa jo käydyn kärkipisteeseen, työnnä tämä kärkipino pinoon.
    Esimerkiksi: Mene kärjestä 0, siirry kärkeen 1, kärkeen 2 ja sitten kärkeen 3. Vertex-3 johtaa jo käyneeseen vertex-0: een, joten työnnä lähdepiste (eli vertex-3) pinoon. Kaavion DFS
    Siirry edelliseen kärkeen (kärki-2) ja vieraile sen alipisteissä eli kärjessä 4, 5, 5 ja 6. Koska kärkipisteestä 7 ei ole minne mennä, työnnä se pinoon. DFS kaaviossa
    Siirry edelliseen kärkeen (kärki-6) ja vieraile sen alipisteissä. Mutta kaikissa sen alipisteissä käydään, joten työnnä se pinoon. Pinoaminen
    Samoin luodaan viimeinen pino. Viimeinen pino
  2. Käännä alkuperäinen kaavio. DFS käänteisessä kaaviossa
  3. Suorita ensimmäinen haku syvennetystä kaaviosta.
    Aloita pinon yläosasta. Kulje sen kaikkien alipisteiden läpi. Kun jo käynyt kärki on saavutettu, muodostuu yksi vahvasti kytketty komponentti.
    Esimerkiksi: Ponna kärkipiste-0 pinosta. Aloita kärjestä 0, kulje sen alipisteiden läpi (kärki-0, kärki-1, kärki-2, kärki-3 peräkkäin) ja merkitse ne käydyksi. Kärkipisteen 3 lapsi on jo käynyt, joten nämä vierailleet pisteet muodostavat yhden vahvasti kytketyn komponentin. Aloita ylhäältä ja kulje kaikkien pisteiden läpi
    Mene pinoon ja ponnahda ylin kärki, jos olet jo käynyt. Muussa tapauksessa valitse ylin kärki pinosta ja kulje sen alipisteiden läpi yllä esitetyllä tavalla. Pop yläkärki, jos jo käynyt Voimakkaasti liitetty komponentti
  4. Siten vahvasti liitetyt komponentit ovat: Kaikki vahvasti liitetyt komponentit

Python-, Java-, C ++ -esimerkkejä

Python Java C ++ 
 # Kosaraju's algorithm to find strongly connected components in Python from collections import defaultdict class Graph: def __init__(self, vertex): self.V = vertex self.graph = defaultdict(list) # Add edge into the graph def add_edge(self, s, d): self.graph(s).append(d) # dfs def dfs(self, d, visited_vertex): visited_vertex(d) = True print(d, end='') for i in self.graph(d): if not visited_vertex(i): self.dfs(i, visited_vertex) def fill_order(self, d, visited_vertex, stack): visited_vertex(d) = True for i in self.graph(d): if not visited_vertex(i): self.fill_order(i, visited_vertex, stack) stack = stack.append(d) # transpose the matrix def transpose(self): g = Graph(self.V) for i in self.graph: for j in self.graph(i): g.add_edge(j, i) return g # Print stongly connected components def print_scc(self): stack = () visited_vertex = (False) * (self.V) for i in range(self.V): if not visited_vertex(i): self.fill_order(i, visited_vertex, stack) gr = self.transpose() visited_vertex = (False) * (self.V) while stack: i = stack.pop() if not visited_vertex(i): gr.dfs(i, visited_vertex) print("") g = Graph(8) g.add_edge(0, 1) g.add_edge(1, 2) g.add_edge(2, 3) g.add_edge(2, 4) g.add_edge(3, 0) g.add_edge(4, 5) g.add_edge(5, 6) g.add_edge(6, 4) g.add_edge(6, 7) print("Strongly Connected Components:") g.print_scc()
 // Kosaraju's algorithm to find strongly connected components in Java import java.util.*; import java.util.LinkedList; class Graph ( private int V; private LinkedList adj(); // Create a graph Graph(int s) ( V = s; adj = new LinkedList(s); for (int i = 0; i < s; ++i) adj(i) = new LinkedList(); ) // Add edge void addEdge(int s, int d) ( adj(s).add(d); ) // DFS void DFSUtil(int s, boolean visitedVertices()) ( visitedVertices(s) = true; System.out.print(s + " "); int n; Iterator i = adj(s).iterator(); while (i.hasNext()) ( n = i.next(); if (!visitedVertices(n)) DFSUtil(n, visitedVertices); ) ) // Transpose the graph Graph Transpose() ( Graph g = new Graph(V); for (int s = 0; s < V; s++) ( Iterator i = adj(s).listIterator(); while (i.hasNext()) g.adj(i.next()).add(s); ) return g; ) void fillOrder(int s, boolean visitedVertices(), Stack stack) ( visitedVertices(s) = true; Iterator i = adj(s).iterator(); while (i.hasNext()) ( int n = i.next(); if (!visitedVertices(n)) fillOrder(n, visitedVertices, stack); ) stack.push(new Integer(s)); ) // Print strongly connected component void printSCC() ( Stack stack = new Stack(); boolean visitedVertices() = new boolean(V); for (int i = 0; i < V; i++) visitedVertices(i) = false; for (int i = 0; i < V; i++) if (visitedVertices(i) == false) fillOrder(i, visitedVertices, stack); Graph gr = Transpose(); for (int i = 0; i < V; i++) visitedVertices(i) = false; while (stack.empty() == false) ( int s = (int) stack.pop(); if (visitedVertices(s) == false) ( gr.DFSUtil(s, visitedVertices); System.out.println(); ) ) ) public static void main(String args()) ( Graph g = new Graph(8); g.addEdge(0, 1); g.addEdge(1, 2); g.addEdge(2, 3); g.addEdge(2, 4); g.addEdge(3, 0); g.addEdge(4, 5); g.addEdge(5, 6); g.addEdge(6, 4); g.addEdge(6, 7); System.out.println("Strongly Connected Components:"); g.printSCC(); ) )
 // Kosaraju's algorithm to find strongly connected components in C++ #include #include #include using namespace std; class Graph ( int V; list *adj; void fillOrder(int s, bool visitedV(), stack &Stack); void DFS(int s, bool visitedV()); public: Graph(int V); void addEdge(int s, int d); void printSCC(); Graph transpose(); ); Graph::Graph(int V) ( this->V = V; adj = new list(V); ) // DFS void Graph::DFS(int s, bool visitedV()) ( visitedV(s) = true; cout << s << " "; list::iterator i; for (i = adj(s).begin(); i != adj(s).end(); ++i) if (!visitedV(*i)) DFS(*i, visitedV); ) // Transpose Graph Graph::transpose() ( Graph g(V); for (int s = 0; s < V; s++) ( list::iterator i; for (i = adj(s).begin(); i != adj(s).end(); ++i) ( g.adj(*i).push_back(s); ) ) return g; ) // Add edge into the graph void Graph::addEdge(int s, int d) ( adj(s).push_back(d); ) void Graph::fillOrder(int s, bool visitedV(), stack &Stack) ( visitedV(s) = true; list::iterator i; for (i = adj(s).begin(); i != adj(s).end(); ++i) if (!visitedV(*i)) fillOrder(*i, visitedV, Stack); Stack.push(s); ) // Print strongly connected component void Graph::printSCC() ( stack Stack; bool *visitedV = new bool(V); for (int i = 0; i < V; i++) visitedV(i) = false; for (int i = 0; i < V; i++) if (visitedV(i) == false) fillOrder(i, visitedV, Stack); Graph gr = transpose(); for (int i = 0; i < V; i++) visitedV(i) = false; while (Stack.empty() == false) ( int s = Stack.top(); Stack.pop(); if (visitedV(s) == false) ( gr.DFS(s, visitedV); cout << endl; ) ) ) int main() ( Graph g(8); g.addEdge(0, 1); g.addEdge(1, 2); g.addEdge(2, 3); g.addEdge(2, 4); g.addEdge(3, 0); g.addEdge(4, 5); g.addEdge(5, 6); g.addEdge(6, 4); g.addEdge(6, 7); cout << "Strongly Connected Components:"; g.printSCC(); )

Kosarajun algoritmikompleksi

Kosarajun algoritmi toimii lineaarisessa ajassa O(V+E).

Voimakkaasti yhdistetyt komponenttisovellukset

  • Ajoneuvojen reitityssovellukset
  • Kartat
  • Mallintarkastus muodollisessa tarkastuksessa

Mielenkiintoisia artikkeleita...