李春葆《数据结构》——图相关代码

邻接矩阵结构体：

#define MAX<最大结点个数>
#define INF 32765 //定义无穷 
typedef struct{int no;//顶点的编号；InfoType info;//顶点的其他信息 
}vertexType;//顶点的类型 
typedef struct{int edges[MAX][Max];//邻接矩阵数组 int vertexType vexs[MAX];//存放顶点的信息int n,e;//顶点数，边数 
}MatGraph; 

邻接表结构体：

typedef struct ANode{int adjvex;//该编的邻接点编号struct ANode *nextarc;//指向下一条边的指针int weight;//权值 
}ArcNode;//边结点类型 typedef struct Vnode{InfoType info;//顶点的其他信息 ArcNode *firstarc;//指向第一个边结点 
}VNode; typedef struct {VNode adjlist[MAX];//邻接表的头节点数组int n,e; //顶点数，边数 
}AdjGraph;

一：带权图。邻接矩阵转换为邻接表。

思想：找不为0和无穷的元素，能够找到，则存在边。头插法插到单链表中。

代码：

void MatToList(MatGraph g,AdjGraph *&G){int i,j;ArcNode *p;G=(AdjGraph *)malloc(sizeof(AdjGraph));for(i=0;i<g.n;i++){G->adjlist[i].firstarc=NULL;//所有头结点指针域置空 }for(i=0;i<g.n;i++){for(j=0;j<g.n;j++){if(g.edges[i][j]!=0&&g.edges[i][i]!=INF){p=(ArcNode*)malloc(sizeof(ArcNode));//创建边结点p->adjvex=j;p->weight=g.edges[i][j];p->nextarc=G->adjlist[i].firstarc;//用头插法插入 G->adjlist[i].firstarc=p;}}} 
} 

二：带权图。邻接表转换为邻接矩阵。

思想：遍历邻接表中的所有单链表，通过第i个单链表查找顶点i的相邻结点p，将邻接矩阵g中的元素g.edges[i][p->adjvex]=p->weight。

代码：

void ListToMat(AdjGraph *G,MatGraph,&g){int i;ArcNode *p;for(i=0;i<G->n;i++){p=G.adjlist[i].firstarc;//p指向第i个单链表的头结点 while(p!=NULL){g.edges[i][p->adjvex]=p->weight;p=p->nextarc;}}g.n=G->n,g.e=G->e;
}

图的深度优先遍历代码：

int visited[Max]={0};//全局数组
void DFS(AdjGraph *G,int v){ArcNode *p;visited[v]=1;printf("%d",v);p=G->adjlist[v].firstarc;while(p!=NULL){if(visited[p->adjvex]==0){DFS(G,p->adjvex);}p=p->nextarc;}
} 

图的深度优先遍历的应用

（1）图采用邻接表存储。设计一个算法判断从顶点u到顶点v是否存在简单路径。

简单路径：路径上不存在重复结点。

代码：

bool ExistPath(AdjGraph *G,int u,int v){int w;ArcNode *p;visited[u]=1;if(u==v) return true;p=G->adjlist[u].firstarc;while(p!=NULL){w=p->adjvex;if(visited[w]==0){if(ExistPath(G,w,v)) return true;}p=p->nextarc;}return false;
}

（2）图采用邻接表存储。输出从顶点u到顶点v的一条简单路径。（假设至少存在一条）

代码：

void FindPath(AdjGraph *G,int u,int v,int path[],int d){//d表示path中的路径长度，假设初始为-1。 int w,i;ArcNode *p; visited[u]=1;d++;path[d]=u;if(u==v){for(i=0;i<=d;i++){printf("%d",path[i]);}printf("\n");return;}p=G->adjlist.firstarc;while(p!=NULL){w=p->adjvex;if(visited[w]==0){FindPath(G,w,v,path,d);}p=p->nextarc;}
}

（3）图采用邻接表存储。输出从顶点u到顶点v的所有简单路径。

代码：

void FindAllPath(AdjGraph *G,int u,int v,int path[],int d){//d表示path中的路径长度，假设初始为-1。 int w,i;ArcNode *p; visited[u]=1;d++;path[d]=u;if(u==v){for(i=0;i<=d;i++){printf("%d",path[i]);}printf("\n");visited[u]=0;//恢复环境 return;}p=G->adjlist.firstarc;while(p!=NULL){w=p->adjvex;if(visited[w]==0){FindAllPath(G,w,v,path,d);}p=p->nextarc;}visited[u]=0;//恢复环境，使该顶点可以重复访问 
}

（4）图采用邻接表存储。输出从顶点u到顶点v长度为a的所有简单路径。

代码：

void PathlenAll(AdjGraph *G,int u,int v,int path[],int d){//d表示path中的路径长度，假设初始为-1。 int w,i;ArcNode *p; visited[u]=1;d++;path[d]=u;if(u==v&&d==a){//限制要输出的路径长度为a for(i=0;i<=d;i++){printf("%d",path[i]);}printf("\n");visited[u]=0;//恢复环境 return;}p=G->adjlist.firstarc;while(p!=NULL){w=p->adjvex;if(visited[w]==0){PathlenAll(G,w,v,path,d);}p=p->nextarc;}visited[u]=0;//恢复环境，使该顶点可以重复访问 
}

（5）图采用邻接表存储。求图中通过顶点k的所有简单回路。

代码：

int visited[Max];//全局变量
void DFSPath(AdjGraph *G,int u,int v,int path[],int d){int w,i;ArcNode *p;visited[u]=1;d++;path[d]=u;p=G->adjlist.firstarc;while(p!=NULL){w=p->adjvex;if(w==v&&d>1){//找到回路输出 printf(" ");for(i=0;i<=d;i++){printf("%d",path[i]);}printf("%d\n",v);}if(visited[w]==0){DFSPath(G,w,v,path,d);}p=p->nextarc;}visited[u]=0;//恢复环境，使该顶点可以重复访问 
}
void FindCyclePath(AdjGraph *G,int k){int path[MAX];DFSPath(G,k,k,path,-1);
}

图的广度优先遍历代码：

void BFS(AdjGraph *G,int v){int i,w;ArcNode *p;SqQueue *q;InitQueue(q);int visited[Max];for(i=0;i<G->n;i++){visited[i]=0;//标记数组初始化 } printf("%d",v);visited[v]=1;enQueue(q,v);while(!QueueEmpth(q)){deQueue(q,w);p=G->adjlist.firstarc;while(p!=NULL){if(visited[p->adjvex]==0){printf("%d",p->adjvex);visited[p->adjvex]=1;enQueu(q,p->adjvex);}p=p->nextarc;}} printf("\n");
} 

图的广度优先遍历的应用

（1）图采用邻接表存储。设计一个算法求不带权连通图G从顶点u到顶点v的最短路径

代码：

// 定义邻接表中边节点结构体
typedef struct ArcNode {int adjvex;                // 该边的终点编号struct ArcNode *nextarc;   // 指向下一条边的指针int weight;              // 该边的权值等信息
} ArcNode;// 定义邻接表中顶点节点结构体
typedef struct VNode {char data;                 // 顶点信息ArcNode *firstarc;         // 指向第一条边
} VNode;// 定义邻接表图结构体
typedef struct {VNode adjlist[MAX];       // 假设最大顶点数为100，可根据实际情况修改int n, e;                 // 图中顶点数n和边数e
} ALGraph;// 定义队列元素结构体
typedef struct {int data;        // 顶点编号int parent;      // 前一个顶点的位置
} QUERE;// 输出从顶点u到顶点v的最短逆路径
void ShortPath(ALGraph *G, int u, int v) {ArcNode *p;int w, i;Queue qu[MAX]; // 假设最大顶点数为100，定义非循环队列，可根据实际情况修改int front = -1, rear = -1; // 队列的头、尾指针int visited[MAX];// 初始化访问数组for (i = 0; i < G->n; i++) {visited[i] = 0;}// 将起始顶点u入队rear++;qu[rear].data = u;qu[rear].parent = -1;visited[u] = 1;// 队列不为空时进行循环while (front!= rear) {front++;w = qu[front].data;// 找到目标顶点v，输出最短逆路径if (w == v) {i = front;while (qu[i].parent!= -1) {printf("%d ", qu[i].data);i = qu[i].parent;}printf("%d ", qu[i].data);printf("\n");break;}// 取出当前顶点w的第一条边p = G->adjlist[w].firstarc;while (p!= NULL) {if (visited[p->adjvex] == 0) {visited[p->adjvex] = 1;// 将未访问过的邻接点入队rear++;qu[rear].data = p->adjvex;qu[rear].parent = front;}// 查找当前顶点w的下一条边p = p->nextarc;}}
}

（2）图采用邻接表存储。设计一个算法求不带权连通图G从顶点u到顶点v的最短路径长度（指路径上的边数）。

代码：

// 定义邻接表中边节点结构体
typedef struct ArcNode {int adjvex;                // 该边的终点编号struct ArcNode *nextarc;   // 指向下一条边的指针int weigth;              // 该边的权值等信息
} ArcNode;// 定义邻接表中顶点节点结构体
typedef struct VNode {char data;                 // 顶点信息ArcNode *firstarc;         // 指向第一条边
} VNode;// 定义邻接表图结构体
typedef struct {VNode adjlist[MAX];       // 假设最大顶点数为100，可根据实际情况修改int n, e;                 // 图中顶点数n和边数e
} ALGraph;// 定义队列元素结构体
typedef struct {int data;        // 顶点编号int parent;      // 前一个顶点的位置
} QUERE;// 输出从顶点u到顶点v的最短逆路径，并返回最短路径长度
int ShortPath(ALGraph *G, int u, int v) {ArcNode *p;int w, i;Queue qu[MAX]; int front = -1, rear = -1; // 队列的头、尾指针int visited[MAX];int distance[MAX]; // 新增数组用于记录每个顶点到起始顶点u的距离// 初始化访问数组和距离数组for (i = 0; i < G->n; i++) {visited[i] = 0;distance[i] = -1; // 初始化为 -1，表示未到达过}// 将起始顶点u入队，设置距离为0rear++;qu[rear].data = u;qu[rear].parent = -1;visited[u] = 1;distance[u] = 0;// 队列不为空时进行循环while (front!= rear) {front++;w = qu[front].data;// 找到目标顶点v，输出最短逆路径并返回最短路径长度if (w == v) {i = front;while (qu[i].parent!= -1) {printf("%d ", qu[i].data);i = qu[i].parent;}printf("%d ", qu[i].data);printf("\n");return distance[v];}// 取出当前顶点w的第一条边p = G->adjlist[w].firstarc;while (p!= NULL) {if (visited[p->adjvex] == 0) {visited[p->adjvex] = 1;// 将未访问过的邻接点入队rear++;qu[rear].data = p->adjvex;qu[rear].parent = front;// 更新距离数组，距离为当前顶点w的距离加1distance[p->adjvex] = distance[w] + 1;}// 查找当前顶点w的下一条边p = p->nextarc;}}return -1; // 如果未找到路径，返回 -1
}