C语言数据结构 图 深度优先遍历创建森林 最小树生成 拓扑排序 关键路径_c 树拓扑数据结构

配置

IDE：Visual Studio 2019
声明：为了方便书写代码，用到了C++的引用调用特性和iostream作为输入输出，读者可以使用指针调用和scanf_s/print语句实现相同效果
tips：有疑问可以在下面交流，我会尽量回复的

代码

头文件heads.h

#pragma once
#include "stdio.h"
#include "iostream"
#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OVERFLOW -1
using namespace std;
typedef short int Status;
1
2
3
4
5
6
7
8
9
10

栈的头文件Stack.h

#pragma once
#include "heads.h"
#define STACK_INIT_SIZE 1000
#define STACKINCREMENT 200
typedef int ElemType;
typedef struct Stack {//基础栈结构
	ElemType* base;
	ElemType* top;
	int stacksize;
}SqStack;
Status InitStack(SqStack& S);
//返回栈顶元素
Status GetTOP(SqStack S, ElemType& e);
//入栈
Status Push(SqStack& S, ElemType e);
//出栈
Status Pop(SqStack& S, ElemType& e);
//判断栈是否为空
Status StackEmpty(SqStack S);
//清空栈
Status Clear(SqStack& S);
//遍历函数
Status visit(ElemType e);
Status StackTraverse(SqStack S, Status(*visit)(ElemType));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

图的头文件Graph.h

#include "heads.h"
#include "Treefunctions.h"
#include "Stack.h";
typedef int VRType;//顶点关系类型
typedef int InfoType;//弧相关信息
typedef int VertexType;//顶点信息
enum GraphKind{ DG, DN, UDG, UDN };
//数组表示法
#define INFINITY INT_MAX;
#define MAX_VERTEX_NUM 20
typedef struct ArcCell {
	VRType adj;
	InfoType* info;
}AreCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
	VertexType vexs[MAX_VERTEX_NUM];
	AdjMatrix arcs;
	int vexnum, arcnum;//图当前顶点数和弧数
	enum GraphKind Kind;
}MGraph;
//MGraph
//结点在图中的定位
int LocateMVex(MGraph G, VertexType e);
//创造邻接矩阵
Status CreateMGraph(MGraph& G);
//邻接表
typedef struct ArcNode {
	int adjvex;
	struct ArcNode* nextarc;
	InfoType* info;
}ArcNode,*Arc;
typedef struct VNode {
	VertexType data;
	ArcNode* firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct {
	AdjList vertices;
	int vexnum, arcnum;
	enum GraphKind Kind;
}AlGraph;
//结点在图中的定位
int LocateVex(AlGraph G, VertexType e);
//创建邻接表
Status CreateAlGraph(AlGraph& G);
//删除邻接表
Status DestoryAlGraph(AlGraph& G);
//顶点赋值 
Status PutVex(AlGraph& G, int i, VertexType e);
//返回第一个邻接点
int FirstAdjVex(AlGraph G, int v);
//返回下一个邻接点
int NextAdjVex(AlGraph G, int v, int w);
//增加结点
Status InsertVex(AlGraph& G, VertexType e);
//删除结点和依附的弧
Status DeleteVex(AlGraph& G, VertexType e);
//插入弧
Status InsertArc(AlGraph& G, int v, int w, InfoType e);
//删除弧
Status DeleteArc(AlGraph& G, int v, int w);
//深度优先遍历
Status visit(AlGraph G, int v);
void DFS(AlGraph G, int v);
void DFSTraverse(AlGraph G, Status(*visit)(AlGraph G, int v));
//创建森林
void DFSForest(AlGraph G, CSTree& T);
//最小生成树
void MiniSpanTree_Prim(MGraph G, VertexType u);
//拓扑排序
Status TopologicalSort(AlGraph G);
//关键路径
Status Mainpath(AlGraph G);
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

邻接表实现代码AlGraph.cpp

#include "Graph.h"
bool visited[MAX_VERTEX_NUM];
Status(*VisitFunc)(AlGraph G, int v);
//弧的初始化
Status InitArc(AlGraph &G,int a,int b,InfoType e) {
	Arc q=G.vertices[a].firstarc;
	Arc p = (Arc)malloc(sizeof(ArcNode));
	p->info = (InfoType*)malloc(sizeof(InfoType));
	if (!p)return ERROR;
	p->nextarc = NULL;
	*(p->info) = e;
	p->adjvex = b;
	if (q == NULL) {
		G.vertices[a].firstarc = p;
	}
	else {
		while (q->nextarc)q = q->nextarc;
		q->nextarc = p;
	}
	return OK;
}//InitArc
//结点在图中的定位
int LocateVex(AlGraph G, VertexType e) {
	int i = 0;
	for (; i < G.vexnum; i++) {
		if (e == G.vertices[i].data)break;
	}
	return i;
}//LocateVex
//创建有向网
Status CreateDNAlGraph(AlGraph& G) {
	cout << "有向网图开始初始化..." << endl;
	VertexType v1, v2;
	VRType w;
	int i, j;
	cout << "依次输入顶点数，弧数" << endl;
	cin >> G.vexnum >> G.arcnum;
	for (i = 0; i < G.vexnum; ++i) {
		cout << "输入第" << i + 1 << "个顶点的元素" << endl;
		cin >> G.vertices[i].data;
		G.vertices[i].firstarc = NULL;
	}
	for (int k = 0; k < G.arcnum; k++) {
		cout << "依次输入第" << k + 1 << "条弧依附的两个顶点的元素以及弧的权值" << endl;
		cin >> v1 >> v2 >> w;
		i = LocateVex(G, v1); j = LocateVex(G, v2);
		InitArc(G, i, j, w);
	}
	return OK;
}//CreateDNAlGraph
//创建邻接表
Status CreateAlGraph(AlGraph& G) {
	cout << "请输入邻接表的样式" << endl;
	scanf_s("%u", &G.Kind);
	switch (G.Kind)
	{
	case DN:return CreateDNAlGraph(G);
	case UDN:break;
	default:return ERROR;
	}
}//CreateAlGraph
//删除邻接表
Status DestoryAlGraph(AlGraph& G) {
	for (int i = 0; i < G.vexnum; ++i) {
		Arc p = G.vertices[i].firstarc, q = p->nextarc;
		if (p == NULL)continue;
		while (p) {
			free(p->info);
			free(p);
			p = q;
			if(q->nextarc)q = q->nextarc;
		}
	}
	free(&G);
	return OK;
}//DeatoryAlGraph
//顶点赋值 
Status PutVex(AlGraph& G, int i, VertexType e) {
	G.vertices[i].data = e;
	return OK;
}//PutVex
//返回第一个邻接点
int FirstAdjVex(AlGraph G, int v) {
	if (G.vertices[v].firstarc)return G.vertices[v].firstarc->adjvex;
	return -1;
}//FirstAdjVex
//返回下一个邻接点
int NextAdjVex(AlGraph G, int v, int w) {
	Arc p = G.vertices[v].firstarc;
	while (p) {
		if (p->adjvex == w)break;
		p = p->nextarc;
	}
	if (p == NULL || p->nextarc == NULL)return -1;
	return p->nextarc->adjvex;
}//NextAdjVex
//增加结点
Status InsertVex(AlGraph& G, VertexType e) {
	G.vertices[G.vexnum].data = e;
	G.vertices[G.vexnum].firstarc = NULL;
	G.vexnum++;
	return OK;
}//InsertVex
//删除结点和依附的弧
Status DeleteVex(AlGraph& G, VertexType e) {
	int i = LocateVex(G, e), j = 0;
	Arc p = G.vertices[i].firstarc, q = p;
	G.vertices[i].firstarc = NULL;
	while (p) {
		q = p->nextarc;
		free(p->info);
		free(p);
		p = q;
		j++;
	}
	for (int z = i; z < G.vexnum; z++) {
		G.vertices[z].data = G.vertices[z + 1].data;
		G.vertices[z].firstarc = G.vertices[z + 1].firstarc;
	}
	G.vexnum--;
	for (int z = 0; z < G.vexnum; z++) {
		p=G.vertices[z].firstarc;
		if (p) {
			if (p->adjvex == i) {
				G.vertices[z].firstarc = p->nextarc;
				free(p->info);
				free(p);
				j++;
				p = G.vertices[z].firstarc;
			}
			while (p) {
				if (p->adjvex == i) {
					q->nextarc = p->nextarc;
					free(p->info);
					free(p);
					j++;
					p = q->nextarc;
					continue;
				}
				if (p->adjvex > i) {
					p->adjvex--;
				}
				q = p;
				p = p->nextarc;
			}
		}
	}
	G.arcnum -= j;
	return OK;
}//DeleteVex
//插入弧
Status InsertArc(AlGraph& G, int v, int w,InfoType e){
	InitArc(G, v, w, e);
	++G.arcnum;
	return OK;
}//InsertArc
//删除弧
Status DeleteArc(AlGraph& G, int v, int w) {
	int a, b;
	a = LocateVex(G, v);
	b = LocateVex(G, w);
	Arc p = G.vertices[a].firstarc, q = p;
	if (G.vertices[a].firstarc->adjvex == b) {
		G.vertices[a].firstarc = p->nextarc;
		free(p->info);
		free(p);
		G.arcnum--;
		return OK;
	}
	else {
		while (p) {
			if (p->adjvex == b) {
				q->nextarc = p->nextarc;
				free(p->info);
				free(p);
				G.arcnum--;
				return OK;
			}
			q = p;
			p = p->nextarc;
		}
	}
	return ERROR;
}//DeleteArc
//深度优先遍历
Status visit(AlGraph G, int v) {
	cout<<G.vertices[v].data<<" ";
	return OK;
}
void DFS(AlGraph G, int v) {
	visited[v] = TRUE; VisitFunc(G, v);
	for (int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
		if (!visited[w])DFS(G, w);
	}
}
void DFSTraverse(AlGraph G, Status(*visit)(AlGraph G, int v)) {
	VisitFunc = visit;
	for (int v = 0; v < G.vexnum; ++v)visited[v] = FALSE;
	for (int v = 0; v < G.vexnum; v++) {
		if (!visited[v])DFS(G, v);
	}
	cout << endl;
}//DFSTraverse
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203

最小树生成和深度优先遍历森林DFS.cpp

#include "Graph.h"
#include "Treefunctions.h"
bool visite[MAX_VERTEX_NUM];
//深度优先遍历创建森林
void DFSTree(AlGraph G, int v, CSTree& T) {
	visite[v] = TRUE;
	bool first = TRUE;
	CSTree p, q=NULL;
	for (int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
		if (!visite[w]) {
			p = (CSTree)malloc(sizeof(CSNode));
			*p = { G.vertices[w].data,NULL,NULL };
			if (first) {
				T->firstchild = p;
				first = FALSE;
			}
			else {
				q->nextsibling = p;
			}
			q = p;
			DFSTree(G, w, q);
		}
	}
}
void DFSForest(AlGraph G, CSTree& T) {
	T = NULL;
	CSTree p, q=NULL;
	for (int v = 0; v < G.vexnum; ++v)
		visite[v] = FALSE;
	for (int v = 0; v < G.vexnum; ++v) {
		if (!visite[v]) {
			p = (CSTree)malloc(sizeof(CSNode));
			*p = { G.vertices[v].data,NULL,NULL };
			if (!T)T = p;
			else q->nextsibling = p;
			q = p;
			DFSTree(G, v, p);
		}
	}
}
//最小树生成
void MiniSpanTree_Prim(MGraph G, VertexType u) {
	struct {
		VertexType adjvex;
		VRType lowcost;
	}closedge[MAX_VERTEX_NUM];
	int k = LocateMVex(G, u);
	for (int j = 0; j < G.vexnum; ++j) {
		if (j != k)closedge[j] = { u,G.arcs[k][j].adj };
	}
	closedge[k].lowcost = 0;
	for (int i = 1; i < G.vexnum; ++i) {
		int num = -1;
		for (int a = 0; a < G.vexnum; ++a) {
			if (closedge[a].lowcost != 0) {
				if (num == -1)num = a;
				else if (closedge[a].lowcost < closedge[num].lowcost)num = a;
			}
		}
		k = num;
		cout << closedge[k].adjvex <<" "<< G.vexs[k] << endl;
		closedge[k].lowcost = 0;
		for (int j = 0; j < G.vexnum; ++j) {
			if (G.arcs[k][j].adj < closedge[j].lowcost)
				closedge[j] = { G.vexs[k],G.arcs[k][j].adj };
		}
	}
}
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

拓扑排序和关键路径打印DAG.cpp

#include "Graph.h"
//拓扑排序
void FindInDegree(AlGraph G, int *n) {
	Arc p;
	for (int i = 0; i < G.vexnum; ++i)n[i] = 0;
	for (int i = 0; i < G.vexnum; ++i) {
		p = G.vertices[i].firstarc;
		while (p) {
			n[p->adjvex]++;
			p = p->nextarc;
		}
	}
}
Status TopologicalSort(AlGraph G) {
	int indegree[MAX_VERTEX_NUM];
	Stack S;
	FindInDegree(G, indegree);
	InitStack(S);
	for (int i = 0; i < G.vexnum; ++i) {
		if (!indegree[i])Push(S, i);
	}
	int count = 0;
	while (!StackEmpty(S)) {
		int i;
		Pop(S, i);
		cout << i << ": " << G.vertices[i].data << endl;
		++count;
		for (Arc p = G.vertices[i].firstarc; p; p = p->nextarc) {
			int k = p->adjvex;
			if (!(--indegree[k]))Push(S, k);
		}
	}
	if (count < G.vexnum)return ERROR;
	return OK;
}
Status Mainpath(AlGraph G) {
	int le[MAX_VERTEX_NUM],re[MAX_VERTEX_NUM],indegree[MAX_VERTEX_NUM];
	Stack S, T;
	int sat=0;
	FindInDegree(G, indegree);
	InitStack(T);
	InitStack(S);
	int l = 0;
	for (int i = 0; i < G.vexnum; ++i) {
		if (!indegree[i]) {
			Push(S, i);
			l++;
		}
		if (l > 1) {
			cout << "错误:关键路径有两个起始点" << endl;
			return ERROR;
		}
	}
	for (int i = 0; i < G.vexnum; ++i) {
		le[i] = 0;
	}
	int count = 0;
	while (!StackEmpty(S)) {
		Pop(S, l);
		sat++;
		Push(T, l);
		count++;
		for (Arc p = G.vertices[l].firstarc; p; p = p->nextarc) {
			int k = p->adjvex;
			if (le[l] + *(p->info) > le[k]) { 
				le[k] = le[l] + *(p->info);
		}
			if (!(--indegree[k])) {
				Push(S, k);
				sat = 0;
			}
		}
	}
	if (count < G.vexnum) {
		cout << "错误:该图内有环" << endl;
		return ERROR;
	}
	if (sat > 1) {
		cout << "错误:关键路径有两个以上结束点" << endl;
		return ERROR;
	}
	for (int i = 0; i < G.vexnum; ++i) {
		re[i] = le[G.vexnum - 1];
	}
	while (!StackEmpty(T)) {
		Pop(T, l);
		Arc p = G.vertices[l].firstarc;
		if (!p)continue;
		int j = re[p->adjvex] - *(p->info);
		while (p->nextarc) {
			if (re[p->nextarc->adjvex]- *(p->nextarc->info) <j) {
				j = re[p->nextarc->adjvex] - *(p->nextarc->info);
			}
			p = p->nextarc;
		}
		re[l] = j;
	}
	for (int i = 0; i < G.vexnum; ++i) {
		if (le[i] == re[i])cout << G.vertices[i].data << " ";
	}
	return OK;
}
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

欢迎交流！！！