组件化项目自动打Tag算法分析
一、问题背景：
组件化开发项目的过程中，会产生很多子库嵌入到壳工程，子库之间依赖关系复杂度也越来越大，每一次发版改动的子库需要打Tag，子库打完Tag后，壳工程打打Tag，项目越来越大时，手动打Tag愈发繁琐，要做到脚本自动化完成打tag，必须先分析子库之间的依赖关系，确定打Tag的先后顺序。
二、抽象模型
壳工程为依赖关系的起点，子库之间也有复杂的依赖关系，使用图状结构再来表示最为合适，下图描述了一个组件化项目壳工程与子库，子库与子库之间的依赖关系。
图一：依赖关系图
【图一：依赖关系图】
三、依赖关系图的存储结构
1、 数组表示法（二维数组，一个表示顶点信息，一个表示依赖关系）
图二：图的邻接矩阵
注：例如存在A->B的依赖关系，则矩阵位置（2，1）为1，否则为0，纵向看是每个结点的被依赖关系，横向是依赖关系。
2、邻接表表示法
图三：邻接表 结点后的链表表示出度
图四：逆邻接表 结点后的链表表示入度
简单的具体实现：
typedef Node{ intput[], output[]}//定义结点，两个数组分别表示入度和出度
Set(Node,Node*......)//集合包含所有的结点
3、十字链表表示
图五：十字链表
四、依赖关系图的遍历
通过遍历图，找到出度为0的结点，出度为0即说明此仓库没有依赖项，是需要先打Tag的库。处理完后在图中标记此结点，这个结点关联的弧即全部失效，再从剩余的结点找到出度为0的点，依此类推，直到最后一个结点。
1、邻接矩阵的递归遍历以及非递归遍历：
核心代码：
邻接矩阵的创建（C语言实现）
typedef struct /*图的邻接矩阵*/
{
int vexnum, arcnum; //顶点数量，边数量
char vexs[N]; //顶点数组
int arcs[N][N]; ///邻接矩阵
} graph;
void createGraph(graph *g) /*建立一个有向图的邻接矩阵*/
{
int i = 0; int j = 0; char v; g->vexnum = 0; g->arcnum = 0;
printf("输入顶点序列(char字符表示，例如一共有顶点A，顶点B，顶点C，输入ABC#，)(以#结束)：\n");
while ((v = getchar()) != '#') {
g->vexs[i] = v; /*写入顶点信息*/
i++;
}
g->vexnum = i; /*顶点数目*/
initgraph();/*邻接矩阵初始化*/
printf("\n输入边的信息（例如:顶点AB的边，从A到B，输入AB回车）：\n");
char m; char n;
scanf("\n%c%c", &m, &n);
while (m != '#' && n != '#') {
int indexI = indexOfVex(m, g); int indexj = indexOfVex(n, g);
if (indexI != -1 && indexj != -1) {
g->arcs[indexI][indexj] = 1;
}
scanf("\n%c%c", &m, &n);
}
}
邻接矩阵的递归遍历，时间复杂度为O(n^2)，实现较为简单
从任意顶点开始，即从第几行开始遍历，遍历到第i列不为0，递归第i行。
void dfs(int i, graph *g) /*从第i个顶点出发深度优先搜索*/
{
int j;
visited[i] = 1;
for (j = 0; j < g->vexnum; j++)
{
if (visited[j] == 0 && g->arcs[i][j] == 1)
{
dfs(j, g);
}
}
printf("\n打tag：%c", g->vexs[i]);
}
邻接矩阵的非递归遍历
借助栈来实现，如从第0个顶点开始遍历，第0个顶点入栈
取栈顶元素，遍历此顶点的出度，找到一个，入栈，再取栈顶元素循环
栈的变化：
l A
l AB
l ABC
l AB //C结点没有出度（没有依赖项），出栈，出栈即打Tag时机
l ABE //B的第二个出度E结点入栈（第二个依赖）
l ABED // E的出度D入栈
l ABE // D没有出度，出栈
l ABF //B的第三个出度F入栈
l ABFG
l ABF
l AB
l A
l 栈空，结束循环
邻接矩阵打Tag示例代码：https://gitlab.com/360fengdai/tagorder.git
2、邻接表的递归遍历
邻接表的创建（C语言实现，数组代替邻接链接）：
数据结构：
typedef struct /*顶点*/
{
char info; //顶点
int visit;
int outCount; //出度数量
int inCount; //入度数量
char outdegree[N]; //出度数组
char indegree[N]; //入度数组
} vex;
typedef struct
{
int count;// 顶点数量
vex data[N];// 顶点数组
} graph;
邻接表递归遍历示例代码：https://gitlab.com/360fengdai/tagorder.git
3、十字链表的遍历
数据结构定义：
typedef struct EdgeNode //弧结点的定义
{
int tailvex; //弧尾结点的下标
int headvex; //弧头结点的下标
struct EdgeNode *headlink; //指向弧头相同的下一条弧的链域
struct EdgeNode *taillink; //指向弧尾相同的下一条弧的链域
EdgeType info; //弧中所含有的信息 可以是权值等
} EdgeNode;
typedef struct VertexNode //顶点结点的定义
{
int index; //下标值
VertexType data; //顶点内容
EdgeNode *firstout; //顶点的第一条出弧
EdgeNode *firstin; //顶点的第一条入弧
} VertexNode;
typedef struct OLGraph //十字链表存储结构的有向图定义
{
VertexNode vertices[MaxVex];
int vexnum; //顶点数
int arcnum; //边数
} OLGraph;
非递归深度优先遍历核心代码，实现稀疏矩阵遍历最优时间复杂度O(n+e):
网友评论