के साथ टॉपोलॉजिकल सॉर्ट करें, इसलिए इनपुट डेटा के आधार पर स्थलीय सॉर्टिंग में, आमतौर पर कई सही समाधान होते हैं जिसके लिए ग्राफ को "संसाधित" किया जा सकता है ताकि सभी निर्भरता नोड्स से पहले आ सकें जो उन पर "निर्भर" हैं। हालांकि, मैं एक अलग जवाब के लिए देख रहा हूँ:ग्रुपिंग
निम्न डेटा मान लीजिए: a -> b और c -> d (a आना चाहिए से पहले b और cd से पहले आना चाहिए)।
केवल इन दो बाधाओं के साथ हमारे पास कई उम्मीदवार समाधान हैं: (a b c d, a c d b, c a b d, आदि)। हालांकि, मैं इन नोड्स को "ग्रुपिंग" करने की एक विधि बनाना चाहता हूं ताकि समूह की प्रसंस्करण के बाद, अगले समूह में सभी प्रविष्टियों की उनकी निर्भरताएं देखभाल की जाएंगी। उपर्युक्त डेटा के लिए मैं (a, c) (b, d) जैसे समूह की तलाश कर रहा हूं। प्रत्येक समूह के भीतर यह कोई बात नहीं जो आदेश नोड्स कार्रवाई की जाती है (ac या bd से पहले, आदि और इसके विपरीत से पहले) बस इतने लंबे समय के रूप में समूह 1 (a, c) कम्प्लिट्स समूह 2 (b, d) में से किसी से पहले कार्रवाई की जाती है।
एकमात्र अतिरिक्त पकड़ यह होगा कि प्रत्येक नोड जल्द से जल्द समूह में होना चाहिए। पर विचार करें निम्नलिखित:
a -> b -> c
d -> e -> f
x -> y
(a, d) (b, e, x) (c, f, y) का समूह योजना तकनीकी रूप से सही होगा क्योंकि xy से पहले, एक अधिक इष्टतम समाधान (a, d, x) (b, e, y) (c, f) होगा क्योंकि समूह 2 में x होने का तात्पर्य है कि x निर्भर था समूह में कुछ नोड पर 1.
ऐसा करने के बारे में कोई विचार कैसे है?
संपादित करें: मुझे लगता है कि मैं कुछ समाधान कोड को एक साथ थप्पड़ मारने में कामयाब रहा। उन सभी के लिए धन्यवाद जिन्होंने मदद की!
// Topological sort
// Accepts: 2d graph where a [0 = no edge; non-0 = edge]
// Returns: 1d array where each index is that node's group_id
vector<int> top_sort(vector< vector<int> > graph)
{
int size = graph.size();
vector<int> group_ids = vector<int>(size, 0);
vector<int> node_queue;
// Find the root nodes, add them to the queue.
for (int i = 0; i < size; i++)
{
bool is_root = true;
for (int j = 0; j < size; j++)
{
if (graph[j][i] != 0) { is_root = false; break; }
}
if (is_root) { node_queue.push_back(i); }
}
// Detect error case and handle if needed.
if (node_queue.size() == 0)
{
cerr << "ERROR: No root nodes found in graph." << endl;
return vector<int>(size, -1);
}
// Depth first search, updating each node with it's new depth.
while (node_queue.size() > 0)
{
int cur_node = node_queue.back();
node_queue.pop_back();
// For each node connected to the current node...
for (int i = 0; i < size; i++)
{
if (graph[cur_node][i] == 0) { continue; }
// See if dependent node needs to be updated with a later group_id
if (group_ids[cur_node] + 1 > group_ids[i])
{
group_ids[i] = group_ids[cur_node] + 1;
node_queue.push_back(i);
}
}
}
return group_ids;
}
ऐसा लगता है जैसे आप सिर्फ "लालची" समूह बनाना चाहते हैं। पहले समूह में हो सकने वाले सभी नोड्स खोजें। फिर सभी नोड्स जो दूसरे समूह में हो सकते हैं, आदि, जब तक कि कोई नोड्स असाइन नहीं किया जाता है। – aschepler
अपना समाधान पोस्ट करने के लिए धन्यवाद, लेकिन क्या आप अपेक्षित इनपुट प्रारूप का बेहतर वर्णन कर सकते हैं? शायद एक उदाहरण के साथ? – mpen
@mpen - मैंने जो समाधान पोस्ट किया है वह 2 डी वेक्टर आसन्नता मैट्रिक्स की अपेक्षा करता है। मैं मूल इनपुट प्रारूप शामिल करूंगा लेकिन यह प्रश्न लगभग 6 साल पुराना है और मैंने मूल कोड को गलत स्थानांतरित कर दिया है। –