李春葆《数据结构》——图相关代码
邻接矩阵结构体：
#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入队，设置距离为0
rear++;
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的距离加1
distance[p->adjvex] = distance[w] + 1;
}
// 查找当前顶点w的下一条边
p = p->nextarc;
}
}
return -1; // 如果未找到路径，返回 -1
}原文地址：https://blog.csdn.net/m0_56332819/article/details/143920951
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！