DataStruct/Topologic_sort_DFS.cpp at master · githubdlj/DataStruct · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
/********************************************************************
	Time:	  2015/11/11
	Filename: Topologic_sort_DFS
	Author:	  dinglj

	Purpose:  拓扑排序，有向图
              DFS实现,邻接表
              时间复杂度 O(n + e),也就是邻接表DFS的时间复杂度

              拓扑排序可以用DFS实现
              反过来，图的遍历也可以用拓扑排序来实现
*********************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

#define MAXSIZE 20
//////////////////////////////////////////////////////////////////////
//   边结构
typedef struct
{
    int weight;
}EdgeType;
typedef struct Node
{
    EdgeType e;

    int adjvex;
    struct Node *next;
}ENode;

//  顶点结构
typedef struct
{
    int no;
    char info;
}VertexType;

typedef struct
{
    VertexType v;
    ENode *firstNode;
}VNode;

//  邻接表
typedef struct
{
    VNode adjList[MAXSIZE];

    int vertexNum;
    int edgeNum;
}AGraph;

/********************************************************************
	Method:    DFS
	Parameter:
	Returns:

	Purpose:

*********************************************************************/
//  辅助存储结构, 标记顶点是否已被访问
bool isVisited[MAXSIZE];

//  辅助存储结构，保存退栈顶点
int stack[MAXSIZE], top = -1;

//////////////////////////////////////////////////////////////////////
void DFS(AGraph G, int v)
{
//    cout << v;
    isVisited[v] = true;

    ENode *pENode = G.adjList[v].firstNode;
    while (NULL != pENode)
    {
        if (false == isVisited[pENode->adjvex])
        {
            DFS(G, pENode->adjvex);
        }
        pENode = pENode->next;
    }

    //  退出DFS时候, 将退站顶点入栈
    top++;
    stack[top] = v;
}

/********************************************************************
	Method:    Topologic_sort
	Parameter:
	Returns:

	Purpose:

*********************************************************************/
bool Topologic_sort(AGraph G)
{
    for (int vertexNo = 0; vertexNo < G.vertexNum; ++vertexNo)
    {
        isVisited[vertexNo] =  false;
    }

    for (int vertexNo = 0; vertexNo < G.vertexNum; ++vertexNo)
    {
        if (false == isVisited[vertexNo])
        {
            DFS(G, vertexNo);
        }
    }

    //  输出序列
    if (top == G.vertexNum - 1)
    {
        while (-1 != top)
        {
            cout << stack[top] << "\t";
            top--;
        }
        return true;
    }
    else    //  有环
    {
        return false;
    }
}