1

For example suppose there are 3 nodes A,B,C and A links to B and C, B links to A and C, and C links to B and A. In visual form its like this

C <- A -> B //A links to B & C
A <- B -> C //B links to A & C
B <- C -> A //C links to B & A

Assume the A,B,C are held in an array like so [A,B,C] with index starting at 0. How can I efficiently sort the array [A,B,C] according to the value held by each node.

For example if A holds 4, B holds -2 and C holds -1, then sortGraph([A,B,C]) should return [B,C,A]. Hope its clear. Would it be possible if I can somehow utilize std::sort?

EDIT: Not basic sort algorithm. Let me clarify a bit more. Assume I have a list of Nodes [n0,n1...nm]. Each ni has a left and right neighbor index. For example, n1 left neight is n0 and its right neighbor is n2. I use index to represent the neighbor. If n1 is at index 1, then its left neighbor is at index 0 and its right neighbor is at index 2. If I sort the array, then I need to update the neighbor index as well. I don't want to really implement my own sorting algorithm, any advice on how to proceed?

4

4 回答 4

3

这是一个 C++ 实现，希望是有用的（它包括几个算法，如 dijkstra、kruskal，它使用深度优先搜索等进行排序......）

图.h

#ifndef __GRAPH_H
#define __GRAPH_H

#include <vector>
#include <stack>
#include <set>

typedef struct __edge_t
{
    int v0, v1, w;

    __edge_t():v0(-1),v1(-1),w(-1){}
    __edge_t(int from, int to, int weight):v0(from),v1(to),w(weight){}
} edge_t;

class Graph
{
public:
    Graph(void); // construct a graph with no vertex (and thus no edge)
    Graph(int n); // construct a graph with n-vertex, but no edge
    Graph(const Graph &graph); // deep copy of a graph, avoid if not necessary
public:
    // @destructor
    virtual ~Graph(void);
public:
    inline int getVertexCount(void) const { return this->numV; }
    inline int getEdgeCount(void)   const { return this->numE; }
public:
    // add an edge
    // @param: from [in] - starting point of the edge
    // @param: to   [in] - finishing point of the edge
    // @param: weight[in] - edge weight, only allow positive values
    void addEdge(int from, int to, int weight=1);
    // get all edges
    // @param: edgeList[out] - an array with sufficient size to store the edges
    void getAllEdges(edge_t edgeList[]);
public:
    // topological sort
    // @param: vertexList[out] - vertex order
    void sort(int vertexList[]);
    // dijkstra's shortest path algorithm
    // @param: v[in] - starting vertex
    // @param: path[out] - an array of <distance, prev> pair for each vertex
    void dijkstra(int v, std::pair<int, int> path[]);
    // kruskal's minimum spanning tree algorithm
    // @param: graph[out] - the minimum spanning tree result
    void kruskal(Graph &graph);
    // floyd-warshall shortest distance algorithm
    // @param: path[out] - a matrix of <distance, next> pair in C-style
    void floydWarshall(std::pair<int, int> path[]);
private:
    // resursive depth first search
    void sort(int v, std::pair<int, int> timestamp[], std::stack<int> &order);
    // find which set the vertex is in, used in kruskal
    std::set<int>* findSet(int v, std::set<int> vertexSet[], int n);
    // union two sets, used in kruskal
    void setUnion(std::set<int>* s0, std::set<int>* s1);
    // initialize this graph
    void init(int n);
    // initialize this graph by copying another
    void init(const Graph &graph);
private:
    int numV, numE; // number of vertices and edges
    std::vector< std::pair<int, int> >* adjList; // adjacency list
};

#endif

图形.cpp

#include "Graph.h"
#include <algorithm>
#include <map>

Graph::Graph()
:numV(0), numE(0), adjList(0)
{
}

Graph::Graph(int n)
:numV(0), numE(0), adjList(0)
{
    this->init(n);
}

Graph::Graph(const Graph &graph)
:numV(0), numE(0), adjList(0)
{
    this->init(graph);
}

Graph::~Graph()
{
    delete[] this->adjList;
}

void Graph::init(int n)
{
    if(this->adjList){
        delete[] this->adjList;
    }
    this->numV = n;
    this->numE = 0;
    this->adjList = new std::vector< std::pair<int, int> >[n];
}

void Graph::init(const Graph &graph)
{
    this->init(graph.numV);    
    for(int i = 0; i < numV; i++){
        this->adjList[i] = graph.adjList[i];
    }
}

void Graph::addEdge(int from, int to, int weight)
{
    if(weight > 0){
        this->adjList[from].push_back( std::make_pair(to, weight) );
        this->numE++;
    }
}

void Graph::getAllEdges(edge_t edgeList[])
{
    int k = 0;
    for(int i = 0; i < numV; i++){
        for(int j = 0; j < this->adjList[i].size(); j++){
            // add this edge to edgeList
            edgeList[k++] = edge_t(i, this->adjList[i][j].first, this->adjList[i][j].second);
        }
    }
}

void Graph::sort(int vertexList[])
{
    std::pair<int, int>* timestamp = new std::pair<int, int>[this->numV];
    std::stack<int> order;

    for(int i = 0; i < this->numV; i++){
        timestamp[i].first = -1;
        timestamp[i].second = -1;
    }

    for(int v = 0; v < this->numV; v++){
        if(timestamp[v].first < 0){
            this->sort(v, timestamp, order);
        }
    }

    int i = 0;
    while(!order.empty()){
        vertexList[i++] = order.top();
        order.pop();
    }
    delete[] timestamp;
    return;
}

void Graph::sort(int v, std::pair<int, int> timestamp[], std::stack<int> &order)
{
    // discover vertex v
    timestamp[v].first = 1;

    for(int i = 0; i < this->adjList[v].size(); i++){
        int next = this->adjList[v][i].first;
        if(timestamp[next].first < 0){
            this->sort(next, timestamp, order);
        }
    }
    // finish vertex v
    timestamp[v].second = 1;
    order.push(v);
    return;
}

void Graph::dijkstra(int v, std::pair<int, int> path[])
{
    int* q = new int[numV];
    int numQ = numV;

    for(int i = 0; i < this->numV; i++){
        path[i].first = -1; // infinity distance
        path[i].second = -1; // no path exists
        q[i] = i;
    }

    // instant reachable to itself
    path[v].first = 0;
    path[v].second = -1;

    while(numQ > 0){
        int u = -1; // such node not exists
        for(int i = 0; i < numV; i++){
            if(q[i] >= 0 
            && path[i].first >= 0 
            && (u < 0 || path[i].first < path[u].first)){ // 
                u = i;
            }
        }


        if(u == -1){
            // all remaining nodes are unreachible
            break;
        }
        // remove u from Q
        q[u] = -1;
        numQ--;

        for(int i = 0; i < this->adjList[u].size(); i++){
            std::pair<int, int>& edge = this->adjList[u][i];
            int alt = path[u].first + edge.second;

            if(path[edge.first].first < 0 || alt < path[ edge.first ].first){
                path[ edge.first ].first = alt;
                path[ edge.first ].second = u;
            }
        }
    }

    delete[] q;
    return;
}

// compare two edges by their weight
bool edgeCmp(edge_t e0, edge_t e1)
{
    return e0.w < e1.w;
}

std::set<int>* Graph::findSet(int v, std::set<int> vertexSet[], int n)
{
    for(int i = 0; i < n; i++){
        if(vertexSet[i].find(v) != vertexSet[i].end()){
            return vertexSet+i;
        }
    }
    return 0;
}

void Graph::setUnion(std::set<int>* s0, std::set<int>* s1)
{
    if(s1->size() > s0->size()){
        std::set<int>* temp = s0;
        s0 = s1;
        s1 = temp;
    }

    for(std::set<int>::iterator i = s1->begin(); i != s1->end(); i++){
        s0->insert(*i);
    }
    s1->clear();
    return;
}

void Graph::kruskal(Graph &graph)
{
    std::vector<edge_t> edgeList;
    edgeList.reserve(numE);
    for(int i = 0; i < numV; i++){
        for(int j = 0; j < this->adjList[i].size(); j++){
            // add this edge to edgeList
            edgeList.push_back( edge_t(i, this->adjList[i][j].first, this->adjList[i][j].second) );
        }
    }

    // sort the list in ascending order
    std::sort(edgeList.begin(), edgeList.end(), edgeCmp);

    graph.init(numV);   
    // create disjoint set of the spanning tree constructed so far
    std::set<int>* disjoint = new std::set<int>[this->numV];
    for(int i = 0; i < numV; i++){
        disjoint[i].insert(i);
    }

    for(int e = 0; e < edgeList.size(); e++){
        // consider edgeList[e]
        std::set<int>* s0 = this->findSet(edgeList[e].v0, disjoint, numV);
        std::set<int>* s1 = this->findSet(edgeList[e].v1, disjoint, numV);
        if(s0 == s1){
            // adding this edge will make a cycle
            continue;
        }

        // add this edge to MST
        graph.addEdge(edgeList[e].v0, edgeList[e].v1, edgeList[e].w);
        // union s0 & s1
        this->setUnion(s0, s1);
    }
    delete[] disjoint;
    return;
}

#define IDX(i,j)    ((i)*numV+(j))

void Graph::floydWarshall(std::pair<int, int> path[])
{
    // initialize
    for(int i = 0; i < numV; i++){
        for(int j = 0; j < numV; j++){
            path[IDX(i,j)].first = -1;
            path[IDX(i,j)].second = -1;
        }
    }
    for(int i = 0; i < numV; i++){
        for(int j = 0; j < this->adjList[i].size(); j++){
            path[IDX(i,this->adjList[i][j].first)].first
                = this->adjList[i][j].second;
            path[IDX(i,this->adjList[i][j].first)].second
                = this->adjList[i][j].first;
        }
    }

    // dynamic programming
    for(int k = 0; k < numV; k++){
        for(int i = 0; i < numV; i++){
            for(int j = 0; j < numV; j++){
                if(path[IDX(i,k)].first == -1
                || path[IDX(k,j)].first == -1){
                    // no path exist from i-to-k or from k-to-j
                    continue;
                }

                if(path[IDX(i,j)].first == -1
                || path[IDX(i,j)].first > path[IDX(i,k)].first + path[IDX(k,j)].first){
                    // there is a shorter path from i-to-k, and from k-to-j
                    path[IDX(i,j)].first = path[IDX(i,k)].first + path[IDX(k,j)].first;
                    path[IDX(i,j)].second = k;
                }
            }
        }
    }
    return;
}
于 2012-11-19T06:00:30.857 回答
3

如果我正确理解编辑的问题，您的图表是一个循环链表：每个节点指向前一个和下一个节点，“最后一个”节点指向“第一个”节点作为其下一个节点。

没有什么特别的，你需要做你想要的那种。这是我将使用的基本步骤。

  1. 将所有节点放入一个数组中。
  2. 使用任何排序算法（例如qsort）对数组进行排序。
  3. 循环遍历结果并重置每个节点的 prev/next 指针，同时考虑到第一个和最后一个节点的特殊情况。
于 2012-11-19T06:25:28.253 回答
1

如果你正在寻找排序算法，你应该问谷歌：

http://en.wikipedia.org/wiki/Sorting_algorithm

我个人最喜欢的是 BogoSort 加上平行宇宙理论。该理论是，如果您将一台机器连接到可以破坏宇宙的程序，那么如果列表在一次迭代后没有排序，它将破坏宇宙。这样，除了列表排序的平行宇宙之外的所有平行宇宙都将被破坏，并且您有一个复杂度为 O(1) 的排序算法。

最好的 ....

于 2012-11-19T05:55:02.063 回答
0

创建一个这样的结构：

template<typename Container, typename Comparison = std::less<typename Container::value_type>>
struct SortHelper
{
    Container const* container;
    size_t org_index;
    SortHelper( Container const* c, size_t index ):container(c), org_index(index) {}
    bool operator<( SortHelper other ) const
    {
      return Comparison()( (*c)[org_index], (*other.c)[other.org_index] );
    }
};

这使您可以随心所欲地处理事情。

现在，制作一个std::vector<SortHelper<blah>>，对其进行排序，您现在有一个vector说明，说明在您排序后一切最终会发生在哪里。

应用这些说明（有几种方法）。一种简单的方法是将container指针重用为布尔值。走那帮vector帮手。将第一个条目移动到它应该去的地方，将你找到的东西移动到它应该去的地方，然后重复，直到你循环或整个数组被排序。当你走的时候，清除container你的帮助结构中的指针，并检查它们以确保你没有移动已经移动的条目（例如，这可以让你检测循环）。

一旦发生循环，继续vector寻找下一个尚未正确放置的条目（带有非空container指针）。

于 2012-11-19T06:33:34.527 回答