Notes
  1. 数据结构：图 的操作集 C/C++代码实现

1. 图 - 邻接矩阵

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
#include <iostream>
using namespace std;

#define MaxVertexNum 100        // 最大顶点数
typedef int WeightType;         // 权值
typedef int Vertex;             // 顶点
typedef int DataType;           // 数据

// 边
typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;              // < V1, V2 > 有向边
    WeightType Weight;          // 权重
};
typedef PtrToENode Edge;

// 图
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;                     // 顶点数
    int Ne;                     // 边数
    WeightType G[MaxVertexNum][MaxVertexNum];   // 邻接矩阵
    DataType Data[MaxVertexNum];                // 数据
};
typedef PtrToGNode MGraph;

MGraph CreateGraph(int VertexNum);          // 初始化图
void InsertEdge(MGraph Graph, Edge E);      // 插入边
MGraph BuildGraph();                        // 建图

MGraph CreateGraph(int VertexNum)
{
    Vertex v, w;
    MGraph Graph = new struct GNode;
    Graph->Nv = VertexNum;
    Graph->Ne = 0;

    for(v=0; v<VertexNum; v++)
        for(w=0; w<VertexNum; w++)  Graph->G[v][w] = 0;

    return Graph;
}

void InsertEdge(MGraph Graph, Edge E)
{
    Graph->G[E->V1][E->V2] = E->Weight;
    // 若为无向图，需要插入下面那行
    Graph->G[E->V2][E->V1] = E->Weight;
}

MGraph BuildGraph()
{
    MGraph Graph;
    Edge E;
    Vertex V;
    int Nv;
    cin >> Nv;
    Graph = CreateGraph(Nv);
    cin >> Graph->Ne;
    if(Graph->Ne != 0)
    {
        E = new struct ENode;
        for(int i=0; i<Graph->Ne; i++)
        {
            cin >> E->V1 >> E->V2 >> E->Weight;
            InsertEdge(Graph, E);
        }
    }
    return Graph;
}




2. 图 - 邻接表

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
#include <iostream>
using namespace std;

#define MaxVertexNum 100        // 最大顶点数
typedef int Vertex;             // 顶点
typedef int WeightType;         // 边的权值
typedef int DataType;           // 数据

// 边
typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;          // 有向边 <V1, V2>
    WeightType Weight;      // 权重
};
typedef PtrToENode Edge;

// 邻接点
typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
    Vertex ADjV;            // 邻接点下标
    WeightType Weight;      // 边权重
    PtrToAdjVNode Next;     // 指针
};

// 顶点表头结点
typedef struct VNode{
    PtrToAdjVNode FirstEdge;    // 边表头结点
    DataType Data;              // 数据
}AdjList[MaxVertexNum];         // 邻接表类型

// 图
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;                     // 顶点数
    int Ne;                     // 边数
    AdjList G;                  // 邻接表
};
typedef PtrToGNode LGraph;      // 邻接表-图类型

// 操作集
LGraph CreateGraph(int VertexNum);      // 初始化图
void InsertEdge(LGraph Graph, Edge E);  // 插入边
LGraph BuildGraph();                    // 建图

// 操作集实现
LGraph CreateGraph(int VertexNum)
{
    Vertex v, w;
    LGraph Graph = new struct GNode;
    Graph->Nv = VertexNum;
    Graph->Ne = 0;

    for(v=0; v<Graph->Nv; v++)  Graph->G[v].FirstEdge = NULL;
    return Graph;
}

void InsertEdge(LGraph Graph, Edge E)
{
    PtrToAdjVNode newNode;
    newNode = new struct AdjVNode;
    // 插入 <V1, V2>
    newNode->ADjV = E->V2;
    newNode->Weight = E->Weight;
    newNode->Next = Graph->G[E->V1].FirstEdge;  // 旧表头接在新结点的后面
    Graph->G[E->V1].FirstEdge = newNode;        // 新结点成为新的表头

    // 插入 <V2, V1>   <---- 无向图
    newNode = new struct AdjVNode;
    newNode->ADjV = E->V1;
    newNode->Weight = E->Weight;
    newNode->Next = Graph->G[E->V2].FirstEdge;  // 旧表头接在新结点的后面
    Graph->G[E->V2].FirstEdge = newNode;        // 新结点成为新的表头
}

LGraph BuildGraph()
{
    LGraph Graph;
    Edge E;
    Vertex V;
    int Nv;
    cin >> Nv;
    Graph = CreateGraph(Nv);
    cin >> Graph->Ne;
    if(Graph->Ne)
        for(int i=0; i<Graph->Ne; i++)
        {
            E = new struct ENode;
            cin >> E->V1 >> E->V2 >> E->Weight;
            InsertEdge(Graph, E);
        }
    return Graph;
}




3. DFS - 深度优先搜索

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
#include <iostream>
using namespace std;
// DFS 深度优先搜索 算法

bool Visited[10] = {0};

#define MaxVertexNum 100        // 最大顶点数
typedef int Vertex;             // 顶点
typedef int WeightType;         // 边的权值
typedef int DataType;           // 数据

// 边
typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;          // 有向边 <V1, V2>
    WeightType Weight;      // 权重
};
typedef PtrToENode Edge;

// 邻接点
typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
    Vertex ADjV;            // 邻接点下标
    WeightType Weight;      // 边权重
    PtrToAdjVNode Next;     // 指针
};

// 顶点表头结点
typedef struct VNode{
    PtrToAdjVNode FirstEdge;    // 边表头结点
    DataType Data;              // 数据
}AdjList[MaxVertexNum];         // 邻接表类型

// 图
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;                     // 顶点数
    int Ne;                     // 边数
    AdjList G;                  // 邻接表
};
typedef PtrToGNode LGraph;      // 邻接表-图类型

// 操作集
void Visit(Vertex V);
void DFS(LGraph Graph, Vertex V);

void Visit(Vertex V)
{
    cout << "This Vertex is: " << V << endl;
}

void DFS(LGraph Graph, Vertex V, void (*Visit)(Vertex))
{
    PtrToAdjVNode W;
    Visit(V);
    Visited[V] = true;

    for(W=Graph->G[V].FirstEdge; W; W=W->Next)
        if(!Visited[W->ADjV])  DFS(Graph, W->ADjV, Visit);
}




4. BFS - 广度优先搜索

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
#include <iostream>
#include <queue>
using namespace std;
// BFS 广度优先搜索 算法


#define MaxVertexNum 100        // 最大顶点数
typedef int WeightType;         // 权值
typedef int Vertex;             // 顶点
typedef int DataType;           // 数据
bool Visited[10] = {0};

// 边
typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;              // < V1, V2 > 有向边
    WeightType Weight;          // 权重
};
typedef PtrToENode Edge;

// 图
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;                     // 顶点数
    int Ne;                     // 边数
    WeightType G[MaxVertexNum][MaxVertexNum];   // 邻接矩阵
    DataType Data[MaxVertexNum];                // 数据
};
typedef PtrToGNode MGraph;

// 操作集
bool IsEdge(MGraph Graph, Vertex V, Vertex W);
void BFS(MGraph Graph, Vertex S, void (*Visit)(Vertex));
void Visit(Vertex V);


void Visit(Vertex V)
{
    cout << "This Vertex is: " << V << endl;
}

bool IsEdge(MGraph Graph, Vertex V, Vertex W)
{
    return (Graph->G[V][W]>0?true:false);
}

void BFS(MGraph Graph, Vertex S, void (*Visit)(Vertex))
{
    queue <Vertex> Q;
    Vertex V, W;

    Visit(S);
    Visited[S] = true;
    Q.push(S);

    while(!Q.empty())
    {
        V = Q.front();
        Q.pop();
        for(W=0; W<Graph->Nv; W++)
            if(!Visited[W] && IsEdge(Graph, V, W))
            {
                Visit(W);
                Visited[W] = true;
                Q.push(W);
            }
    }
}




5. 例题 - 六度空间 ( BFS算法邻接矩阵图 )

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
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
// 例题：六度空间 ---> BFS算法 - 邻接矩阵图

int ENode[1001][1001] = {0};
int Nv, Ne;

int BFS(int v)
{
    queue <int> Q;
    bool visited[1001] = {false};
    Q.push(v);
    int cnt=0, level=0, last=v, tail=v;
    while(!Q.empty())
    {
        v = Q.front();
        Q.pop();
        for(int w=1; w<=Nv; w++)
            if(!visited[w] && ENode[v][w])  Q.push(w), cnt++, tail = w, visited[w] = true;
            else continue;
        // cout << "V: " << v << ' ' << "Level:" << level << ' ' << tail << endl;
        if(v == last)  level++, last = tail;
        if(level == 6)  break;
    }
    return cnt;
}

int main()
{
    cin >> Nv >> Ne;
    for(int i=1; i<=Ne; i++)
    {
        int v, w;
        cin >> v >> w;
        ENode[v][w] = 1;
        ENode[w][v] = 1;
    }
    for(int v=1; v<=Nv; v++)
    {
        float tmp = BFS(v)/(Nv*1.0)*100;
        cout << v << ": ";
        printf("%.2f%\n", tmp);
    }
    return 0;
}




6. 无权图的最短路径问题

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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 邻接矩阵 - 无权图的单源最短路算法

#define MaxVertexNum 100        // 最大顶点数
typedef int WeightType;         // 权值
typedef int Vertex;             // 顶点
typedef int DataType;           // 数据

vector <int> dist(MaxVertexNum, -1);     // 存储路径, 并初始化为 -1      
vector <int> path(MaxVertexNum);         // 存储路径长度

// 边
typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;              // < V1, V2 > 有向边
    WeightType Weight;          // 权重
};
typedef PtrToENode Edge;

// 图
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;                     // 顶点数
    int Ne;                     // 边数
    WeightType G[MaxVertexNum][MaxVertexNum];   // 邻接矩阵
    DataType Data[MaxVertexNum];                // 数据
};
typedef PtrToGNode MGraph;

/* 邻接矩阵 - 无权图的单源最短路算法 */
void Unweighted(MGraph Graph, Vertex V);

void Unweighted(MGraph Graph, Vertex V)
{
	queue<Vertex> Q;
    dist[V] = 0, path[V] = -1;
    Q.push(V);
    while(!Q.empty())
    {
        V = Q.front();
        Q.pop();
        for(Vertex W=0; W < Graph->Nv; W++)
            if(Graph->G[V][W] && dist[W] == -1)
            {
                dist[W] = dist[V] + 1;
                path[W] = V;
                Q.push(W);
            }
    }
}




7. 邻接矩阵 - 有权图的单源最短路算法 - Dijkstra算法

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
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
// 邻接矩阵 - 有权图的单源最短路算法 - Dijkstra算法

#define MaxVertexNum 100        // 最大顶点数
#define Maxdist 100000000        // 最大顶点数
typedef int WeightType;         // 权值
typedef int Vertex;             // 顶点
typedef int DataType;           // 数据

vector <int> dist(MaxVertexNum, -1);              // 存储路径, 并初始化为 -1      
vector <int> path(MaxVertexNum, Maxdist);         // 存储路径长度, 并初始化为 Maxdist
vector <bool> collected(MaxVertexNum, false);     // 判断该Vertex是否收集, 并初始化为 false

// 边
typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;              // < V1, V2 > 有向边
    WeightType Weight;          // 权重
};
typedef PtrToENode Edge;

// 图
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;                     // 顶点数
    int Ne;                     // 边数
    WeightType G[MaxVertexNum][MaxVertexNum];   // 邻接矩阵
    DataType Data[MaxVertexNum];                // 数据
};
typedef PtrToGNode MGraph;

/* 邻接矩阵 - Dijkstra算法 */
void Dijkstra(MGraph Graph, Vertex V);

void Dijkstra(MGraph Graph, Vertex V)
{
    dist[V] = 0, path[V] = -1;
    collected[V] = true;
    for(Vertex W=0; W<Graph->Nv; W++)
        if(Graph->G[V][W])
        {
            dist[W] = dist[V] + Graph->G[V][W];
            path[W] = V;
        }

    while(1)
    {
        for(Vertex W=0; W<Graph->Nv; W++)
            if(V != W && !collected[W])  V = min(dist[W], Maxdist);
            else  V = 0;
        
        if(!V)  break;
        
        collected[V] = true;
        
        for(Vertex W=0; W<Graph->Nv; W++)
            if(Graph->G[V][W] && !collected[W])
                if(dist[V] + Graph->G[V][W] < dist[W])
                {
                    dist[W] = dist[V] + Graph->G[V][W];
                    path[W] = V;
                }
    }
}




8. 邻接矩阵 - 有权图的多源最短路算法 - Floyd算法

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
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
// 邻接矩阵 - 有权图的多源最短路算法 - Floyd算法

#define MaxVertexNum 100        // 最大顶点数
#define Maxdist 100000000        // 最大顶点数
typedef int WeightType;         // 权值
typedef int Vertex;             // 顶点
typedef int DataType;           // 数据

vector<vector<int>> dist(MaxVertexNum, vector<int>(MaxVertexNum, 0));          // 存储路径长度, 并初始化为 0      
vector<vector<int>> path(MaxVertexNum, vector<int>(MaxVertexNum, -1));         // 存储路径, 并初始化为 -1  

// 边
typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;              // < V1, V2 > 有向边
    WeightType Weight;          // 权重
};
typedef PtrToENode Edge;

// 图
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;                     // 顶点数
    int Ne;                     // 边数
    WeightType G[MaxVertexNum][MaxVertexNum];   // 邻接矩阵
    DataType Data[MaxVertexNum];                // 数据
};
typedef PtrToGNode MGraph;

/* 邻接矩阵 - Floyd算法 */
void Floyd(MGraph Graph, Vertex V);

void Floyd(MGraph Graph, Vertex V)
{
    Vertex i, j, k;
    for(i=0; i<Graph->Nv; i++)
        for(j=0; j<Graph->Nv; j++)
            if(i!=j)                                                // dist[i][j] 初始化为 0, 所以 i=j对角 均跳过(为默认值0)
                if(Graph->G[i][j])  dist[i][j] = Graph->G[i][j];    // 若Graph->G[i][j] 为 0, 则判定为 无边，因此初始化为Maxdist;
                else  dist[i][j] = Maxdist;

    for(k=0; k<Graph->Nv; k++)
        for(i=0; i<Graph->Nv; i++)
            for(j=0; j<Graph->Nv; j++)
                if(dist[i][k] + dist[k][j] < dist[i][j])  dist[i][j] = dist[i][k] + dist[k][j], path[i][j] = k;
}




9. 例题 - 哈利·波特的考试 ( BFS + Floyd 算法 )

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
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
// 邻接矩阵 - BFS + Floyd 算法

struct animalTra{
    int Ne;
    int Nv;
    int Weight[102][102] = {0};
};
typedef struct animalTra AniTran;

bool BFS_LT(AniTran Graph)
{
    queue <int> Q;
    Q.push(1);
    int v;
    bool res = true;
    int checked[102] = {0};
    checked[1] = 1;

    while(!Q.empty())
    {
        v = Q.front();
        Q.pop();
        for(int w=2; w<=Graph.Nv; w++)
            if(Graph.Weight[v][w] && !checked[w])
            {
                Q.push(w);
                checked[w] = 1;
            }
    }

    for(int w=1; w<=Graph.Nv; w++)
        if(checked[w] == 0)  res = false;

    return res;
}

void Floyd(AniTran Graph)
{
    vector <vector <int>> dist(102, vector<int>(102, 0));
    int res[102] = {0}, resMin = 102;

    for(int i=1; i<=Graph.Nv; i++)
        for(int j=1; j<=Graph.Nv; j++)
            if(i!=j)
                if(Graph.Weight[i][j])  dist[i][j] = Graph.Weight[i][j];
                else dist[i][j] = 102;
    
    for(int k=1; k<=Graph.Nv; k++)
        for(int i=1; i<=Graph.Nv; i++)
            for(int j=1; j<=Graph.Nv; j++)
                    if(dist[i][k] + dist[k][j] < dist[i][j])  dist[i][j] = dist[i][k] + dist[k][j];

    for(int i=1; i<=Graph.Nv; i++)
    {
        for(int j=1; j<=Graph.Nv; j++)
            res[i] = max(res[i], dist[i][j]);
        resMin = min(resMin, res[i]);
    }
    
    for(int i=1; i<=Graph.Nv; i++)
        if(resMin == res[i])
        { 
            cout << i << ' ' << res[i];
            break;
        }
}

int main()
{
    AniTran AniGraph;
    cin >> AniGraph.Nv >> AniGraph.Ne;
    for(int i=1; i<=AniGraph.Ne; i++)
    {
        int v, w, weight;
        cin >> v >> w >> weight;
        AniGraph.Weight[v][w] = weight;
        AniGraph.Weight[w][v] = weight;
    }
    if(BFS_LT(AniGraph))  Floyd(AniGraph);
    else cout << BFS_LT(AniGraph);

    return 0;
}




10. 邻接矩阵 - 最小生成树 - Prim算法

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 邻接矩阵 - 最小生成树 - Prim算法

#define Maxdist 10000000
#define MaxVertexNum 100        // 最大顶点数
typedef int WeightType;         // 权值
typedef int Vertex;             // 顶点
typedef int DataType;           // 数据

vector <int> dist(MaxVertexNum, Maxdist);   // 存储距离, 并初始化为 Maxdist
vector <Vertex> parent(MaxVertexNum, -1);      // 储存父节点, 并初始化为 -1
vector <Vertex> MST;                           // 最小生成树

// 边
typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;              // < V1, V2 > 有向边
    WeightType Weight;          // 权重
};
typedef PtrToENode Edge;

// 图
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;                     // 顶点数
    int Ne;                     // 边数
    WeightType G[MaxVertexNum][MaxVertexNum];   // 邻接矩阵
    DataType Data[MaxVertexNum];                // 数据
};
typedef PtrToGNode MGraph;

// 操作集
void initPrim(Vertex s);                         // 初始化 Prim
int FindMinVertex(MGraph Graph, Vertex v);      // 找出dist最小值
void Prim(MGraph Graph, Vertex s);               // Prim算法

void initPrim(MGraph Graph, Vertex s)
{
    MST.push_back(s), dist[s] = 0;
    for(Vertex w=0; w<Graph->Nv; w++)
        if(Graph->G[s][w])  dist[w] = Graph->G[s][w], parent[w] = s;
}

int FindMinVertex(MGraph Graph, Vertex v)
{
    Vertex vMin = -1;
    int minV = Maxdist;
    for(Vertex w=0; w<Graph->Nv; w++)
        if(dist[w] && dist[w] < minV)  minV = dist[w], vMin = w;
    return vMin;
}

void Prim(MGraph Graph, Vertex s)
{
    initPrim(Graph, s);
    Vertex v;
    int cnt=1;
    while(1)
    {
        v = FindMinVertex(Graph, v);
        if(v==-1)  break;
        MST.push_back(v), dist[v] = 0, cnt++;

        for(Vertex w=0; w<Graph->Nv; w++)
            if(dist[w] && Graph->G[v][w])
                if(Graph->G[v][w] < dist[w])  dist[w] = Graph->G[v][w], parent[w] = v;

        if(cnt < Graph->Nv)  cout << "Bu Lian Tong !" << endl;
    }
}




11. 邻接矩阵 - 最小生成树 - Kruskal算法

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
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
// 邻接矩阵 - 最小生成树 - Kruskal算法

#define Maxdist 10000000
#define MaxVertexNum 100        // 最大顶点数
typedef int WeightType;         // 权值
typedef int Vertex;             // 顶点
typedef int DataType;           // 数据

vector <int> dist(MaxVertexNum, Maxdist);   // 存储距离, 并初始化为 Maxdist
vector <int> parent(MaxVertexNum, -1);      // 储存父节点, 并初始化为 -1


// 边
typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;              // < V1, V2 > 有向边
    WeightType Weight;          // 权重
    bool operator< (const ENode &b) const       // 重载运算符
    {
        return this->Weight>b.Weight;
    }
};
typedef PtrToENode Edge;
priority_queue <Edge> MinHeap;     // 最小堆 <优先队列> 需存入边集合
vector <Edge> MST;                 // 最小生成树

// 图
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;                     // 顶点数
    int Ne;                     // 边数
    WeightType G[MaxVertexNum][MaxVertexNum];   // 邻接矩阵
    DataType Data[MaxVertexNum];                // 数据
};
typedef PtrToGNode MGraph;

// 操作集
int Kruskal(MGraph Graph);
void Union(Vertex v, Vertex w);
bool Union_HL(MGraph Graph, Edge E);        // 判断回路

bool Union_HL(MGraph Graph, Edge E)
{
    Vertex v = E->V1, w = E->V2;
    for(; parent[v]>=0; v=parent[v]);
    for(; parent[w]>=0; w=parent[w]);
    
    if(v==w) return true;
    else
    {
        Union(v, w);
        return false;
    }
}

void Union(Vertex v, Vertex w)
{
    if(parent[v]<parent[w])  
        parent[v]+=parent[w], parent[w]=v;
    else  
        parent[w]+=parent[v], parent[v]=w;
}

int Kruskal(MGraph Graph)
{
    WeightType weight = 0;
    while(MST.size()<(Graph->Nv-1) && !MinHeap.empty())
    {
        Edge E = MinHeap.top();
        MinHeap.pop();
        if(!Union_HL(Graph, E))  weight+=E->Weight, MST.push_back(E);
    }
    if(MST.size()<(Graph->Nv-1))  cout << "Bu Lian Tong !!!" << endl;
    return weight;
}




12. 邻接表 - 拓扑排序

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
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
// 邻接表 - 拓扑排序

#define MaxVertexNum 100        // 最大顶点数
typedef int Vertex;             // 顶点
typedef int WeightType;         // 边的权值
typedef int DataType;           // 数据

vector <Vertex> TopOrder(MaxVertexNum);          // 拓扑排序后的下标顺序

// 边
typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;          // 有向边 <V1, V2>
    WeightType Weight;      // 权重
};
typedef PtrToENode Edge;

// 邻接点
typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
    Vertex ADjV;            // 邻接点下标
    WeightType Weight;      // 边权重
    PtrToAdjVNode Next;     // 指针
};

// 顶点表头结点
typedef struct VNode{
    PtrToAdjVNode FirstEdge;    // 边表头结点
    DataType Data;              // 数据
}AdjList[MaxVertexNum];         // 邻接表类型

// 图
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;                     // 顶点数
    int Ne;                     // 边数
    AdjList G;                  // 邻接表
};
typedef PtrToGNode LGraph;      // 邻接表-图类型

// 操作集
bool TopSort(LGraph Graph, Vertex *TopOrder);   // 拓扑排序

bool TopSort(LGraph Graph, Vertex *TopOrder)
{
    queue <Vertex> zeroDegree;  // 0 度 队列
    int Indegree[MaxVertexNum], cnt = 0;
    
    for(Vertex V=0; V<Graph->Nv; V++)  Indegree[V] = 0;
    for(Vertex V=0; V<Graph->Nv; V++)
        for(PtrToAdjVNode W=Graph->G[V].FirstEdge; W; W=W->Next)
            Indegree[W->ADjV]++;
    
    for(Vertex V=0; V<Graph->Ne; V++)
        if(!Indegree[V])  zeroDegree.push(V);
    
    while(!zeroDegree.empty())
    {
        Vertex V = zeroDegree.front();
        TopOrder[cnt++] = V;
        zeroDegree.pop();
        for(PtrToAdjVNode W=Graph->G[V].FirstEdge; W; W->Next)
            if(--Indegree[W->ADjV] == 0)  zeroDegree.push(W->ADjV);
    }

    if(cnt < Graph->Nv)  return false;      // 存在回路
    else  return true;                      // 排序成功
}