一：假设不带权有向图采用邻接矩阵 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，表示 vu 存在一条路径，如果顶点 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;
}
}
五：设有
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 入队，初始层次为 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; // 恢复环境，使该顶点可重新使用
}
