数据结构

Status CreateGraph( MGraph &G ) { // 算法7.1
// 采用数组(邻接矩阵)表示法，构造图G。
scanf(&G.kind); // 自定义输入函数，读入一个随机值
switch (G.kind) {
case DG: return CreateDG(G); // 构造有向图G
case DN: return CreateDN(G); // 构造有向网G
case UDG: return CreateUDG(G); // 构造无向图G
case UDN: return CreateUDN(G); // 构造无向网G，算法7.2
default : return ERROR;
}
} // CreateGraph


Status CreateUDN(MGraph &G) {// 算法 7.2
// 采用数组（邻接矩阵）表示法，构造无向网G。
int i,j,k,w;
VertexType v1,v2;
printf("G.vexnum :" ); scanf("%d",&G.vexnum);
printf("G.arcnum :"); scanf("%d",&G.arcnum);
getchar(); /*** 加上此句getchar()!!! ***/
// scanf("%d,%d,%d",&G.vexnum, &G.arcnum, &IncInfo);
for (i=0; iprintf("G.vexs[%d] : ",i);
scanf("%c",&G.vexs[i]);
getchar();
} // 构造顶点向量
for (i=0; ifor (j=0; jG.arcs[i][j].adj = INFINITY; //{adj,info}
G.arcs[i][j].info= NULL;
}
for (k=0; kprintf("v1 (char) : "); scanf("%c", &v1);getchar();
printf("v2 (char) : "); scanf("%c", &v2);getchar();
printf("w (int) : " ); scanf("%d", &w); getchar();
// 输入一条边依附的顶点及权值
i = LocateVex(G, v1); j = LocateVex(G, v2);
// 确定v1和v2在G中位置
G.arcs[i][j].adj = w; // 弧的权值
// if (IncInfo) scanf(G.arcs[i][j].info); // 输入弧含有相关信息
G.arcs[j][i].adj = G.arcs[i][j].adj; // 置的对称弧
}
return OK;
} // CreateUDN


Status CreateDG(OLGraph &G) { // 算法7.3
// 采用十字链表存储表示，构造有向图G（G.kind=DG）。
//scanf(&G.vexnum, &G.arcnum, &IncInfo);
int i,j,k;
char v1,v2;
int IncInfo=0;
struct ArcBox *p;
scanfInit(); // 输入初始化
scanf(&G.vexnum, &G.arcnum, &IncInfo); // 自定义输入函数
for (i=0; iscanf(&G.xlist[i].data); // 输入顶点值
G.xlist[i].firstin = G.xlist[i].firstout = NULL; // 初始化指针
}
for (k=0; kscanf(&v1, &v2); // 输入一条弧的始点和终点
i=LocateVex(G, v1); j=LocateVex(G, v2); // 确定v1和v2在G中位置

p=(ArcBox *) malloc (sizeof (ArcBox)); // 假定有足够空间
// *p = {i, j, G.xlist[j].firstin, G.xlist[i].firstout, NULL}
// {tailvex, headvex, hlink, tlink, info}
p->tailvex=i;
p->headvex=j;
p->hlink=G.xlist[j].firstin;
p->tlink=G.xlist[j].firstout;
G.xlist[j].firstin = G.xlist[i].firstout = p;
// 完成

在入弧和出弧链头的插入
//if (IncInfo) Input(*p->info); // 输入弧含有相关信息，此略!!!
}
return OK;
} // CreateDG



void DFSTraverse(Graph G, Status (*Visit)(int v)) { // 算法7.4
// 对图G作深度优先遍历。
int v;
VisitFunc = Visit; // 使用全局变量VisitFunc，使DFS不必设函数指针参数
for (v=0; vfor (v=0; vif (!visited[v]) DFS(G, v); // 对尚未访问的顶点调用DFS
}



//--- 算法7.4和7.5使用的全局变量 ---
bool visited[MAX_VERTEX_NUM]; // 访问标志数组
Status (* VisitFunc)(int v); // 函数变量

void DFS(Graph G, int v) { // 算法7.5
// 从第v个顶点出发递归地深度优先遍历图G。
int w;
visited[v] = true; VisitFunc(v); // 访问第v个顶点
for (w=FirstAdjVex(G, v); w!=-1; w=NextAdjVex(G, v, w))
if (!visited[w]) // 对v的尚未访问的邻接顶点w递归调用DFS
DFS(G, w);
}




void BFSTraverse(Graph G, Status (*Visit)(int v )) {// 算法7.6
// 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。
QElemType v,w;
queue Q;
QElemType u;
for (v=0; vInitQueue(Q); // 置空的辅助队列Q
for (v=0; vif (!visited[v]) { // v尚未访问
visited[v] = TRUE; Visit(v); // 访问v
EnQueue(Q, v); // v入队列
while (!QueueEmpty(Q)) {
DeQueue(Q, u); // 队头元素出队并置为u
for (w=FirstAdjVex(G, u); w>=0; w=NextAdjVex(G, u, w))
if (!visited[w]) { // u的尚未访问的邻接顶点w入队列Q
visited[w] = TRUE; Visit(w);
EnQueue(Q, w);
}//if
}//while
}//if
} // BFSTraverse




void DFSForest(Graph G, CSTree &T) { // 算法7.7
// 建立无向图G的深度优先生成森林的(最左)孩子(右)兄弟链表T
int v; int j=0;
CSTree p,q;
T = NULL;
for (v=0; vfor (v=0; vif (!visited[v]) { // 第v顶点为新的生成树的根结点
p= (CSTree)malloc(sizeof(CSNode)); // 分配根结点
p->data=GetVex(G,v); // 给该结点赋值
p->firstchild=NULL;
p->nextsibling=NULL;
if (!T) T = p; // 是第一棵生成树的根(T的根)
else q->nextsibling = p; // 其它生成树的根(前一棵的根的“兄弟”)
q = p; // q指示当前生成树的根
DFSTree(G, v,p); // 建立以p为根的生成树
}//if
} // DFSForest




void DFSTree(Graph G, int v, CSTree &T) { // 算法7.8
// 从第v个顶点出发深度优先遍历图G，建立以T为根的生成树
int w;
CSTree p,q;
bool first

=TRUE;
visited[v] = TRUE;
for (w=FirstAdjVex(G, v); w!=-1; w=NextAdjVex(G, v, w))
if (!visited[w]) {
p = (CSTree) malloc (sizeof (CSNode)); // 分配孩子结点
p->data = GetVex(G,w);
p->firstchild=NULL;
p->nextsibling=NULL;
if (first) { // w是v的第一个未被访问的邻接顶点
T->firstchild = p; first = FALSE; // 是根的左孩子结点
} else { // w是v的其它未被访问的邻接顶点
q->nextsibling = p; // 是上一邻接顶点的右兄弟结点
}
q = p;
DFSTree(G,w,q) ;
}//if
} // DFSTree




void MiniSpanTree_PRIM(MGraph G, VertexType u) { // 算法7.9
// 用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。
// 记录从顶点集U到V－U的代价最小的边的辅助数组定义：
// struct {
// VertexType adjvex;
// VRType lowcost;
// } closedge[MAX_VERTEX_NUM];
int i,j,k;
k = LocateVex ( G, u );
for ( j=0; jif (j!=k)
{ closedge[j].adjvex=u; closedge[j].lowcost=G.arcs[k][j].adj; }
}
closedge[k].lowcost = 0; // 初始，U＝{u}
for (i=1; ik = minimum(closedge); // 求出T的下一个结点：第k顶点
// 此时closedge[k].lowcost =
// MIN{ closedge[vi].lowcost | closedge[vi].lowcost>0, vi∈V-U }
printf(closedge[k].adjvex, G.vexs[k]); // 输出生成树的边
closedge[k].lowcost = 0; // 第k顶点并入U集
for (j=0; jif (G.arcs[k][j].adj < closedge[j].lowcost) {
// 新顶点并入U后重新选择最小边
// closedge[j] = { G.vexs[k], G.arcs[k][j].adj };
closedge[j].adjvex=G.vexs[k];
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
} // MiniSpanTree



void FindArticul(ALGraph G) { // 算法7.10
// 连通图G以邻接表作存储结构，查找并输出G上全部关节点。
// 全局量count对访问计数。
int v;
struct ArcNode *p;
visited[0] = 1; // 设定邻接表上0号顶点为生成树的根
for (int i=1; ip = G.vertices[0].firstarc;
if(p) {
v = p->adjvex;
DFSArticul(G, v); // 从第v顶点出发深度优先查找关节点。
if (count < G.vexnum) { // 生成树的根有至少两棵子树
printf (0, G.vertices[0].data); // 根是关节点，输出
while (p->nextarc) {
p = p->nextarc; v = p->adjvex;
if (visited[v]==0) DFSArticul(G, v);
}//while
}//if
}//if(p)
} // FindArticul



void DFSArticul(ALGraph G, int v0 ) { // 算法7.11
// 从第v0个顶点出发深度优先遍历图G，查找并输出关节点
int min,w;
struct ArcNode *p;
visited[v0] = min = ++count; // v0是第count个访

问的顶点
for (p=G.vertices[v0].firstarc; p!=NULL; p=p->nextarc) {
// 检查v0的每个邻接顶点
w = p->adjvex; // w为v0的邻接顶点
if (visited[w] == 0) { // w未曾被访问，是v0的孩子
DFSArticul(G, w); // 返回前求得low[w]
if (low[w] < min) min = low[w];
if (low[w] >= visited[v0])
printf(v0, G.vertices[v0].data); // 输出关节点
}
else if (visited[w] < min) min = visited[w];
// w已被访问，w是v0在生成树上的祖先
}//for
low[v0] = min;
} // DFSArticul




Status TopologicalSort(ALGraph G) { // 算法7.12
// 有向图G采用邻接表存储结构。
// 若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则ERROR。
SqStack S;
int count,k,i;
ArcNode *p;
char indegree[MAX_VERTEX_NUM];
FindInDegree(G, indegree); // 对各顶点求入度indegree[0..vernum-1]
InitStack(S);
for (i=0; iif (!indegree[i]) Push(S, i); // 入度为0者进栈
count = 0; // 对输出顶点计数
while (!StackEmpty(S)) {
Pop(S, i);
printf(i, G.vertices[i].data); ++count; // 输出i号顶点并计数
for (p=G.vertices[i].firstarc; p; p=p->nextarc) {
k = p->adjvex; // 对i号顶点的每个邻接点的入度减1
if (!(--indegree[k])) Push(S, k); // 若入度减为0，则入栈
}
}
if (countelse return OK;
} // TopologicalSort



Status TopologicalOrder(ALGraph G, Stack &T) { // 算法7.13
// 有向网G采用邻接表存储结构，求各顶点事件的最早发生时间ve(全局变量)。
// T为拓扑序列定点栈，S为零入度顶点栈。
// 若G无回路，则用栈T返回G的一个拓扑序列，且函数值为OK，否则为ERROR。
Stack S;int count=0,k;
char indegree[40];
ArcNode *p;
InitStack(S);
FindInDegree(G, indegree); // 对各顶点求入度indegree[0..vernum-1]
for (int j=0; jif (indegree[j]==0) Push(S, j); // 入度为0者进栈
InitStack(T);//建拓扑序列顶点栈T
count = 0;
for(int i=0; iwhile (!StackEmpty(S)) {
Pop(S, j); Push(T, j); ++count; // j号顶点入T栈并计数
for (p=G.vertices[j].firstarc; p; p=p->nextarc) {
k = p->adjvex; // 对j号顶点的每个邻接点的入度减1
if (--indegree[k] == 0) Push(S, k); // 若入度减为0，则入栈
if (ve[j]+p->info > ve[k]) ve[k] = ve[j]+p->info;
}//for *(p->info)=dut()
}//while
if (countelse return OK;
} // TopologicalOrder




Status CriticalPath(ALGraph G) { // 算法7.14
// G为有向网，输出G的各项关键活动。
Stack T;

int a,j,k,el,ee,dut;
char tag;
ArcNode *p;
if (!TopologicalOrder(G, T)) return ERROR;
for(a=0; avl[a] = ve[G.vexnum-1]; // 初始化顶点事件的最迟发生时间
while (!StackEmpty(T)) // 按拓扑逆序求各顶点的vl值
for (Pop(T, j), p=G.vertices[j].firstarc; p; p=p->nextarc) {
k=p->adjvex; dut=p->info; //dut
if (vl[k]-dut < vl[j]) vl[j] = vl[k]-dut;
}
for (j=0; jfor (p=G.vertices[j].firstarc; p; p=p->nextarc) {
k=p->adjvex;dut=p->info;
ee = ve[j]; el = vl[k]-dut;
tag = (ee==el) ? '*' : ' ';
printf(j, k, dut, ee, el, tag); // 输出关键活动
}
return OK;
} // CriticalPath




void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)
{ // 算法7.15
// 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]
// 及其带权长度D[v]。
// 若P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点。
// final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径。
int i=0,j, v,w,min;
bool final[MAX_VERTEX_NUM];
for (v=0; vfinal[v] = FALSE;
D[v] = G.arcs[v0][v].adj;
for (w=0; wif (D[v] < INFINITY) { P[v][v0] = TRUE; P[v][v] = TRUE; }
}
D[v0] = 0; final[v0] = TRUE; // 初始化，v0顶点属于S集
//--- 开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集 ---
for (i=1; imin = INFINITY; // 当前所知离v0顶点的最近距离
for (w=0; wif (!final[w]) // w顶点在V-S中
if (D[w]final[v] = TRUE; // 离v0顶点最近的v加入S集
for (w=0; wif (!final[w] && (min+G.arcs[v][w].adj// 修改D[w]和P[w], w∈V-S
D[w] = min + G.arcs[v][w].adj;
for(j=0;jP[w][w] = TRUE; // P[w] = P[v]+[w]
}//if
}//for
} // ShortestPath_DIJ



void ShortestPath_FLOYD(MGraph G, PathMatrix P[], DistancMatrix &D) {
// 算法7.16
// 用Floyd算法求有向网G中各对顶点v和w之间的最短路径P[v][w]及其
// 带权长度D[v][w]。若P[v][w][u]为TRUE，则u是从v到w当前求得最
// 短路径上的顶点。
int v,w,u,i;
for (v=0; vfor (w=0; wD[v][w] = G.arcs[v][w].adj;
for (u=0; uif (D[v][w] < INFINITY) { // 从v到w有直接路径
P[v][w][v

] = P[v][w][w] = TRUE;
}//if
}//for
for (u=0; ufor (v=0; vfor (w=0; wif (D[v][u]+D[u][w] < D[v][w]) { // 从v经u到w的一条路径更短
D[v][w] = D[v][u]+D[u][w];
for (i=0; iP[v][w][i] =(P[v][u][i] || P[u][w][i]);
}//if
} // ShortestPath_FLOYD