[图](12)题集_2
14、编写算法，由依次输入的顶点数目、弧的数组、各顶点的信息和各弧的信息建立有向图的邻接表：
/*
typedef enum { DG, DN, UDG, UDN }GraphKind;
#define MAX_VERTEX_NUM 20 //最大顶点数
typedef int InfoType;
typedef int VertexType;
typedef struct ArcNode {
int adjvex;//邻接顶点的序号
InfoType weight;//该弧所带信息
struct ArcNode* nextarc;//指针域
}ArcNode;
typedef struct VNnde {
VertexType data;//顶点序号
ArcNode* firstarc;//该顶点所指向的第一条出度边
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices;//邻接表
int vexnum, arcnum;//顶点数，弧数
GraphKind Kind;//图类型
}ALGraph;
*/
int LocateVex(ALGraph* G, int e) {
for (int i = 0; i < G->vexnum; i++)
if (G->vertices[i].data == e) return i;
return -1;
}
Status CreateDG(ALGraph* G) {
char tem;//过滤空格符
printf("Please Input Vexnum and Arcnum：");
scanf("%d,%d%c", &G->vexnum, &G->arcnum, &tem);
if (G->vexnum < 1 || G->arcnum < 1) return ERROR;
printf("Please Input VexSet：");//初始化顶点表
for (int i = 0; i < G->vexnum; i++)
scanf("%d%c", &G->vertices[i].data, &tem);
int vi, vj;
int InVex, OutVex;//入度顶点、出度顶点
ArcNode* p;
//创建邻接表
for (int i = 0; i < G->arcnum; i++) {
printf("Please InVex 、OutVex and Weight：");
scanf("%d,%d,%d%c", &vi, &vj, &tem);
OutVex = LocateVex(G, vi);
InVex = LocateVex(G, vj);
if (InVex == -1 || OutVex == -1) return ERROR;
p = (ArcNode*)malloc(sizeof(ArcNode));//创建结点
p->adjvex = InVex;
p->nextarc = G->vertices[OutVex].firstarc;
G->vertices[OutVex].firstarc = p;
}
return OK;
}15、试在邻接矩阵存储结构上实现图的基本操作：InsertVex(G,v)、InsertArc(G,v,w)、DeleteVex(G,v)和DeleteArc(G,v,w)
思路：先来复习下这几个操作是啥，由于题目未表明那种图，则用有向网实现下述操作
InsertVex(&G,v)
初始条件:图G存在,v和图中顶点有相同特征
操作结果:在图G中增添新顶点v
DeleteVex(&G,v)
初始条件:图G存在,v是G中某个结点
操作结果:删除G中顶点v及其相关的弧
InsertArc(&G,v,w)
初始条件:图G存在,v和w是G中两个顶点
操作结果:在G中增添弧<v,w>,若G是无向的,则还增添对称弧<w,v>
DeleteArc(&G,v,w)
初始条件:图G存在,v和w是G中两个顶点
操作结果:在G中删除弧<v,w>,若G是无向的,则还删除对称弧<w,v>根据上述写出来即可
/*
int LocateVex(MGraph* G, int e) {
for (int i = 0; i < G->vexnum; i++)
if (G->vexs[i] == e) return i;
return -1;
}
Status CreateDN(MGraph* G) {
char tem;
scanf("%d,%d%c", &G->vexnum, &G->arcnum, &tem);
for (int i = 0; i < G->vexnum; i++) {
scanf("%d%c", &G->vexs[i], &tem);
for (int j = 0; j < G->vexnum; j++) {
G->arcs[i][j].adj = 0;
}
}
int v1, v2;
int InVex, OutVex, weight;
printf("请输入边和权值：");
for (int k = 0; k < G->arcnum; k++) {
scanf("%d,%d,%d%c", &v1, &v2, &weight, &tem);
OutVex = LocateVex(G, v1);
InVex = LocateVex(G, v2);
if (OutVex == InVex || OutVex == -1 || InVex == -1)
return ERROR;
G->arcs[OutVex][InVex].adj = weight;
}
return OK;
}
*/
Status InsertVex(MGraph* G, int v) {//插入顶点
if (G->vexnum == MAX_VERTEX_NUM) return ERROR;
G->vexnum++;
G->vexs[G->vexnum - 1] = v;
for (int j = 0; j < G->vexnum; j++) {
G->arcs[j][G->vexnum - 1].adj = 0;
G->arcs[G->vexnum - 1][j].adj = 0;
}
return OK;
}
Status DeleteVex(MGraph* G, int v) {//删除顶点
int Vex = LocateVex(G, v);
if (Vex == -1) return ERROR;
int j = Vex + 1;
for (int v = Vex, v1 = j; v1 < G->vexnum; v1++, v++)//移动顶点集
G->vexs[v] = G->vexs[v1];
for (int i = 0; i < G->vexnum; i++) {
if (G->arcs[i][Vex].adj != 0 || G->arcs[Vex][i].adj != 0)//若发现边，则将其删除，同时边数自减
G->arcnum--;
G->arcs[i][Vex].adj = 0;//入度出度都要删
G->arcs[Vex][i].adj = 0;
}
for (int i = Vex; j < G->vexnum; i++, j++) {
for (int k = 0; k < G->vexnum; k++) {
//将矩阵移动，该顶点的行列均往前推一格
G->arcs[k][i] = G->arcs[k][j];
G->arcs[i][k] = G->arcs[j][k];
}
}
G->vexnum--;
return OK;
}
Status InsertArc(MGraph* G, int v, int w,int weight) {//插入弧
int InVex = LocateVex(G, v);
int OutVex = LocateVex(G, w);
if (InVex == -1 || OutVex == -1 || InVex == OutVex)
return ERROR;
G->arcs[InVex][OutVex].adj = weight;
G->arcnum++;
return OK;
}
Status DeleteArc(MGraph* G, int v, int w) {//删除弧
int InVex = LocateVex(G, v);
int OutVex = LocateVex(G, w);
if (InVex == -1 || OutVex == -1 || InVex == OutVex)
return ERROR;
G->arcs[InVex][OutVex].adj = 0;
G->arcnum--;
return OK;
}
/*
Status Print_MGraph(MGraph G) {
printf("\n");
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
printf("%d ", G.arcs[i][j].adj);
}
printf("\n");
}
return OK;
}
*/其中只有删除结点稍微难点，我们知道，在邻接矩阵存储结构中，以为其图的结构已经固定的，所以要不便于更改，图示如下：
16、试对邻接表存储结构重做15题
Status InsertVex(ALGraph* G, int v) {
if (G->vexnum >= MAX_VERTEX_NUM) return ERROR;
G->vexnum++;
G->vertices[G->vexnum - 1].data = v;
G->vertices[G->vexnum - 1].firstarc = NULL;
return OK;
}
Status DeleteVex(ALGraph* G, int v) {
int Vex = LocateVex(G, v);
if (Vex == -1) return ERROR;
ArcNode* pre = NULL;
ArcNode* p = G->vertices[Vex].firstarc;
while (p) {//删除以该顶点为弧尾的边
pre = p;
p = p->nextarc;
free(pre);
G->arcnum--;
pre = NULL;
}
for (int i = Vex, j = i + 1; j < G->vexnum; i++, j++)
G->vertices[i] = G->vertices[j];
G->vexnum--;
for (int j = 0; j < G->vexnum; j++) {//删除以该顶点为弧头的边
p = G->vertices[j].firstarc;
if (p && p->adjvex == Vex) {
G->vertices[j].firstarc = p->nextarc;
free(p);
G->arcnum--;
p = NULL;
}
else {
while (p) {
if (p->adjvex == Vex) {
pre->nextarc = p->nextarc;
free(p);
G->arcnum--;
p = NULL;
p = pre->nextarc;
}
else {
pre = p;
p = p->nextarc;
}
}
}
}
for (int i = 0; i < G->vexnum; i++) {//处理顶点序号
ArcNode* p = G->vertices[i].firstarc;
while (p) {
if (p->adjvex > Vex) p->adjvex--;
p = p->nextarc;
}
}
return OK;
}
Status InsertArc(ALGraph* G, int v, int w,int weight) {
int OutVex = LocateVex(G, v);
int InVex = LocateVex(G, w);
if (OutVex == -1 || InVex == -1 || OutVex == InVex)
return ERROR;
ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = w;
p->weight = weight;
p->nextarc = G->vertices[OutVex].firstarc;
G->vertices[OutVex].firstarc = p;
G->arcnum++;
return OK;
}
Status DeleteArc(ALGraph* G, int v, int w) {
int OutVex = LocateVex(G, v);
int InVex = LocateVex(G, w);
if (OutVex == -1 || InVex == -1 || OutVex == InVex)
return ERROR;
ArcNode* pre, * p;
p = G->vertices[OutVex].firstarc;
if (p->adjvex == w) {
G->vertices[OutVex].firstarc = p->nextarc;
free(p);
p = NULL;
}
else {
while (p) {
if (p->adjvex == w) {
pre->nextarc = p->nextarc;
free(p);
p = NULL;
break;
}
pre = p;
p = p->nextarc;
}
}
G->arcnum--;
return OK;
}同样还是删除顶点复杂一点，它不仅需要删除以该顶点为出度的弧，还需要删除以该顶点为入度的弧，需要移动顶点表和遍历整个邻接表来完成。
17、试对十字链表存储结构重做15题
思路：难点还是在删除哪儿，因为我们需要调整所有结点的入度域以及出度域，又因通过一个顶点即可访问到其出度和入度，则我们需先断开所有顶点与该顶点的邻接再通过该结点去释放与其关联的所有出度边与入度边
/*
typedef struct ArcBox {
int tailvex, headvex;
struct ArcBox* hlink, * tlink;
InfoType info;
}ArcBox;
typedef struct VexNode {
VertexType data;
ArcBox* firstin, * firstout;
}VexNode;
typedef struct {
VexNode xlist[MAX_VERTEX_NUM];
int vexnum, arcnum;
}OLGraph;
*/
Status InsertVex(OLGraph* G, int v) {
G->vexnum++;
if (G->vexnum > MAX_VERTEX_NUM) return ERROR;
G->xlist[G->vexnum - 1].data = v;
G->xlist[G->vexnum].firstin = G->xlist[G->vexnum].firstout = NULL;
return OK;
}
Status DeleteVex(OLGraph* G, int v) {
int Vex = LocateVex(G, v);
if (Vex == -1) return ERROR;
ArcBox* In = NULL, * Out = NULL , * pre = NULL;
for (int i = 0; i < G->vexnum; i++) {//断开所有结点与其的出度弧，保持原有连通性
Out = G->xlist[i].firstout;
pre = NULL;
if (Out&&Out->headvex == Vex) {
G->xlist[i].firstout = Out->tlink;
G->arcnum--;
}
else {
while (Out) {
if (Out->headvex == Vex) {
pre->tlink = Out->tlink;
G->arcnum--;
Out = pre->tlink;
}
else {
pre = Out;
Out = Out->tlink;
}
}
}
}
for (int i = 0; i < G->vexnum; i++) {//断开所有结点与其的入度弧，保持原有连通性
In = G->xlist[i].firstin;
pre = NULL;
if (In && In->tailvex == Vex) {
G->xlist[i].firstin = In->hlink;
G->arcnum--;
}
else {
while (In) {
if (In->tailvex == Vex) {
pre->hlink = In->hlink;
In = pre->hlink;
G->arcnum--;
}
else {
pre = In;
In = pre->hlink;
}
}
}
}
//释放所有结点
Out = G->xlist[Vex].firstout;
In = G->xlist[Vex].firstin;
while (Out) {
pre = Out;
Out = Out->tlink;
free(pre); pre = NULL;
}
while (In) {
pre = In;
In = In->hlink;
free(pre); pre = NULL;
}
//调整顶点集
for (int i = Vex, j = i + 1; j < G->vexnum; i++, j++)
G->xlist[i] = G->xlist[j];
G->vexnum--;
return OK;
}
Status InsertArc(OLGraph* G, int v, int w,int weight) {
int OutVex = LocateVex(G, v);
int InVex = LocateVex(G, v);
if (OutVex == -1||InVex==-1||OutVex==InVex)
return ERROR;
ArcBox* p = (ArcBox*)malloc(sizeof(ArcBox));
p->hlink = p->tlink = NULL;
p->tailvex = OutVex;
p->headvex = InVex;
p->hlink = G->xlist[InVex].firstin;
p->tlink = G->xlist[OutVex].firstout;
G->xlist[InVex].firstin = G->xlist[OutVex].firstout = p;
G->arcnum++;
return OK;
}
Status DeleteArc(OLGraph* G, int v, int w) {
int OutVex = LocateVex(G, v);
int InVex = LocateVex(G, w);
if (OutVex == -1 || InVex == -1 || OutVex == InVex)
return ERROR;
ArcBox* pre = NULL, * p = NULL;
p = G->xlist[OutVex].firstout;//改变以该边为出度顶点的出度域，因后还需要调整入度域，则该步不进行删除
if (p->headvex == InVex && p->tailvex == OutVex)
G->xlist[OutVex].firstout = p->tlink;
else {
while (p) {
if (p->headvex == InVex && p->tailvex == OutVex) {
pre->tlink = p->tlink;
p = pre->tlink;
}
else {
pre = p;
p = p->tlink;
}
}
}
p = G->xlist[InVex].firstin;
if (p->headvex == InVex && p->tailvex == OutVex)//改变以该结点为入度顶点的入度域，同时释放该弧所代表的结点
G->xlist[InVex].firstin = p->hlink;
else {
while (p) {
if (p->headvex == InVex && p->tailvex == OutVex) {
pre->hlink = p->hlink;
free(p); p = NULL;
p = pre->hlink;
}
else {
pre = p;
p = p->hlink;
}
}
}
G->arcnum--;
return OK;
}
Status Print_MGraph(OLGraph G) {
printf("\n");
for (int i = 0; i < G.vexnum; i++) {
printf("V(%d)：", G.xlist[i].data);
ArcBox* p = G.xlist[i].firstout;
//p=G.xlist[i].firstin
while (p) {
printf("(%d,%d,%d)-->", p->tailvex, p->headvex, p->info);
p = p->tlink;
//p=p->hlink
}
printf("\n");
}
return OK;
}
18、试对邻接多重表结构重做15题
思路：18和19题算法均采用下图作为测试样例，其插入顶点，删除顶点，插入边，删除边和打印算法均测试成功，篇幅太长所以采用下载如下所示：
19、试编写算法，由依次输入的顶点数目，边的数目、各顶点的信息和各边的信息建立无向图的邻接多重表
思路：邻接多重表麻烦的是需要判断顶点是属于其挂载边的 i 端点还是 j 端点，来确定新建边集是在插入其ilink域还是jlink域，算法如下所示，对应逻辑图很容易就能理解算法：
/*
typedef enum{unvisited,Visited}VisitIf;//变量名转换
typedef struct EBox {
VisitIf mark;//变量mark只能取unvisited和visited;未访问和已访问
int ivex, jvex;//该边依附的两个顶点为止
struct EBox* ilink, * jlink;//分别指向依附这两个顶点的下一条边
int weight;//权值
}EBox;
typedef struct VexBox {
int data;
EBox* firstedge;//指向第一条依附该顶点的边
}VexBox;
typedef struct {
VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum, edgenum;//无向图的当前顶点数和边数
}AMLGraph;
int LocateVex(AMLGraph* G, int e) {
for (int i = 0; i < G->vexnum; i++)
if (G->adjmulist[i].data == e) return i;
return -1;
}
*/
Status CreateUDN(AMLGraph* G) {
char tem;
scanf("%d,%d%c", &G->vexnum, &G->edgenum, &tem);
for (int i = 0; i < G->vexnum; i++) {
scanf("%d%c", &G->adjmulist[i].data, &tem);
G->adjmulist[i].firstedge = NULL;
}
EBox* p1, * p2, * a;
int v1, v2, i ,j ,weight;
for (int k = 0; k < G->edgenum; k++) {
scanf("%d,%d,%d%c", &v1, &v2, &weight, &tem);
i = LocateVex(G, v1);
j = LocateVex(G, v2);
if (i == -1 || j == -1 || i == j)
return ERROR;
//创建结点
p1 = (EBox*)malloc(sizeof(EBox));
p1->ilink = p1->jlink = NULL;
p1->ivex = i;
p1->jvex = j;
p1->weight = weight;
if (G->adjmulist[i].firstedge == NULL) {//若为空，则直接插入
p1->ilink = G->adjmulist[i].firstedge;
G->adjmulist[i].firstedge = p1;
}
else {//否则则判断其与i相同还是与j相同，头插法插入
p2 = G->adjmulist[i].firstedge;
if (p2->ivex == i) {
p1->ilink = p2->ilink;
p2->ilink = p1;
}
else {
p1->ilink = p2->jlink;
p2->jlink = p1;
}
}
//处理入度边
if (G->adjmulist[j].firstedge == NULL) {
p1->jlink = G->adjmulist[j].firstedge;
G->adjmulist[j].firstedge = p1;
}
else {
p2 = G->adjmulist[j].firstedge;
if (p2->jvex == j) {
p1->jlink = p2->jlink;
p2->jlink = p1;
}
else {
p1->jlink = p2->ilink;
p2->ilink = p1;
}
}
}
return OK;
}20、下面的算法段可以测定图G=(V,E)是否可传递：
trans=TRUE
for(V中每个x)
for(N(x)中每个y)
for(N(y)中不等于x的每个z)
if(z不在N(x)中) trans=FALSE；其中N(x)表示x邻接到的所有顶点的集合。试以邻接矩阵存储结构实现判断一个图的可传递性算法，并通过n=|V|，m=|E|和d=结点度数的均值，估计执行时间。
思路：解释下图的传递性
就是途中任意相邻接的两个顶点，他们的邻接顶点集合只有对方这一点不同，其他的顶点都是相同的。
才能称为可传递
BOOL Trans(MGraph* G) {
BOOL trans = TRUE;
for (int x = 0; x < G->vexnum; x++) {//V中每个x
for (int y = 0; y < G->vexnum; y++) {//N(x)中的每个y
if (!G->arcs[x][y].adj) continue;//y不是x的邻接点
for (int z = 0; z < G->vexnum; z++) {//N(y)中的每个z
if (!G->arcs[y][z].adj||z==x) continue;//z不是y的邻接点
if (!G->arcs[x][z].adj) {//z不在N(x)中
trans = FALSE;
return trans;
}
}
}
}
return trans;
}21、试对邻接表存储结构重做20题
思路与上述一样，代码如下所示：
BOOL Trans(ALGraph* G) {
BOOL trans = TRUE;
ArcNode* p, * p1, * p2;
for (int x = 0; x < G->vexnum; x++) {//V中的每个x
p = G->vertices[x].firstarc;
while (p) {
int y = p->adjvex;
p1 = G->vertices[y].firstarc;
while (p1) {
int z = p1->adjvex;
if (z == x) continue;
p2 = G->vertices[x].firstarc;
while (p2) {
if (p2->adjvex == z) break;
p2 = p2->nextarc;
}
if (!p2) {
trans = FALSE;
return trans;
}
p1 = p1->nextarc;
}
p = p->nextarc;
}
}
return trans;
}22、试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径( i ≠ j )。注意：算法中涉及的图的基本操作必须在此存储结构上实现
BOOL DFSing(ALGraph* G, int Start, int End, int* visited) {
if (Start == End) return TRUE;
if (visited[Start]) return FALSE;
visited[Start] = 1;
ArcNode* p = G->vertices[Start].firstarc;
while (p) {
if (DFSing(G, p->adjvex, End, visited)) {
printf("<--V(%d)", G->vertices[p->adjvex].data);
return TRUE;
}
p = p->nextarc;
}
return FALSE;
}
BOOL DFS(ALGraph* G, int i, int j) {
int Start = LocateVex(G, i);
int End = LocateVex(G, j);
if (Start == -1 || End == -1 || Start == End) return FALSE;
int* Visited = (int*)malloc(sizeof(int) * G->vexnum);
memset(Visited, 0, sizeof(Visited));
Visited[Start] = 1;
ArcNode* p = G->vertices[Start].firstarc;
while (p) {
if (DFSing(G, p->adjvex, End, Visited)) {
printf("<--V(%d)", G->vertices[p->adjvex].data);
printf("<--V(%d)", G->vertices[Start].data);
return TRUE;
}
p = p->nextarc;
}
return FALSE;
}23、同22题要求，试基于图的广度优先搜索策略写一算法
/*
#define MAX_QUEUE_SIZE 30
typedef struct QNode {
VNnde data[MAX_QUEUE_SIZE];
int front;
int rear;
}Queue;
Status EnQueue(Queue* Q, VNnde e) {
if ((Q->rear + 1) % MAX_QUEUE_SIZE == Q->front)
return ERROR;
Q->data[Q->rear] = e;
Q->rear = (Q->rear + 1) % MAX_QUEUE_SIZE;
return OK;
}
Status DeQueue(Queue* Q, VNnde* e) {
if (Q->front == Q->rear)
return ERROR;
*e = Q->data[Q->front];
Q->front = (Q->front + 1) % MAX_QUEUE_SIZE;
return OK;
}
Status InitQueue(Queue* Q) {
Q->front = Q->rear = 0;
return OK;
}
*/
BOOL BFS(ALGraph* G, int i, int j) {
int Start = LocateVex(G, i);
int End = LocateVex(G, j);
if (Start == -1 || End == -1 || Start == End) return FALSE;
int* Visited = (int*)malloc(sizeof(int) * G->vexnum);
memset(Visited, 0, sizeof(Visited));
Queue Q;
VNnde Vex;
Visited[Start] = 1;
InitQueue(&Q);
EnQueue(&Q, G->vertices[Start]);
while (Q.front != Q.rear) {
DeQueue(&Q, &Vex);
ArcNode* p = Vex.firstarc;
while (p) {
if (!Visited[p->adjvex]) {
if (p->adjvex == End)
return TRUE;
EnQueue(&Q, G->vertices[p->adjvex]);
Visited[p->adjvex] = 1;
}
p = p->nextarc;
}
}
return FALSE;
}
24、试利用栈的基本操作编写，按深度优先搜索策略遍历一个强连通分量的非递归形式算法，算法中不规定具体的存储结构，而将图Graph看成是一种抽象的数据类型
思路：复习下强连通分量的定义：
有向图G的极大连通子图称为G的强连通分量
- 极大强连通子图意思是：该子图是G的强连通子图，将G的任何不在该子图中的顶点加入，子图不再是强连通的
算法如下所示：
void STraverse_Nonrecursive(Graph G) {
int visited[G->vexnum];
InitStack(S);
Push(S, GetVex(S, 1));//将第一个顶点入栈
visit(1);
visited = 1;
while (!StackEmpty(S)) {
while (Gettop(S, i) && i) {
j = FirstAdjVex(G, i);
if (j && !visited[j]) {
visit(j);
visited[j] = 1;
Push(S, j);//向左走到尽头
}
}
if (!StackEmpty) {
Pop(S, j);
Gettop(S, i);
k = NextAdjVex(G, i, j);//向右一步
if (k && !visited[k]) {
visit(k);
visited[k] = 1;
Push(S, k);
}
}
}
return;
}本算法的基本思想与二叉树的先序遍历非递归算法相同，由于是强连通图，所以从第一个结点出发一定能够访问到所有结点，而将该结点当作树的根结点，用记忆数组反之重复走就可以了
25、假设对有向图中n各顶点进行自然编号，并以三个数组s[1..max]，fst[1..n]和lst[1..n]表示之，其中数组s存放每个顶点的后继顶点的信息，第 i 个顶点后的后继顶点存放在 s 中下标从fst[i]起到lst[i]的分量中(i=1,2,..n)。若fst[i]>lst[i]，则第 i 个顶点无后继顶点，试编写判别该有向图中是否存在回路的算法
思路：这题做不出，网上也没得合适的答案，下列给出大佬的答案：
26、试证明，对有向图中顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全零的充要条件是：该有向图不含回路。然后写一算法对无环有向图的顶点重新编号，使其邻接矩阵变为下三角形，并输出新旧编号对照表。
这章节我只想到拓扑排序....，下面贴出拓扑排序的算法：
27、采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法：
思路：从给定结点出发深搜，定一个访问数组，防止走回路，然后给一个计步变量，判断所有步数为k的路径是否为终点即可，算法如下所示：
BOOL DFSing(ALGraph* G, int* Visited, int Start, int End, int k, int count) {
if (count == k && Start == End) return TRUE;
if (count > k) return FALSE;
ArcNode* p = G->vertices[Start].firstarc;
while (p) {
if (!Visited[p->adjvex]) {
Visited[p->adjvex] = 1;
if (DFSing(G, Visited, p->adjvex, End, k, count + 1))
return TRUE;
}
p = p->nextarc;
}
return FALSE;
}
BOOL DFS(ALGraph* G, int i, int j, int k) {
int Start = LocateVex(G, i);
int End = LocateVex(G, j);
if (Start == End || Start == -1 || End == -1)
return ERROR;
int* Visited = (int*)malloc(sizeof(int) * G->vexnum);
memset(Visited, 0, sizeof(Visited));
int count = 0;
Visited[Start] = 1;
ArcNode* p = G->vertices[Start].firstarc;
while (p) {
if ( !Visited[p->adjvex] ) {
Visited[p->adjvex] = 1;
if (DFSing(G, Visited, p->adjvex, End, k, count + 1))
return TRUE;
}
p = p->nextarc;
}
return FALSE;
}
28、已知有向图和图中两个顶点u和v，试编写算法求有向图中从u到v的所有简单路径，并以下图为例手工执行你的算法，画出相应的搜索过程图
思路：这题就是一道简单的递归回溯问题，算法如下所示：
/* 测试用例
5,8
1
2
3
4
5
1,2
1,4
2,3
2,5
4,5
3,5
1,5
3,4
*/
void DFSing(ALGraph* G, int* Visited, int Start, int End, int* temp, int** res, int *resleng, int templeng) {
if (Start == End) {
res[*resleng] = (int*)malloc(sizeof(int) * (templeng + 1));
for (int i = 0; i < templeng + 1; i++) res[*resleng][i] = -1;
for (int i = 0; i < templeng; i++)
res[*resleng][i] = temp[i];
(*resleng)++;
return;
}
ArcNode* p = G->vertices[Start].firstarc;
while (p) {
if (!Visited[p->adjvex]) {
Visited[p->adjvex] = 1;
temp[templeng] = p->adjvex;
templeng++;
DFSing(G, Visited, p->adjvex, End, temp, res, resleng, templeng);
templeng--;
Visited[p->adjvex] = 0;
}
p = p->nextarc;
}
return;
}
Status DFS(ALGraph* G, int v, int u) {
int Start = LocateVex(G, v);
int End = LocateVex(G, u);
if (Start == End || Start == -1 || End == -1)
return ERROR;
int** res = (int**)malloc(sizeof(int*) * 100);
int* temp = (int*)malloc(sizeof(int*) * 100);
int Visited[100];
memset(Visited, 0, sizeof(Visited));
int templeng = 0;
int resleng = 0;
Visited[Start] = 1;
ArcNode* p = G->vertices[Start].firstarc;
while (p) {
if (!Visited[p->adjvex]) {
Visited[p->adjvex] = 1;
temp[templeng] = p->adjvex;
templeng++;
DFSing(G, Visited, p->adjvex, End, temp, res, &resleng, templeng);
templeng--;
Visited[p->adjvex] = 0;
}
p = p->nextarc;
}
for (int i = 0; i < resleng; i++) {
int j = 0;
printf("V(%d)-->", G->vertices[Start].data);
while (res[i][j] != -1) {
printf("V(%d)-->", G->vertices[res[i][j]].data);
j++;
}
printf("\n");
}
return OK;
}29、试写一个算法，在以邻接矩阵方式存储的有向图G中求顶点 i 到 顶点 j 的不含回路的、长度为k的路径数
思路：一个递归回溯的算法，代码如下
void DFSing(MGraph* G, int Start, int End, int count, int k, int** res, int* Visited, int* temp, int tempSize, int *resSize) {
printf("check\n");
if (count > k) return;
if (Start == End && count == k) {
res[*resSize] = (int*)malloc(sizeof(int) * (tempSize + 1));
for (int n = 0; n < tempSize + 1; n++) res[*resSize][n] = -1;
for (int m = 0; m < tempSize; m++)
res[*resSize][m] = temp[m];
(*resSize)++;
return;
}
for (int n = 0; n < G->vexnum; n++) {
if (!G->arcs[Start][n].adj||Visited[n]) continue;
Visited[n] = 1;
temp[tempSize] = n;
tempSize++;
DFSing(G, n, End, count + 1, k, res, Visited, temp, tempSize, resSize);
tempSize--;
Visited[n] = 0;
}
return;
}
Status DFS(MGraph* G, int i, int j, int k) {
int Start = LocateVex(G,i);
int End = LocateVex(G, j);
if (Start == -1 || End == -1 || Start == End)
return ERROR;
int count = 0;
int** res = (int**)malloc(sizeof(int*) * MAX_VERTEX_NUM);
int resSize = 0;
int* temp = (int*)malloc(sizeof(int) * MAX_VERTEX_NUM);
int tempSize = 0;
int Visited[MAX_VERTEX_NUM];
memset(Visited, 0, sizeof(Visited));
Visited[Start] = 1;
for (int n = 0; n < G->vexnum; n++) {
if (!G->arcs[Start][n].adj||Visited[n]) continue;
Visited[n] = 1;
temp[tempSize] = n;
tempSize++;
DFSing(G,n, End, count + 1, k, res, Visited, temp, tempSize, &resSize);
tempSize--;
Visited[n] = 0;
}
for (int i = 0; i < resSize; i++) {
int j = 0;
printf("V(%d)-->", G->vexs[Start]);
while (res[i][j] != -1) {
printf("V(%d)-->", G->vexs[res[i][j]]);
j++;
}
printf("\n");
}
return OK;
}
30、试写一个求有向图G中所有回路的算法
思路：根据上两算法一样，就是将End也设为Start就行，代码如下所示
void DFSing(MGraph* G, int Start, int End, int** res, int* Visited, int* temp, int tempSize, int *resSize) {
if (Start == End) {
res[*resSize] = (int*)malloc(sizeof(int) * (tempSize + 1));
for (int n = 0; n < tempSize + 1; n++) res[*resSize][n] = -1;
for (int m = 0; m < tempSize; m++)
res[*resSize][m] = temp[m];
(*resSize)++;
return;
}
for (int n = 0; n < G->vexnum; n++) {
if (!G->arcs[Start][n].adj||Visited[n]) continue;
Visited[n] = 1;
temp[tempSize] = n;
tempSize++;
DFSing(G, n, End, res, Visited, temp, tempSize, resSize);
tempSize--;
Visited[n] = 0;
}
return;
}
Status Print_(MGraph* G) {
for (int i = 0; i < G->vexnum; i++) {
for (int j = 0; j < G->vexnum; j++)
printf("%d ", G->arcs[i][j].adj);
printf("\n");
}
return OK;
}
Status DFS(MGraph* G) {
int** res = (int**)malloc(sizeof(int*) * MAX_VERTEX_NUM);
int resSize = 0;
int* temp = (int*)malloc(sizeof(int) * MAX_VERTEX_NUM);
int tempSize = 1;
int Visited[MAX_VERTEX_NUM];
memset(Visited, 0, sizeof(Visited));
Print_(G);
for (int Start = 0; Start < G->vexnum; Start++) {
temp[0] = Start;
for(int n=0;n<G->vexnum;n++){
if (!G->arcs[Start][n].adj || Visited[Start]) continue;
Visited[n] = 1;
temp[tempSize] = n;
tempSize++;
DFSing(G, n, Start, res, Visited, temp, tempSize, &resSize);
tempSize--;
Visited[n] = 0;
}
}
for (int i = 0; i < resSize; i++) {
int j = 0;
while (res[i][j] != -1) {
printf("V(%d)-->", G->vexs[res[i][j]]);
j++;
}
printf("\n");
}
return OK;
}测试图片如下：
31、试完成求有向图的强连通分量的算法，并分析算法的时间复杂度
int visited[MAX_VERTEX_NUM];
int finished[MAX_VERTEX_NUM];
int count;
void DFS1(OLGraph G, int v) {
visited[v] = 1;
for (ArcBox* p = G.xlist[v].firstout; p; p = p->tlink) {
int w = p->headvex;
if (!visited[w])DFS1(G, w);
}
finished[++count] = v;
return;
}
void DFS2(OLGraph G, int v) {
visited[v] = 1;
printf("V(%d)-->", G.xlist[v].data);
for (ArcBox* p = G.xlist[v].firstin; p; p = p->hlink) {
int w = p->tailvex;
if (!visited[w])DFS2(G, w);
}
return;
}
void Get_SGraph(OLGraph G) {
count = 0;
for (int i = 0; i < G.vexnum; i++)
visited[i] = 0;
for (int v = 0; v < G.vexnum; v++)
if (!visited[v]) DFS1(G, v);
for (int i = 0; i < G.vexnum; i++)
visited[i] = 0;
for (int i = G.vexnum - 1; i >= 0; i--) {
int v = finished[i];
if (!visited[v]) {
printf("\n");
DFS2(G, v);
}
}
return;
}
其时间复杂度跟深度优先搜素一样，也是O(n+e)的时间复杂度
32、修改prim算法，试之能在邻接表存储结构上实现求图的最小生成森林，并分析其时间复杂度(森林的存储结构为孩子兄弟链表)
void Addto_Forest(CTree* T, int i, int j) {
CTree p = NULL, q, r;
Locate(T, i, &p);//找到结点i对应的指针p
q = (CTree)malloc(sizeof(TNode));
q->data = j;
q->firstchild = q->nextsibling = NULL;
if (!p) {
p = (CTree)malloc(sizeof(TNode));
p->data = i;
p->firstchild = p->nextsibling = NULL;
for (r = *T; r->nextsibling; r = r->nextsibling);
r->nextsibling = p;
p->firstchild = q;
}//作为新树插入到最右侧
else if (!p->firstchild)//双亲还没有孩子
p->firstchild = q;//作为双亲的第一个孩子
else {
for (r = p->firstchild; r->nextsibling; r = r->nextsibling);
r->nextsibling = q;
}
return;
}
void Print_Tree(CTree T,ALGraph G) {
if (T) {
printf("V(%d)--> ", G.vertices[T->data].data);
Print_Tree(T->firstchild, G);
if (T->nextsibling) {
printf("\n");
Print_Tree(T->nextsibling, G);
}
}
return;
}
int Visited[MAX_VERTEX_NUM];
void Forest_Prim(ALGraph G, int k, CTree* T, int* Visited) {
CLosedge A;
for (int j = 0; j < G.vexnum; j++) {
if (j == k) continue;
A[j].adjvex = k;
A[j].Lowcost = INFMAX;
for (ArcNode* p = G.vertices[j].firstarc; p; p = p->nextarc)
if (p->adjvex == k) A[j].Lowcost = p->weight;
}
Visited[k] = 1;
A[k].Lowcost = A[k].adjvex = -1;
for (int i = 1; i < G.vexnum; i++) {
int k = MinVex(G, A);
Visited[k] = 1;
if (k != -1 && A[k].Lowcost < INFMAX) {
Addto_Forest(T, A[k].adjvex, k);
A[k].Lowcost = A[k].adjvex = -1;
for (ArcNode* p = G.vertices[k].firstarc; p; p = p->nextarc)
if (p->weight < A[p->adjvex].Lowcost) {
A[p->adjvex].adjvex = k;
A[p->adjvex].Lowcost = p->weight;
}
}
else {
int n = 0;
while (n < G.vexnum) {
if (!Visited[n]) break;
n++;
}
if (n >= G.vexnum) return;
Forest_Prim(G, n, T, Visited);
}
}
return;
}
void Print_ArcList(ALGraph G) {
for (int i = 0; i < G.vexnum; i++) {
printf("V(%d)：", G.vertices[i].data);
ArcNode* p = G.vertices[i].firstarc;
while (p) {
printf("V(%d)-->", G.vertices[p->adjvex].data);
p = p->nextarc;
}
printf("\n");
}
return;
}
33、已知无向图的边集存放在某个类型为EdgeSetType的数据结构EdgeSet 中（没有端点相重的环边），并在此结构上已定义两种基本运算:
(1)函数GetMinEdge(EdgeSet, u, v)：若EdgeSet非空，则必存在最小边，变参u和v分别含最小边上两顶点，并返回true；否则返回false；
(2)过程DelMinEdge(EdgeSet, u, v)：从EdgeSet中删除依附于顶点u和v的最小边。 试在上述结构上实现求最小生成树（以孩子-兄弟链表表示）的克鲁斯卡尔算法。
34试编写一个算法，给有向无环图G中每个顶点赋以一个整数序号，并满足以下条件：若从顶点i至顶点j有一条弧，则应使i<j。
思路：就是一个拓扑排序，代码如下：
Status TopSort(ALGraph* G) {
//拓扑排序
int* Stack = (int*)malloc(sizeof(int) * G->vexnum);//栈作为记录入度量为0的顶点
int top = -1;
int count = 0;//累加器
for (int i = 0; i < G->vexnum; i++) {
if (G->vertices[i].in == 0) {
top++;
Stack[top] = i;//记录其顶点序号
}
}
int OutVex, InVex;
while (top != -1) {
OutVex = Stack[top--];//出度边等于栈顶元素，按照其约定，需要删去其所有出度边
p = G->vertices[OutVex].firstarc;
printf("%d ", G->vertices[OutVex].data);//打印顶点，打印其拓扑序列
while (p) {
InVex = p->adjvex;
G->vertices[InVex].in--;//不改变其逻辑结构，为拓扑排序只改变其入度量
if (G->vertices[InVex].in == 0) Stack[++top] = InVex;
p = p->nextarc;
}
}
if (count < G->vexnum) {
printf("存在回路\n");
return ERROR;
}
return OK;
}35、若在DAG图中存在一个顶点r，在r和图中所有其他顶点之间均存在由r出发的有向路径，则称该DAG图有根，试编写求DAG图根的算法：
思路：有向无环图中根为唯一，则就是拓扑排序的起点，算法如下所示：
void FindInDegree(ALGraph G, int* indegree) {
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
if (i == j)continue;
ArcNode* p = G.vertices[j].firstarc;
while (p) {
if (p->adjvex == i) indegree[i]++;
p = p->nextarc;
}
}
}
return;
}
BOOL DGA(ALGraph G, char* root) {
//求DAG图的根(求拓扑序列起点)
int indegree[MAX_VERTEX_NUM + 1];
int k, count;
memset(indegree, 0, sizeof(indegree));
FindInDegree(G, indegree);//对各顶点求入度已定义
for (k = 0, count = 0; k < G.vexnum; k++) {
if (!indegree[k]) {
count++;
*root = G.vertices[k].data;
}
}
if (count == 1) return TRUE;//有向无环弱连通图的根若存在则唯一
return ERROR;
}36、在图的邻接表存储结构中，为每个顶点增加一个MPL域，试写一算法，求有向无环图G的每个顶点出发的最长路径长度，并存入MPL域，请给出算法的时间复杂度。
思路：用递归求解，深搜反推每一个结点的最长路径
int DFSing(ALGraph* G, int start) {
int maxlen = 0;//最长路径初始化为0
for (ArcNode* p = G->vertices[start].firstarc; p; p = p->nextarc) {
maxlen = p->weight;//深搜等于这条路径的权值
maxlen += DFSing(G, p->adjvex);//加上下个顶点的最大路径
if (maxlen > G->vertices[start].MPL) G->vertices[start].MPL = maxlen;//若当前路径比之前路径长，则更新
}
return G->vertices[start].MPL;
}
Status LongestPath(ALGraph* G) {
//求出入度为0的结点作为起点，DAG图中只有一个为根的顶点
int* indge = (int*)malloc(sizeof(int) * G->vexnum);
memset(indge, 0, sizeof(indge));
for (int i = 0; i < G->vexnum; i++)
for (ArcNode* p = G->vertices[i].firstarc; p; p = p->nextarc)
indge[p->adjvex]++;
int count = 0;
int index = -1;
for (int i = 0; i < G->vexnum; i++) {
if (!indge[i]) {
count++;
index = i;
}
}
if (count != 1 || index == -1) return ERROR;
DFSing(G, index);
for (int i = 0; i < G->vexnum; i++)
printf("V(%d) 's longest path length：%d\n", G->vertices[i].data, G->vertices[i].MPL);
system("pause");
return OK;
}
测试图：
其时间复杂度和深搜复杂度相同，O(n+e)空间是深搜栈的空间
37、试设计一个求有向无环图中最长路径的算法，并估计其时间复杂度
思路：对36题算法稍作修改，用一个一维数组记录下路径即可，代码如下所示：
int DFSing(ALGraph* G, int start, int path[][MAX_VERTEX_NUM]) {
int maxlen = 0;
for (ArcNode* p = G->vertices[start].firstarc; p; p = p->nextarc) {
maxlen = p->weight;
maxlen += DFSing(G, p->adjvex, path);
if (maxlen > G->vertices[start].MPL) {
//添加路径
G->vertices[start].MPL = maxlen;
path[start][0] = path[p->adjvex][0] + 1;
path[start][path[start][0] - path[p->adjvex][0]] = p->adjvex;
for (int i = path[start][0] - path[p->adjvex][0] + 1, j = 1; j <= path[p->adjvex][0]; i++, j++)
path[start][i] = path[p->adjvex][j];
}
}
return G->vertices[start].MPL;
}
Status LongestPath(ALGraph* G) {
int* indge = (int*)malloc(sizeof(int) * G->vexnum);
memset(indge, 0, sizeof(indge));
for (int i = 0; i < G->vexnum; i++)
for (ArcNode* p = G->vertices[i].firstarc; p; p = p->nextarc)
indge[p->adjvex]++;
int count = 0;
int index = -1;
for (int i = 0; i < G->vexnum; i++) {
if (!indge[i]) {
count++;
index = i;
}
}
if (count != 1 || index == -1) return ERROR;
int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
for (int i = 0; i < G->vexnum; i++)
memset(path[i], 0, sizeof(path[i]));
DFSing(G, index, path);
//寻找最长路径
int MaxPath = 0;
int k = -1;
for (int i = 0; i < G->vexnum; i++) {
if (MaxPath > G->vertices[i].MPL) {
MaxPath = G->vertices[i].MPL;
k = i;
}
}
//打印所有路径，稍作修改即可打印最长路径，方便检查
for (int i = 0; i < G->vexnum; i++) {
printf("V(%d)：", G->vertices[i].data);
for (int j = 1; j <= path[i][0]; j++)
printf("V(%d)--> ", path[i][j] );
printf("\n");
}
system("pause");
return OK;
}38、一个四则运算算术表达式以有向无环图的邻接表方式存储，每个操作数原子都由单个字母表示，写一个算法输出其逆波兰表达式
题意：别被复杂的逻辑图蒙蔽了双眼，这题就是结合树的后根遍历在邻接表上实现，代码如下所示：
us Post_traversal(ALGraph* G,int root) {
for (int i = root; i < G->vexnum; i++) {
ArcNode* p = G->vertices[i].firstarc;
while (p) {
//不需要记忆数组 ，因为有向无环图无环，不会出现重路
Post_traversal(G, p->adjvex);
p = p->nextarc;
}
}
printf("%c", G->vertices[root].data);
return OK;
}39、把存储结构改为二叉链表，重做38题
思路：就是树的后序遍历，代码如下：
Status Post_traversal(BinTree *T) {
if (T) {
Post_traversal(&T->lchild);
Post_traversal(&T->rchild);
printf("%c", T->data);
}
return OK;
}40、若38题的运算符和操作数原子分别由字符和整数表示，请设计邻接表的结类型，并且写一个表达式求值的算法
41和42题由于太麻烦，涉及到的就是关键路径和单源最短路迪杰斯特拉算法，我不太想浪费时间在重新构造图的存储结构上面，由于马上需要竞赛，所以暂且搁置，有意查询可以移步大佬博客：https://www.cnblogs.com/kangjianwei101/p/5244218.html