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

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]);
}
}

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);
} 
}

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 存在一条边且回路长度大于 1
has=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;
}
}

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 入队，初始层次为 0

    while (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 表示路径长度，初始为 0
    int w, i;
    ArcNode *p;
    path[d] = u; // 将顶点 u 加入到路径中
    d++; // 顶点数增 1
    visited[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; // 恢复环境，使该顶点可重新使用
}