有向图的拓扑排序

andalousie

对于有向图，只需要在IsConnected里面只定义一个方向值等于一，另一个值不定义即可。graph.h

#if !defined (GRAPH_H)
#define GRAPH_H
#include "stack.h"

/************************************************************

Class Graph represents a Graph [V,E] having vertices V and
edges E.

************************************************************/
class Graph {
    private:
        int    _n;  /// n is the number of vertices in the graph
        int ** _A;  /// A stores the edges between two vertices
        bool * visited;
        IStack reverse;
    public:
        Graph(int size = 2);
        ~Graph();
        bool isConnected(int, int);
        void addEdge(int x, int y);
        void DFS(int);
        void Toposort();
};

#endif

graph.cc

#include <iostream>
#include "graph.h"
#include "stack.h"

Graph::Graph(int size) {
    int i, j;
    if (size < 2) _n = 2;
    else _n = size;
    _A = new int*[_n];
    for (i = 0; i < _n; ++i)
        _A[i] = new int[_n];
    for (i = 0; i < _n; ++i)
        for (j = 0; j < _n; ++j)
            _A[i][j] = 0;
} 

Graph::~Graph() {
    for (int i = 0; i < _n; ++i)
    delete [] _A[i];
    delete [] _A;
    delete [] visited;
} 

/******************************************************
Checks if two given vertices are connected by an edge
@param u vertex
@param v vertex
@return true if connected false if not connected
******************************************************/
bool Graph::isConnected(int x, int y) {
    return (_A[x-1][y-1] == 1);
} 

/*****************************************************
adds an edge E to the graph G.
@param u vertex
@param v vertex
*****************************************************/
void Graph::addEdge(int x, int y) {
    _A[x-1][y-1] = 1;
}

/*****************************************************
performs Depth First Search
@param x initial vertex
*****************************************************/
void Graph::DFS(int v)
{
    visited[v] = true;
    for(int w = 1; w <= _n; ++w)
    {
            if(isConnected(v, w) && !visited[w]) DFS(w);
    }
    reverse.push(v);
}

void Graph::Toposort(){
        visited = new bool[_n+1];
        for (int i = 1; i <= _n; ++i)
        visited[i] = false;
    for (int v = 1; v <= _n; ++v)
    {
            if(!visited[v]) DFS(v);
    }
    while(!reverse.isEmpty())
            std::cout << reverse.pop() << " ";
}

stack.h, stack.cc参照我另一篇文章里面的代码。
Graph_search.cpp

#include <iostream>
#include "graph.h"
using namespace std;

int main(){    
        /** Creates a graph with 12 vertices */
    Graph g1(7);

    /** Adds edges to the graph */
    g1.addEdge(1, 6); g1.addEdge(1, 3);
    g1.addEdge(1, 2); g1.addEdge(4, 7);
    g1.addEdge(4, 6); g1.addEdge(4 ,5);
    g1.addEdge(6, 5); g1.addEdge(7, 5);
    g1.addEdge(7, 1); g1.addEdge(4, 3);
    g1.addEdge(2, 5);

    /** Explores all vertices findable from vertex 1 */
    g1.Toposort();
} 

cable5881

谢谢楼主分享！！！！！！！！

tlwangxd

学习

leslie初见

必须得顶下

tlwangxd

学习

Ayfkm

正在学习到需要用到这方面知识，谢谢楼主分享