老师扒下内裤让我爽了一夜 ,久久人人爽人人爽人人爽,欧美ⅴdeσsex性欧美

快捷導(dǎo)航

詳解C++實(shí)現(xiàn)拓?fù)渑判蛩惴?/h1>

更新時間：2021年06月11日 16:20:34 作者：Ouyang_Lianjun

拓?fù)渑判蚴菍σ粋€有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進(jìn)行拓?fù)渑判?，是將G中所有頂點(diǎn)排成一個線性序列，使得圖中任意一對頂點(diǎn)u和v，若邊(u,v)∈E(G)，則u在線性序列中出現(xiàn)在v之前。本文將對其原理進(jìn)行講解，并且用C++進(jìn)行實(shí)現(xiàn)

一、拓?fù)渑判虻慕榻B

拓?fù)渑判驅(qū)?yīng)施工的流程圖具有特別重要的作用，它可以決定哪些子工程必須要先執(zhí)行，哪些子工程要在某些工程執(zhí)行后才可以執(zhí)行。為了形象地反映出整個工程中各個子工程(活動)之間的先后關(guān)系，可用一個有向圖來表示，圖中的頂點(diǎn)代表活動(子工程)，圖中的有向邊代表活動的先后關(guān)系，即有向邊的起點(diǎn)的活動是終點(diǎn)活動的前序活動，只有當(dāng)起點(diǎn)活動完成之后，其終點(diǎn)活動才能進(jìn)行。通常，我們把這種頂點(diǎn)表示活動、邊表示活動間先后關(guān)系的有向圖稱做頂點(diǎn)活動網(wǎng)(Activity On Vertex network)，簡稱AOV網(wǎng)。

一個AOV網(wǎng)應(yīng)該是一個有向無環(huán)圖，即不應(yīng)該帶有回路，因?yàn)槿魩в谢芈?，則回路上的所有活動都無法進(jìn)行（對于數(shù)據(jù)流來說就是死循環(huán)）。在AOV網(wǎng)中，若不存在回路，則所有活動可排列成一個線性序列，使得每個活動的所有前驅(qū)活動都排在該活動的前面，我們把此序列叫做拓?fù)湫蛄?Topological order)，由AOV網(wǎng)構(gòu)造拓?fù)湫蛄械倪^程叫做拓?fù)渑判?Topological sort)。AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?，滿足上述定義的任一線性序列都稱作它的拓?fù)湫蛄小?/p>

二、拓?fù)渑判虻膶?shí)現(xiàn)步驟

1.在有向圖中選一個沒有前驅(qū)的頂點(diǎn)并且輸出

2.從圖中刪除該頂點(diǎn)和所有以它為尾的?。ò自捑褪牵簞h除所有和它有關(guān)的邊）

3.重復(fù)上述兩步，直至所有頂點(diǎn)輸出，或者當(dāng)前圖中不存在無前驅(qū)的頂點(diǎn)為止，后者代表我們的有向圖是有環(huán)的，因此，也可以通過拓?fù)渑判騺砼袛嘁粋€圖是否有環(huán)。

三、拓?fù)渑判蚴纠謩訉?shí)現(xiàn)

如果我們有如下的一個有向無環(huán)圖，我們需要對這個圖的頂點(diǎn)進(jìn)行拓?fù)渑判?，過程如下：

這里寫圖片描述

首先，我們發(fā)現(xiàn)V6和v1是沒有前驅(qū)的，所以我們就隨機(jī)選去一個輸出，我們先輸出V6，刪除和V6有關(guān)的邊，得到如下圖結(jié)果：

這里寫圖片描述

然后，我們繼續(xù)尋找沒有前驅(qū)的頂點(diǎn)，發(fā)現(xiàn)V1沒有前驅(qū)，所以輸出V1，刪除和V1有關(guān)的邊，得到下圖的結(jié)果：

這里寫圖片描述

然后，我們又發(fā)現(xiàn)V4和V3都是沒有前驅(qū)的，那么我們就隨機(jī)選取一個頂點(diǎn)輸出（具體看你實(shí)現(xiàn)的算法和圖存儲結(jié)構(gòu)），我們輸出V4，得到如下圖結(jié)果：

這里寫圖片描述

然后，我們輸出沒有前驅(qū)的頂點(diǎn)V3，得到如下結(jié)果：

這里寫圖片描述

然后，我們分別輸出V5和V2，最后全部頂點(diǎn)輸出完成，該圖的一個拓?fù)湫蛄袨椋?/p>

v6–>v1—->v4—>v3—>v5—>v2

四、拓?fù)渑判虻拇a實(shí)現(xiàn)

下面，我們將用兩種方法來實(shí)現(xiàn)我么的拓?fù)渑判颍?/p>

1.Kahn算法

2.基于DFS的拓?fù)渑判蛩惴?/p>

首先我們先介紹第一個算法的思路：

Kahn的算法的思路其實(shí)就是我們之前那個手動展示的拓?fù)渑判虻膶?shí)現(xiàn)，我們先使用一個棧保存入度為0 的頂點(diǎn)，然后輸出棧頂元素并且將和棧頂元素有關(guān)的邊刪除，減少和棧頂元素有關(guān)的頂點(diǎn)的入度數(shù)量并且把入度減少到0的頂點(diǎn)也入棧。具體的代碼如下：

bool Graph_DG::topological_sort() {
    cout << "圖的拓?fù)湫蛄袨椋? << endl;
    //棧s用于保存棧為空的頂點(diǎn)下標(biāo)
    stack<int> s;
    int i;
    ArcNode * temp;
    //計算每個頂點(diǎn)的入度，保存在indgree數(shù)組中
    for (i = 0; i != this->vexnum; i++) {
        temp = this->arc[i].firstarc;
        while (temp) {
            ++this->indegree[temp->adjvex];
            temp = temp->next;
        }

    }

    //把入度為0的頂點(diǎn)入棧
    for (i = 0; i != this->vexnum; i++) {
        if (!indegree[i]) {
            s.push(i); 
        }
    }
    //count用于計算輸出的頂點(diǎn)個數(shù)
    int count=0;
    while (!s.empty()) {//如果棧為空，則結(jié)束循環(huán)
        i = s.top();
        s.pop();//保存棧頂元素，并且棧頂元素出棧
        cout << this->arc[i].data<<" ";//輸出拓?fù)湫蛄?
        temp = this->arc[i].firstarc;
        while (temp) {
            if (!(--this->indegree[temp->adjvex])) {//如果入度減少到為0，則入棧
                s.push(temp->adjvex);
            }
            temp = temp->next;
        }
        ++count;
    }
    if (count == this->vexnum) {
        cout << endl;
        return true;
    } 
    cout << "此圖有環(huán)，無拓?fù)湫蛄? << endl;
    return false;//說明這個圖有環(huán)
}

現(xiàn)在，我們來介紹第二個算法的思路：
其實(shí)DFS就是深度優(yōu)先搜索，它每次都沿著一條路徑一直往下搜索，知道某個頂點(diǎn)沒有了出度時，就停止遞歸，往回走，所以我們就用DFS的這個思路，我們可以得到一個有向無環(huán)圖的拓?fù)湫蛄?，其?shí)DFS很像Kahn算法的逆過程。具體的代碼實(shí)現(xiàn)如下：

bool Graph_DG::topological_sort_by_dfs() {
    stack<string> result;
    int i;
    bool * visit = new bool[this->vexnum];
    //初始化我們的visit數(shù)組
    memset(visit, 0, this->vexnum);
    cout << "基于DFS的拓?fù)渑判驗(yàn)椋? << endl;
    //開始執(zhí)行DFS算法
    for (i = 0; i < this->vexnum; i++) {
        if (!visit[i]) {
            dfs(i, visit, result);
        }
    }
    //輸出拓?fù)湫蛄?，因?yàn)槲覀兠看味际钦业搅顺龆葹?的頂點(diǎn)加入棧中，
    //所以輸出時其實(shí)就要逆序輸出，這樣就是每次都是輸出入度為0的頂點(diǎn)
    for (i = 0; i < this->vexnum; i++) {
        cout << result.top() << " ";
        result.pop();
    }
    cout << endl;
    return true;
}
void Graph_DG::dfs(int n, bool * & visit, stack<string> & result) {

        visit[n] = true;
        ArcNode * temp = this->arc[n].firstarc;
        while (temp) {
            if (!visit[temp->adjvex]) {
                dfs(temp->adjvex, visit,result);
            }
            temp = temp->next;
        }
        //由于加入頂點(diǎn)到集合中的時機(jī)是在dfs方法即將退出之時，
        //而dfs方法本身是個遞歸方法，
        //僅僅要當(dāng)前頂點(diǎn)還存在邊指向其他不論什么頂點(diǎn)，
        //它就會遞歸調(diào)用dfs方法，而不會退出。
        //因此，退出dfs方法，意味著當(dāng)前頂點(diǎn)沒有指向其他頂點(diǎn)的邊了
        //，即當(dāng)前頂點(diǎn)是一條路徑上的最后一個頂點(diǎn)。
        //換句話說其實(shí)就是此時該頂點(diǎn)出度為0了
        result.push(this->arc[n].data);

}

兩種算法總結(jié)：

對于基于DFS的算法，增加結(jié)果集的條件是：頂點(diǎn)的出度為0。這個條件和Kahn算法中入度為0的頂點(diǎn)集合似乎有著異曲同工之妙，Kahn算法不須要檢測圖是否為DAG，假設(shè)圖為DAG，那么在入度為0的棧為空之后，圖中還存在沒有被移除的邊，這就說明了圖中存在環(huán)路。而基于DFS的算法須要首先確定圖為DAG，當(dāng)然也可以做出適當(dāng)調(diào)整，讓環(huán)路的檢測測和拓?fù)渑判蛲粫r候進(jìn)行，畢竟環(huán)路檢測也可以在DFS的基礎(chǔ)上進(jìn)行。

二者的復(fù)雜度均為O(V+E)。

五、完整的代碼和輸出展示

topological_sort.h文件的代碼

#pragma once
//#pragma once是一個比較常用的C/C++雜注，
//只要在頭文件的最開始加入這條雜注，
//就能夠保證頭文件只被編譯一次。

/*
拓?fù)渑判虮仨毷菍τ邢驁D的操作
算法實(shí)現(xiàn)：
（1）Kahn算法
（2）DFS算法
采用鄰接表存儲圖
*/
#include<iostream>
#include<string>
#include<stack>
using namespace std;
//表結(jié)點(diǎn)
struct ArcNode {
    ArcNode * next; //下一個關(guān)聯(lián)的邊
    int adjvex;   //保存弧尾頂點(diǎn)在頂點(diǎn)表中的下標(biāo)
};
struct Vnode {
    string data; //頂點(diǎn)名稱
    ArcNode * firstarc; //第一個依附在該頂點(diǎn)邊
};

class Graph_DG {
private:
    int vexnum; //圖的頂點(diǎn)數(shù)
    int edge;   //圖的邊數(shù)
    int * indegree; //每條邊的入度情況
    Vnode * arc; //鄰接表
public:
    Graph_DG(int, int);
    ~Graph_DG();
    //檢查輸入邊的頂點(diǎn)是否合法
    bool check_edge_value(int,int);
    //創(chuàng)建一個圖
    void createGraph();
    //打印鄰接表
    void print();
    //進(jìn)行拓?fù)渑判?Kahn算法
    bool topological_sort();
    //進(jìn)行拓?fù)渑判?，DFS算法
    bool topological_sort_by_dfs();
    void dfs(int n,bool * & visit, stack<string> & result);
};

topological_sort.cpp文件代碼

#include"topological_sort.h"

Graph_DG::Graph_DG(int vexnum, int edge) {
    this->vexnum = vexnum;
    this->edge = edge;
    this->arc = new Vnode[this->vexnum];
    this->indegree = new int[this->vexnum];
    for (int i = 0; i < this->vexnum; i++) {
        this->indegree[i] = 0;
        this->arc[i].firstarc = NULL;
        this->arc[i].data = "v" + to_string(i + 1);
    }
}
//釋放內(nèi)存空間
Graph_DG::~Graph_DG() {
    ArcNode * p, *q;
    for (int i = 0; i < this->vexnum; i++) {
        if (this->arc[i].firstarc) {
            p = this->arc[i].firstarc;
            while (p) {
                q = p->next;
                delete p;
                p = q;
            }
        }
    }
    delete [] this->arc;
    delete [] this->indegree;
}
//判斷我們每次輸入的的邊的信息是否合法
//頂點(diǎn)從1開始編號
bool Graph_DG::check_edge_value(int start, int end) {
    if (start<1 || end<1 || start>vexnum || end>vexnum) {
        return false;
    }
    return true;
}
void Graph_DG::createGraph() {
    int count = 0;
    int start, end;
    cout << "輸入每條起點(diǎn)和終點(diǎn)的頂點(diǎn)編號（從1開始編號）" << endl;
    while (count != this->edge) {
        cin >> start;
        cin >> end;
        //檢查邊是否合法
        while (!this->check_edge_value(start, end)) {
            cout << "輸入的頂點(diǎn)不合法，請重新輸入" << endl;
            cin >> start;
            cin >> end;
        }
        //聲明一個新的表結(jié)點(diǎn)
        ArcNode * temp = new ArcNode;
        temp->adjvex = end - 1;
        temp->next = NULL;
        //如果當(dāng)前頂點(diǎn)的還沒有邊依附時，
        if (this->arc[start - 1].firstarc == NULL) {
            this->arc[start - 1].firstarc = temp;
        }
        else {
            ArcNode * now = this->arc[start - 1].firstarc;
            while(now->next) {
                now = now->next;
            }//找到該鏈表的最后一個結(jié)點(diǎn)
            now->next = temp;
        }
        ++count;
    }
}
void Graph_DG::print() {
    int count = 0;
    cout << "圖的鄰接矩陣為：" << endl;
    //遍歷鏈表，輸出鏈表的內(nèi)容
    while (count != this->vexnum) {
        //輸出鏈表的結(jié)點(diǎn)
        cout << this->arc[count].data<<" ";
        ArcNode * temp = this->arc[count].firstarc;
        while (temp) {
            cout<<"<"<< this->arc[count].data<<","<< this->arc[temp->adjvex].data<<"> ";
            temp = temp->next;
        }
        cout << "^" << endl;
        ++count;
    }
}

bool Graph_DG::topological_sort() {
    cout << "圖的拓?fù)湫蛄袨椋? << endl;
    //棧s用于保存棧為空的頂點(diǎn)下標(biāo)
    stack<int> s;
    int i;
    ArcNode * temp;
    //計算每個頂點(diǎn)的入度，保存在indgree數(shù)組中
    for (i = 0; i != this->vexnum; i++) {
        temp = this->arc[i].firstarc;
        while (temp) {
            ++this->indegree[temp->adjvex];
            temp = temp->next;
        }

    }

    //把入度為0的頂點(diǎn)入棧
    for (i = 0; i != this->vexnum; i++) {
        if (!indegree[i]) {
            s.push(i); 
        }
    }
    //count用于計算輸出的頂點(diǎn)個數(shù)
    int count=0;
    while (!s.empty()) {//如果棧為空，則結(jié)束循環(huán)
        i = s.top();
        s.pop();//保存棧頂元素，并且棧頂元素出棧
        cout << this->arc[i].data<<" ";//輸出拓?fù)湫蛄?
        temp = this->arc[i].firstarc;
        while (temp) {
            if (!(--this->indegree[temp->adjvex])) {//如果入度減少到為0，則入棧
                s.push(temp->adjvex);
            }
            temp = temp->next;
        }
        ++count;
    }
    if (count == this->vexnum) {
        cout << endl;
        return true;
    } 
    cout << "此圖有環(huán)，無拓?fù)湫蛄? << endl;
    return false;//說明這個圖有環(huán)
}
bool Graph_DG::topological_sort_by_dfs() {
    stack<string> result;
    int i;
    bool * visit = new bool[this->vexnum];
    //初始化我們的visit數(shù)組
    memset(visit, 0, this->vexnum);
    cout << "基于DFS的拓?fù)渑判驗(yàn)椋? << endl;
    //開始執(zhí)行DFS算法
    for (i = 0; i < this->vexnum; i++) {
        if (!visit[i]) {
            dfs(i, visit, result);
        }
    }
    //輸出拓?fù)湫蛄?，因?yàn)槲覀兠看味际钦业搅顺龆葹?的頂點(diǎn)加入棧中，
    //所以輸出時其實(shí)就要逆序輸出，這樣就是每次都是輸出入度為0的頂點(diǎn)
    for (i = 0; i < this->vexnum; i++) {
        cout << result.top() << " ";
        result.pop();
    }
    cout << endl;
    return true;
}
void Graph_DG::dfs(int n, bool * & visit, stack<string> & result) {

        visit[n] = true;
        ArcNode * temp = this->arc[n].firstarc;
        while (temp) {
            if (!visit[temp->adjvex]) {
                dfs(temp->adjvex, visit,result);
            }
            temp = temp->next;
        }
        //由于加入頂點(diǎn)到集合中的時機(jī)是在dfs方法即將退出之時，
        //而dfs方法本身是個遞歸方法，
        //僅僅要當(dāng)前頂點(diǎn)還存在邊指向其他不論什么頂點(diǎn)，
        //它就會遞歸調(diào)用dfs方法，而不會退出。
        //因此，退出dfs方法，意味著當(dāng)前頂點(diǎn)沒有指向其他頂點(diǎn)的邊了
        //，即當(dāng)前頂點(diǎn)是一條路徑上的最后一個頂點(diǎn)。
        //換句話說其實(shí)就是此時該頂點(diǎn)出度為0了
        result.push(this->arc[n].data);

}

main.cpp文件：

#include"topological_sort.h"

//檢驗(yàn)輸入邊數(shù)和頂點(diǎn)數(shù)的值是否有效，可以自己推算為啥：
//頂點(diǎn)數(shù)和邊數(shù)的關(guān)系是：((Vexnum*(Vexnum - 1)) / 2) < edge
bool check(int Vexnum, int edge) {
    if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge)
        return false;
    return true;
}
int main() {
    int vexnum; int edge;


    cout << "輸入圖的頂點(diǎn)個數(shù)和邊的條數(shù)：" << endl;
    cin >> vexnum >> edge;
    while (!check(vexnum, edge)) {
        cout << "輸入的數(shù)值不合法，請重新輸入" << endl;
        cin >> vexnum >> edge;
    }
    Graph_DG graph(vexnum, edge);
    graph.createGraph();
    graph.print();
    graph.topological_sort();
    graph.topological_sort_by_dfs();
    system("pause");
    return 0;

}

輸入：