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

邻接矩阵结构体：

#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
}