andalousie 发表于 2014-2-18 11:00:22

有向图的拓扑排序

本帖最后由 andalousie 于 2014-2-18 11:03 编辑

对于有向图，只需要在IsConnected里面只定义一个方向值等于一，另一个值不定义即可。graph.h
#if !defined (GRAPH_H)
#define GRAPH_H
#include "stack.h"

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

Class Graph represents a Graph 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();
};

#endifgraph.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*;
    for (i = 0; i < _n; ++i)
      _A = new int;
    for (i = 0; i < _n; ++i)
      for (j = 0; j < _n; ++j)
            _A = 0;
}

Graph::~Graph() {
    for (int i = 0; i < _n; ++i)
    delete [] _A;
    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 == 1);
}

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

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

void Graph::Toposort(){
      visited = new bool;
      for (int i = 1; i <= _n; ++i)
      visited = false;
    for (int v = 1; v <= _n; ++v)
    {
            if(!visited) 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 发表于 2014-8-12 08:13:29

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

tlwangxd 发表于 2014-11-18 09:31:05

学习

leslie初见 发表于 2014-11-26 20:16:26


必须得顶下

tlwangxd 发表于 2014-12-10 09:16:22

学习

Ayfkm 发表于 2014-12-17 22:54:32

正在学习到需要用到这方面知识，谢谢楼主分享
页: [1]
查看完整版本: 有向图的拓扑排序