| | |
| Stránka: 1 z 1
| [ Príspevok: 1 ] | |
Autor | Správa |
---|
Registrovaný: 29.12.10 Prihlásený: 26.10.16 Príspevky: 62 Témy: 19 |
edit: uz som na tom prisiel (mozte temu zmazat) sorry zdravim, nasiel som tento algoritmus na hladanie artikulacii v grafe... ako zistim ake su maximalne hodnoty ktore mozem do grafu zadat? Kód: // A C++ program to find articulation points in a given undirected graph #include<iostream> #include <list> #define NIL -1 using namespace std; // A class that represents an undirected graph class Graph { int V; // No. of vertices list<int> *adj; // A dynamic array of adjacency lists void APUtil(int v, bool visited[], int disc[], int low[], int parent[], bool ap[]); public: Graph(int V); // Constructor void addEdge(int v, int w); // function to add an edge to graph void AP(); // prints articulation points }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); adj[w].push_back(v); // Note: the graph is undirected } // A recursive function that find articulation points using DFS traversal // u --> The vertex to be visited next // visited[] --> keeps tract of visited vertices // disc[] --> Stores discovery times of visited vertices // parent[] --> Stores parent vertices in DFS tree // ap[] --> Store articulation points void Graph::APUtil(int u, bool visited[], int disc[], int low[], int parent[], bool ap[]) { // A static variable is used for simplicity, we can avoid use of static // variable by passing a pointer. static int time = 0; // Count of children in DFS Tree int children = 0; // Mark the current node as visited visited[u] = true; // Initialize discovery time and low value disc[u] = low[u] = ++time; // Go through all vertices aadjacent to this list<int>::iterator i; for (i = adj[u].begin(); i != adj[u].end(); ++i) { int v = *i; // v is current adjacent of u // If v is not visited yet, then make it a child of u // in DFS tree and recur for it if (!visited[v]) { children++; parent[v] = u; APUtil(v, visited, disc, low, parent, ap); // Check if the subtree rooted with v has a connection to // one of the ancestors of u low[u] = min(low[u], low[v]); // u is an articulation point in following cases // (1) u is root of DFS tree and has two or more chilren. if (parent[u] == NIL && children > 1) ap[u] = true; // (2) If u is not root and low value of one of its child is more // than discovery value of u. if (parent[u] != NIL && low[v] >= disc[u]) ap[u] = true; } // Update low value of u for parent function calls. else if (v != parent[u]) low[u] = min(low[u], disc[v]); } } // The function to do DFS traversal. It uses recursive function APUtil() void Graph::AP() { // Mark all the vertices as not visited bool *visited = new bool[V]; int *disc = new int[V]; int *low = new int[V]; int *parent = new int[V]; bool *ap = new bool[V]; // To store articulation points // Initialize parent and visited, and ap(articulation point) arrays for (int i = 0; i < V; i++) { parent[i] = NIL; visited[i] = false; ap[i] = false; } // Call the recursive helper function to find articulation points // in DFS tree rooted with vertex 'i' for (int i = 0; i < V; i++) if (visited[i] == false) APUtil(i, visited, disc, low, parent, ap); // Now ap[] contains articulation points, print them for (int i = 0; i < V; i++) if (ap[i] == true) cout << i << " "; } // Driver program to test above function int main() { // Create graphs given in above diagrams cout << "\nArticulation points in first graph \n"; Graph g1(5); g1.addEdge(1, 0); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(0, 3); g1.addEdge(3, 4); g1.AP(); cout << "\nArticulation points in second graph \n"; Graph g2(4); g2.addEdge(0, 1); g2.addEdge(1, 2); g2.addEdge(2, 3); g2.AP(); cout << "\nArticulation points in third graph \n"; Graph g3(7); g3.addEdge(0, 1); g3.addEdge(1, 2); g3.addEdge(2, 0); g3.addEdge(1, 3); g3.addEdge(1, 4); g3.addEdge(1, 6); g3.addEdge(3, 5); g3.addEdge(4, 5); g3.AP(); return 0; }
|
|
| Stránka: 1 z 1
| [ Príspevok: 1 ] | |
Podobné témy | Témy | Odpovede | Zobrazenia | Posledný príspevok |
---|
| ako stiahnut tento koncert ako mp3? v Audio programy | 3 | 517 | 27.11.2020 22:20 patro16 | | AKO NA TENTO BIOS v Biosy a ladenie výkonu | 2 | 702 | 16.08.2007 21:11 0r0l | | AKO na tento panel? v Operačné systémy Microsoft | 3 | 485 | 27.04.2007 20:48 Devil_SK | | Ako nastavit tento datepicker v JavaScript, VBScript, Ajax | 7 | 774 | 30.11.2017 13:46 unset(array[0]) | | Ako hodnotite tento NB? v PC zostavy | 10 | 556 | 17.03.2008 13:43 mimkork | | Ako rozobrat tento sifon? v Život, životný štýl, móda, bývanie | 3 | 694 | 21.06.2017 15:37 4040 | | ako na tento procak? v Chladiče a všetky druhy chladenia | 2 | 783 | 20.10.2006 15:03 looser | | ako na tento select? v Databázy | 9 | 1067 | 07.02.2007 8:33 rokovic | | ako na tento dotaz v Databázy | 3 | 749 | 21.06.2009 18:04 p360t | | Ako sa volal tento film? v Kultúra, umenie, filmy, hudba, história, média | 17 | 1707 | 22.05.2008 17:35 sairik | | ako sa vola tento mod v Redakčné systémy | 6 | 523 | 26.01.2007 19:35 Tom@S | | Ako sa vola tento uces? v Život, životný štýl, móda, bývanie | 12 | 1025 | 11.07.2009 19:41 majky358 | | existuje rok rovnaky ako tento? v Krčma | 8 | 1299 | 01.01.2008 12:25 twistik | | ako sa vola tento script v JavaScript, VBScript, Ajax | 1 | 522 | 07.02.2010 13:37 rooobertek | | Ako sa volá tento fyzikálny jav? v Vzdelanie, štúdium, škola | 1 | 477 | 22.06.2015 19:04 killer | | Ako sa Vam paci tento web? v Webdesign | 14 | 1006 | 18.04.2008 22:43 pepek92 |
| Nemôžete zakladať nové témy v tomto fóre Nemôžete odpovedať na témy v tomto fóre Nemôžete upravovať svoje príspevky v tomto fóre Nemôžete mazať svoje príspevky v tomto fóre
|
|