李春葆《数据结构》-课后习题代码题

一：假设不带权有向图采用邻接矩阵 g 存储，设计实现以下功能的算法：

（1）求出图中每个顶点的入度。

代码：

void indegree(MatGraph g){int i,j,n;printf("各个顶点的入度：\n");for(int j=0;j<g.n;j++){n=0;for(int i=0;i<g.n;i++){if(g.edges[i][j]!=0){n++;}}printf(" 顶点%d:%d\n",j,n);}
}

（2）求出图中每个顶点的出度。

代码：

void outdegree(MatGraph g){int i,j,n;printf("各个顶点的出度：\n");for(int i=0;i<g.n;i++){n=0;for(int j=0;j<g.n;j++){if(g.edges[i][j]!=0){n++;}}printf(" 顶点%d:%d\n",i,n);}
}

（3）求出图中出度为0的顶点数。

代码：

void zeroOutdegree(MatGraph g){int i,j,n;printf("出度为0的顶点：\n");for(int i=0;i<g.n;i++){n=0;for(int j=0;j<g.n;j++){if(g.edges[i][j]!=0){n++;}}	if(n==0)printf("%d\n",i);}printf("\n");
}

二：假设不带权有向图采用邻接表 G 存储，设计实现以下功能的算法：

（1）求出图中每个顶点的入度。

代码：

void indegree(AdjGraph *g){ArcNode *p;int A[MAX],i;for(i=0;i<g->n;i++){A[i]=0;}for(i=0;i<g->n;i++){//扫描所有头结点p=g->adjlist[i].firstarc;while(p!=NULL){A[p->adjvex]++;//表示 i 到 p->adjvex 顶点有一条边p=p->nextarc;}}printf("各个顶点的入度：\n");for(i=0;i<g->n;i++){printf(" 顶点%d:%d\n",i,A[i]);}
}

（2）求出图中每个顶点的出度。

代码：

void outdegree(AdjGraph *g){ArcNode *p;int i,n;printf("各个顶点的出度：\n");for(i=0;i<g->n;i++){n=0;p=g->adjlist[i].firstarc;while(p!=NULL){n++;p=p->nextarc;}printf(" 顶点%d:%d\n",i,n);} 
}

（3）求出图中出度为0的顶点数。

代码：

void zeroOutdegree(AdjGraph *g){ArcNode *p;int i,n;printf("各出度为0的顶点：\n");for(i=0;i<g->n;i++){n=0;p=g->adjlist[i].firstarc;while(p!=NULL){n++;p=p->nextarc;}if(n==0){printf("%d\n",i);}} printf("\n");
}

三：假设一个连通图采用邻接表作为存储结构，试设计一个算法，判断其中是否存在经过顶点 v 的回路。

思想：利用深度优先遍历。从顶点 v 出发进行深度优先遍历，用 d 记录走过的路径长度，对每个访问的顶点设置标记为 1。若当前访问顶点 u，表示 vu 存在一条路径，如果顶点 u 的邻接点 w 等于 v 并且 d>1，表示顶点 u 到 v 有一条边，即构成经过顶点 v 的回路。Cycle 算法中 has 是布尔值，初始调用时置为 false，执行后若为 true 表示存在经过顶点 v 的回路， 否则表示没有相应的回路。

代码：

int visited[Max];//全局变量
void Cycle(AdjGraph *G,int u,int v,int d,int &has){//has初始为false,d=-1 int w,i;ArcNode *p;visited[u]=1;d++;p=G->adjlist.firstarc;while(p!=NULL){w=p->adjvex;if(visited[w]==0){//若顶点 w 未访问,递归访问它Cycle(G,w,v,d,has);}else if (w=v&&d>1){//u 到 v 存在一条边且回路长度大于 1has=true;return;}p=p->nextarc;//找下一个邻接点}
}
bool FindCyclePath(AdjGraph *G,int k){bool has = false;Cycle(G,v,v,-1,has);return has;
}

四：假设图 G 采用邻接表存储，试设计一个算法，判断无向图 G 是否是一棵树。若是树，返回真；否则返回假。

思想：一个无向图 G 是一棵树的条件是：G 必须是无回路的连通图或者是有 n-1 条边的 连通图。这里采用后者作为判断条件，通过深度优先遍历图 G，并求出遍历过的顶点数 vn 和边数 en，若 vn==G->n 成立（表示为连通图）且 en==2*(G->n-1)（遍历边数为 2*(G->n-1)）成立，则 G 为一棵树。

代码：

//先求无向图的顶点数和边数
void DFS(AdjGraph *G,int v,int &vn,int &en){ArcNode *p;visited[v]=1;vn++;p=p->adjvex[v].firstarc;while(p!=NULL){en++;if(visited[p->adjvex]==0){DFS(G,p->adjvex,vn,en);}p=p->nextarc;}
} 
//判断是否为一棵树 
int IsTree(AdjGraph *G){int vn=0,en=0,i;int visited[MAX];for(i=0;i<G->n;i++){visited[i]=0;}DFS(G,1,vn,en);if(vn==G->n&&en==2*(G->n-1)){return 1;}else{return 0;}
}

五：设有 5 地（ 0 ～ 4 ）之间架设有 6 座桥（ A ～ F ），如图 所示，设计一个算法，

从某一地出发，经过每座桥恰巧一次，最后仍回到原地。

思想：该实地图对应的一个无向图 G 如图所示，本题变为从指定点 k 出发找经过所有 6 条边回到 k 顶点的路径。

代码：

int vedge[MAXV][MAXV]; //边访问数组,vedge[i][j]表示(i,j)边是否访问过
void Traversal(AdjGraph *G, int u, int v, int k, int path[], int d) {//开始时,d=-1 int w,i;ArcNode *p;d++;path[d] = v; // (u,v) 加入到 path 中vedge[u][v] = vedge[v][u] = 1; // (u,v) 边已访问p = G->adjlist[v].firstarc; // p 指向顶点 v 的第一条边while (p != NULL) {w = p->adjvex; // (v,w) 有一条边if (w == k && d == G->e - 1) { // 找到一个回路，输出之printf(" %d->", k);for (i = 0; i <= d; i++) {printf("%d->", path[i]);}printf("%d\n", w);}if (vedge[v][w] == 0) { // (v,w) 未访问过,则递归访问之Traversal(G, v, w, k, path, d);}p = p->nextarc; // 找 v 的下一条边}vedge[u][v] = vedge[v][u] = 0; // 恢复环境：使该边点可重新使用
}void FindCPath(AdjGraph *G, int k) { // 输出经过顶点 k 和所有边的全部回路int path[MAXV];int i, j, v;ArcNode *p;for (i = 0; i < G->n; i++) {// vedge 数组置初值for (j = 0; j < G->n; j++)if (i == j) vedge[i][j] = 1;else vedge[i][j] = 0;}printf("经过顶点%d 的走过所有边的回路:\n", k);p = G->adjlist[k].firstarc;while (p != NULL) {v = p->adjvex;Traversal(G, k, v, k, path, -1);p = p->nextarc;}
}

六：设不带权无向图 G 采用邻接表表示，设计一个算法求源点 i 到其余各顶点的最短路径。

思想： 利用广度优先遍历的思想，求 i 和 j 两顶点间的最短路径转化为求从 i 到 j 的层数，

为此设计一个 level [] 数组记录每个顶点的层次。

代码：

void ShortPath(AdjGraph *G, int i) {int qu[MAX], level[MAX]; // 队列和层次数组int front = 0, rear = 0, k, lev; // k 保存当前顶点，lev 保存从 i 到访问顶点的层数ArcNode *p; // 边节点指针visited[i] = 1; // 标记顶点 i 已访问rear++; qu[rear] = i; level[rear] = 0; // 将顶点 i 入队，初始层次为 0while (front != rear) { // 当队列不为空时执行front = (front + 1) % MAX; // 出队操作k = qu[front]; // 获取队首元素lev = level[front]; // 获取该元素的层次if (k != i) {printf("顶点%d 到顶点%d 的最短距离是:%d\n", i, k, lev); // 打印从 i 到 k 的最短距离}p = G->adjlist[k].firstarc; // 获取顶点 k 的邻接表头指针while (p != NULL) { // 遍历 k 的所有邻接点if (visited[p->adjvex] == 0) { // 如果邻接点未被访问过visited[p->adjvex] = 1; // 标记为已访问rear = (rear + 1) % MAXV; // 入队操作qu[rear] = p->adjvex; // 将邻接点入队level[rear] = lev + 1; // 更新层次}p = p->nextarc; // 移动到下一个邻接点}}
}

七： 对于一个带权有向图，设计一个算法输出从顶点 i 到顶点 j 的所有路径及其路径长度。调用该算法求出图中顶点 0 到顶点 3 的所有路径及其长度。

代码：

int visited[MAX]; //用于标记顶点是否被访问过
void findpath(AdjGraph *G, int u, int v, int path[], int d, int length) {// d 表示 path 中顶点个数，初始为 0；length 表示路径长度，初始为 0int w, i;ArcNode *p;path[d] = u; // 将顶点 u 加入到路径中d++; // 顶点数增 1visited[u] = 1; // 标记顶点 u 已访问if (u == v && d > 0) { // 如果找到一条路径且路径非空printf("路径长度:%d, 路径:", length);for (i = 0; i < d; i++) {printf("%2d", path[i]);}printf("\n");}p = G->adjlist[u].firstarc; // p 指向顶点 u 的第一个邻接点while (p != NULL) {w = p->adjvex; // w 为顶点 u 的邻接点if (visited[w] == 0) { // 如果 w 顶点未访问，递归访问它findpath(G, w, v, path, d, p->weight + length);}p = p->nextarc; // p 指向顶点 u 的下一个邻接点}visited[u] = 0; // 恢复环境，使该顶点可重新使用
}