数据结构C语言--图

设计存储结构体

在C语言中，常用的图的基本操作包括：

1. 创建图：通过定义节点和边等基本数据结构，可以使用结构体或邻接矩阵等方式创建图。
2. 遍历图：遍历图是指从图中某个顶点出发，依次访问图中所有节点的过程。常见的遍历算法有广度优先遍历（BFS）和深度优先遍历（DFS）。
3. 添加节点：向图中添加一个节点，一般需要在图的邻接表或邻接矩阵中增加对应信息。
4. 删除节点：从图中删除一个节点，需要删除与该节点相关的边和其在邻接表或邻接矩阵中的信息。
5. 添加边：向图中添加一条边，需要在邻接表或邻接矩阵中增加对应信息。
6. 删除边：从图中删除一条边，需要在邻接表或邻接矩阵中删除对应信息。
7. 查找节点：在图中查找一个节点，通常需要从图的邻接表或邻接矩阵中查找对应信息。
8. 查找路径：在图中查找两个节点之间的路径，可以使用深度优先搜索或广度优先搜索。
9. 判断连通性：判断图中两个节点是否连通，可以使用深度优先搜索或广度优先搜索。

图的应用非常广泛，如社交网络中的好友关系、电子地图中的城市路线、网络拓扑结构等等。因此，熟练掌握图的基本操作对于开发具有一定的重要性。

本文 只是小书童在学习中的笔记

graph_node.h头文件

Filename:“graph_node.h”

#pragma once

/*===============================================-邻接矩阵存储方式=================================================*/
#define MaxVertexNum 30  //设置最大顶点数

typedef char VertexType;   //设置结点元素类型
typedef int EdgeType;     //设置边元素数据类型

typedef struct {
	VertexType vertexs[MaxVertexNum];  //顶点表
	EdgeType arcs[MaxVertexNum][MaxVertexNum];  //临接矩阵，即边表
	int vertexNum, edgeNum;			//顶点数和边数
}MGragh;    //MGragh 是以邻接矩阵储存的图类型



/*======================邻接表存储算法==========================*/

#define MaxVertexNum 30   //设定最大顶点数

typedef char InfoType;

typedef struct node {//表节点
	int adjvertex;//邻接点域，一般存放顶点和对应的序号和在表头向量中的下标
	InfoType vertex;     //与边弧相关的信息
	struct node* next;	//指向下一个邻接点的指针域
}EdgeNode;

typedef struct vnode {//顶点结点
	VertexType vertex;
	EdgeNode* firstedge;
}VertexNode;

typedef struct {
	VertexNode adjlist[MaxVertexNum];  //邻接表
	int vertexNum, edgeNum;	//顶点数和边数
}ALGraph;  //以邻接表方式存储的图类型

/*===========================十字链表存储表示=============================*/

typedef struct ArcNode {
	int tailvertex, headvertex;		//该弧的尾和头顶点的位置
	struct ArcNode* hlink, * tlink;//分别为弧头相同和弧尾相同的链域
	InfoType info;			//该弧的相关信息
}ArcNode;

typedef struct VertexNode_arc {
	VertexType vertex;
	ArcNode* firsin, * firstout; //分别指向该顶点的第一条入弧和出弧
}Vertex_arc_Node;

typedef struct {
	Vertex_arc_Node xlist[MaxVertexNum];	//表头向量
	int vertexNum, edgeNum;		//顶点数和弧数
}OLGraph;
/*===========================表存储表示=============================*/


/*========================AVO--拓扑排序算法====================*/

//设计结构体
#define MaxVertexNum 30
typedef struct node_Avo  //设计表结点
{						
	int adjvertex;//邻接点域，存放顶点对应的序号或在表头向量中的下标
	struct node_Avo* next;//指向下一个邻接点的指针
}EdgeNode_Avo;

typedef struct vnode_Avo//设计顶点表结点
{
	int indegree;//存放顶点的入度
	int vertex;//顶点域
	EdgeNode_Avo* firstedge;//边表头指针
}VertexNode_Avo;
typedef struct
{
	VertexNode_Avo adjlist[MaxVertexNum];//邻接表
	int vertexNum, edgeNum;//顶点数  边数
}ALGraph_Avo;

/*=====================AVE--关键路径算法=========================*/
//设计结构体
typedef struct node_Ave
{						//设计表节点
	int adjvertex;//邻接点域
	int info;//弧的权值
	struct node_Ave* next;//下个结点的指针域
}EdgeNode_Ave;

typedef struct
{			//设计表头结点
	int indegree;//存放顶点的入度
	int vertex;///顶点域
	EdgeNode_Ave* firstedge;//边表头指针
}VertexNode_Ave;

typedef struct
{
	VertexNode_Ave adjlist[MaxVertexNum];//邻接表
	int vertexNum, edgeNum;//顶点数  边数
}ALGraph_Ave;//设计Ave图的储存结构

图的基本操作

Filename:“graph.h”

#pragma once
#include<stdio.h>
#include"graph_node.h"


/*================================图的基本操作===============================*/
#include<stdlib.h>

//创建图

#define MAX_WEIGHT 10000
//建立图的邻接矩阵表达
void  Creatgraph(MGragh *G)
{
	int i, j, k, w;
	printf("Emter vertexNum and edgeNum:(vertexNum,edgeNum):");
	scanf("%d,%d", &(G->vertexNum), &(G->edgeNum));		//输入图的顶点数和边数
	for (i = 0; i < G->vertexNum; i++)
	{
		printf("Eenter vertex:");
		scanf("%c", &(G->vertexs[i]));
	}
	for (i = 0; i < G->vertexNum; i++)
		for (j = 0; j < G->vertexNum; j++)
			G->arcs[i][j] = MAX_WEIGHT;		//初始化邻接矩阵
	for (k = 0; k < G->edgeNum; j++)
	{
		printf("Emter vertex_a to vertex_b and weight:(vertex_a,vertex_b,weight):");
		/*
		printf("Emter vertex_a to vertex_b :(vertex_a,vertex_b):");
		scanf("%d,%d,%d", &i, &j);
		G->arcs[i][j] = 1;
		*/
		scanf("%d,%d,%d", &i, &j,&w);//输入的为结点位置
		G->arcs[i][j] = w;   //若为带权图，输入权值w,赋值G->arcs[i][j]=w;
		G->arcs[j][i] = w;  //为无向图
	}
	
}

//建立有向图的邻接表存储
void CreatALGraph(ALGraph* G)
{
	//建立有向图的邻接表存储
	int i, j, k;
	EdgeNode* p;
	printf("Enter vertexNum and edgeNum(a,b):");
	scanf("%d,%d", &(G->vertexNum), &(G->edgeNum));		//读入顶点数和边数
	getchar();
	for (i = 0; i < G->vertexNum; i++)
	{
		printf("Enter vertex'name:");
		scanf("%c", &(G->adjlist[i].vertex));
		getchar();
		G->adjlist[i].firstedge = NULL;
	}
	for (k = 0; k < G->edgeNum; k++)
	{
		printf("Enter vertex to vertex(a,b):");
		scanf("%d,%d", &i, &j);//输入链表中结点的位置
		p = (EdgeNode*)malloc(sizeof(EdgeNode));
		p->adjvertex = j;
		p->next = G->adjlist[i].firstedge;
		G->adjlist[i].firstedge = p;	//头插法
	}
}

//建立十字链表的的有向图
void CreateOLgraph(OLGraph *G)
{
	//创建弧指针
	ArcNode* p;
	//采用十字链表表示，构建有向图
	printf("Enter vertexNum and edgeNum(a,b):");
	scanf("%d,%d", &(G->vertexNum), &(G->edgeNum));		//读入顶点数和弧数
	for (int i = 0; i < G->vertexNum; i++)
	{
		printf("Eenter vertex:");
		scanf("%c", &(G->xlist[i].vertex));//输入顶点值
		G->xlist[i].firsin = NULL; G->xlist[i].firstout = NULL;//初始化指针
	}
	//输入各弧，并构造十字链表
	for (int k = 0; k < G->edgeNum; k++)
	{
		int i, j;
		printf("Enter vertex to vertex(a,b):");
		scanf("%d,%d", &i, &j);//此时输入位置，亦可创建locaeVErtex来查询位置
		p = (ArcNode*)malloc(sizeof(ArcNode));
		p->tailvertex = i; p->headvertex = j;
		p->tlink = G->xlist[i].firsin; G->xlist[j].firstout = p;
		p->hlink = G->xlist[j].firsin; G->xlist[j].firsin = p;
		//对弧结点进行赋值并完成弧链头的插入
	}
}

#define false 0
#define true 1

int visited[MaxVertexNum];
void DFS(ALGraph G, int v);

void DFStraverse(ALGraph G)
{//深度优先遍历以邻接表示的图
	printf("深度优先遍历以邻接表示的图:\n");
	int v;
	for (v = 0; v < G.vertexNum; v++)
		visited[v] = false;		//标志向量初始化
	for (v = 0; v < G.vertexNum; v++)
		if (!visited[v])DFS(G, v);
}

void DFS(ALGraph G, int v)
{//从第v个顶点出发深度优先遍历图G
	EdgeNode* p;
	int w;
	printf("%c\t",G.adjlist[v].vertex); visited[v] = true;//访问第v个顶点，并把访问标志置true
	for (p = G.adjlist[v].firstedge; p; p = p->next)
	{
		w = p->adjvertex;
		if (!visited[w]) DFS(G, w);//对尚未访问的邻接顶点w递归调用DFS
	}
}

//广度优先遍历--邻接表
#include"Seqqueue.h"

void BFS(ALGraph G, int v)
{
	printf("广度优先遍历图：\n");
	int s;
	for (s = 0; s < G.vertexNum; s++)
		visited[s] = false;		//标志向量初始化
	//从v出发按广度优先遍历图G;使用辅助队列和访问标志数组visited
	EdgeNode* p;
	int  w;
	VertexNode u;
	PSeqQueue Q;		//定义一个队列
	Q = Init_SeqQueue(); //初始化队列
	printf("%c\t", G.adjlist[v].vertex);   //访问v
	visited[v] = true;  //访问标志量true
	In_SeqQueue(Q, G.adjlist[v]);
	while (!Empty_SeqQueue(Q))
	{
		Out_SeqQueue(Q, &u);
		for (p = u.firstedge; p; p = p->next)
		{
			w = p->adjvertex;
			if (!visited[w])
			{
				printf("%c\t", G.adjlist[w].vertex);
				visited[w] = true;
				In_SeqQueue(Q, G.adjlist[w]);
			}
		}

	}
}
/*==================最小生成树的实现=======================*/

//prim算法生成最小生成树
#define INFINITY 30000//定义权值的最大值与建立邻接矩阵中的无穷等价代换
#define MaxVertexNum 30 //最大的顶点数为30

typedef struct
{
	int adjvertex;  //某顶点与已经构建好的生成树的顶点之间的权值最小的顶点
	int lowcost;	//某顶点与已经构建好的树生成树的顶点的最小权值
}CloseEdge[MaxVertexNum];

void MiniSpanTree_PRIM(MGragh G, int u, CloseEdge closeedge)
{
	//从第u个顶点出发构造图G的最小生成树，最小生成树的信息存放在closeedge
	int i, j, k, w;
	for(i=0;i<G.vertexNum;i++)
		if (i != u)
		{//初始化辅助数组
			closeedge[i].adjvertex = u;
			closeedge[i].lowcost = G.arcs[u][i];
		}
	closeedge[u].lowcost = 0;
	for (i = 0; i < G.vertexNum-1; i++)
	{
		w = INFINITY;
		for(j=0;j<G.vertexNum;j++)  //在辅助数组中选择权最小的顶点
			if (closeedge[j].lowcost != 0 && closeedge[j].lowcost < w)
			{
				w = closeedge[j].lowcost;
				k = j;
			}//求出了生成树的下一个结点
		closeedge[k].lowcost = 0;//第k个结点接入生成树

		for(j=0;j<G.vertexNum;j++)//更新辅助数组
			if (G.arcs[k][j] < closeedge[j].lowcost)
			{
				closeedge[j].adjvertex = k;
				closeedge[j].lowcost = G.arcs[k][j];
			}
		//打印生成树
		for (i = 0; i < G.vertexNum; i++)
		{
			if (i != u)
				printf(" %d -> %d, %d", i, closeedge[i].adjvertex,G.arcs[i][closeedge[i].adjvertex]);
		}
	}
}

//===============krusal算法生成最小生成树

#define MaxVertexNum 30 //最大的顶点数为30
#define MaxEdge 100	
#define WeightType int

typedef struct ENode
{
	int vertex1, vertex2;
	WeightType weight;
}ENode;

typedef struct {
	int vertexNum, edgeNum;	//顶点个数，边的个数
	VertexType vertexs[MaxVertexNum];		//顶点信息
	ENode edges[MaxVertexNum];		//边的信息
}ELGraph;

void sort(ENode edge[])
{
	//将G.edges大小排序
}

void kruskal(ELGraph G, ENode TE[])
{
	//使用krusal算法构造图的最小生成树，用TE[]存放
	int i, j, k;
	int f[MaxVertexNum];
	for (i = 0; i < G.vertexNum; i++) f[i] = i;//初始化为f数组，每个顶点的连通序号均为自己的坐标
	sort(G.edges);//将边集排序
	j = 0; k = 0;
	int s1, s2;
	while (k < G.edgeNum - 1)//选取n-1条边
	{
		s1 = f[G.edges[j].vertex1];
		s2 = f[G.edges[j].vertex2];		//选取边集中的两个结点
		if (s1 != s2)
		{
			TE[k].vertex1 = G.edges[j].vertex1;
			TE[k].vertex2 = G.edges[j].vertex2;
			TE[k].weight = G.edges[j].weight;
			k++;
			for (i = 0; i < G.vertexNum; i++)
				if (f[i] == s2)f[i] = s1;    //修改连通的编号
		}
		j++;
	}

}

/*=================================最短路径==================================*/
//从一个源点到其他结点的最短路径
//迪杰斯特拉
//初始状态设计集合S中只包含源点V0，之后不断的从顶点集合T中选取到V0路径最短的点u加入S
//每次加入后都要更新T中各顶点的最小路径值<--原来的最短路径长度与顶点u的最短路径长度加上u到该顶点的路径长度，中的最小值
//不断重复，知道T为空

#define INFINITY 30000//定义权的最大值
#define MaxVertexNum 30   //假设有向网顶点的数最大为30
#define true 1
#define false 0

void ShorttestPath_DIJ(MGragh G, int v0, int p[], int D[])
{
	//Dijkstra 算法求有向网G的v0结点到其余结点的最短路径
	//入口参数：有向网G 源点v0 P[v]表示v的前驱结点 D[v]表示v0到顶点v的最短带权路径长度
	//final[v]为true则表明已经从v0到v的最短路径
	int i, j, w, v;
	int min;
	int final[MaxVertexNum];   
	//声明辅助

	for(v=0;v<=G.vertexNum-1;v++)//初始化辅助数组
	{
		final[v] = false;	//初始化S集合判断数组
		D[v] = G.arcs[v0][v];	//初始化最短路径辅助数组
		p[v] = -1;//初始化为-1，表示无前驱
		if (D[v] < INFINITY)
			p[v] = v0;//若结点v0->v0成立则前驱改为v0结点
	}//初始化
	D[v0] = 0; final[v0] = true;//初始u时候，v0属于S集合

	/*开始主循环 ，每次求得v0到某个顶点v的最小路径，并加入到S集合*/
	for (i = 1; i < G.vertexNum; i++)
	{
		v = -1;
		min = INFINITY;
		for(w=0;w<=G.vertexNum-1;w++)//寻找距离v0最近的结点
			if ((!final[w]) && (D[w] < min))
			{
				v = w;
				min = D[w];
			}
		if (v == -1) break;//表明所有与v0有通路的结点均已经找到最短路径，退出循环
		final[w] = true;//将结点加入S集合
		//更新最短路径
		for(w=0;w<G.vertexNum;w++)
			if (!final[w] && (min + G.arcs[v][w] < D[w]))
			{
				D[w] = min + G.arcs[v][w];
				p[w] = w;//修改前驱
			}
	}
}

void Print_ShorttestPat(MGragh G, int v0, int p[], int D[])
{
	//入口参数：有向网G 源点v0 P[v]表示v的前驱结点 D[v]表示v0到顶点v的最短带权路径长度
	//final[v]为true则表明已经从v0到v的最短路径
	int v, i, j;
	printf("Theshortest path from Vertex %d to the other Vertex:\n", v0);
	for (v = 0; v < G.vertexNum; v++)
	{
		if (p[v] == -1)continue;//表明顶点v0到v没有通路
		printf("%-4d", D[v]);
		printf("%d<-", v);
		i = v;
		while (p[i] != -1)
		{
			printf("%d<-", p[i]);
			i = p[i];
		}
		printf("\n");
	}
}
//每一对顶点之间的最短路径
//第一种利用上面的算法使得v0遍历T集合从而求得最短路径

void ShorttestPath_Floyd(MGragh G, int p[][MaxVertexNum], int D[][MaxVertexNum])
{
	//入口参数:有向网G, 各对顶点v和w之间的最短路径p[v][w]   带权长度D[v][w]
	int v, w, u;
	for(v=0;v<G.vertexNum;v++)
		for (w = 0; w < G.vertexNum; w++)
		{
			D[v][w] = G.arcs[v][w];
			p[v][w] = v;
			if (D[v][w] == INFINITY)//没有直接路径
				p[v][w] = -1;
		}//初始化 D p
	for(u=0;u<G.vertexNum;u++)
		for (v = 0; v < G.vertexNum; v++)
			for (w = 0; w < G.vertexNum; w++)
				if (D[v][u] + D[u][w] < D[v][w])//从v到u到w的一条路径最短
				{
					D[v][w] = D[v][u] + D[u][w];
					p[v][w] = u;
				}
}

/*========================AVO--拓扑排序算法====================*/
//定义创建函数 
//与上述的相似

//求各个顶点的入度
void FindInDegree(ALGraph_Avo* G)
{
	//入口参数邻接表方式存储的图结构
	int i;
	EdgeNode_Avo* p;
	for (i = 0; i < G->vertexNum; i++)
		G->adjlist[i].indegree = 0;//初始化入度
	for (i = 0; i < G->vertexNum; i++)
	{
		for (p = G->adjlist[i].firstedge; p; p = p->next)
		{
			G->adjlist[p->adjvertex].indegree++;//遍历到结点->使其入度加1
		}
	}//
}//FindInDegree

void Top_Start(ALGraph_Avo G)
{
	//对邻接链表存储的图，输出其拓扑序列
	//入口参数：带有入度元素的邻接链表格式储存的图结构
	int i, j, k, count = 0;
	int top;//栈顶指针初始化
	EdgeNode_Avo* p;
	FindInDegree(&G);//求各个顶点的入度
	for (i = 0; i < G.vertexNum; i++)//依次将入度为零的顶点压入链式栈
	{
		if (G.adjlist[i].indegree == 0)
		{
			G.adjlist[i].indegree = top;
			top = i;
		}
	}
	while (top != -1)//当栈非空的时候
	{
		j = top;
		top = G.adjlist[top].indegree;//从栈中退出一个顶点并输出
		printf("%3d", G.adjlist[j].vertex);
		count++;//排序到的顶点数
		for (p = G.adjlist[j].firstedge; p; p = p->next)
		{
			k = p->adjvertex;
			G.adjlist[k].indegree--;		//当前输入的顶点入度减一
			if (G.adjlist[k].indegree == 0)
			{
				G.adjlist[k].indegree = top;
				top = k;
			}
		}
	}
	if (count < G.vertexNum) printf("The nework has a cycle\n");
}

/*===================AVE--求各个顶点事件的最早发生时间=======================*/
//求各个顶点的入度
void FindInDegree(ALGraph_Ave* G)
{
	//入口参数邻接表方式存储的图结构
	int i;
	EdgeNode_Ave* p;
	for (i = 0; i < G->vertexNum; i++)
		G->adjlist[i].indegree = 0;//初始化入度
	for (i = 0; i < G->vertexNum; i++)
	{
		for (p = G->adjlist[i].firstedge; p; p = p->next)
		{
			G->adjlist[p->adjvertex].indegree++;//遍历到结点->使其入度加1
		}
	}//
}//FindInDegree
int TopOreder(ALGraph_Ave G, int tpord[], int ve[])
{
	//有向图G,采用邻接表存储结构，求各个顶点事件的最早发生时间
	//若G无回路，用数组tpord[]保存G的一个拓扑序列，返回1，否则返回0
	//入口参数：Ave->邻接表示的图结构   tpord[]G的拓扑序列  ve[]保存各个顶点的最早发生时间<-初始为各个边的权值
	int i, j, k,top, count = 0;
	top = -1;//栈顶指针初始化
	EdgeNode_Ave* p;
	FindInDegree(&G);//求顶点入度
	for (i = 0; i < G.vertexNum; i++)//将入度为0的顶点入栈
	{
		if (G.adjlist[i].indegree == 0)
		{
			G.adjlist[i].indegree = top;
			top = i;
		} 
	}
	while (top != -1)
	{
		j = top;
		top = G.adjlist[top].indegree;//从栈中退出一个元素并输出
		tpord[count++] = G.adjlist[j].vertex;
		for (p = G.adjlist[j].firstedge; p; p = p->next)
		{
			k = p->adjvertex;
			G.adjlist[k].indegree--;
			if (G.adjlist[k].indegree == 0)
			{
				G.adjlist[k].indegree = top;
				top = k;//修改栈顶元素
			}
			if (ve[j] + p->info > ve[k])
				ve[k] = ve[j] + p->info;//p->info为边的持续时间
		}
	}
	if (count < G.vertexNum) return 0;
	else return 1;
}//TopOreder

//输出G的各项关键活动
int Criticalpath(ALGraph_Ave G)
{
	//入口参数：关于有有向图设计的邻接表  成功返回1，否则返回0
	int i, j, k, e, l, ve[MaxVertexNum], v1[MaxVertexNum], order[MaxVertexNum];//辅助变量  order为Ave=图的一个拓扑序列 
	EdgeNode_Ave* p;
	int count = G.vertexNum;
	if (TopOreder(G, order, ve) == 0) return 0;//该有向图有回路返回0
	for (i = 0; i < G.vertexNum; i++) v1[i] = ve[G.vertexNum - 1]; //初始化顶点事件的最迟发生时间
	for(i=count;i>0;i--)//按照拓扑序列求各个顶点的最迟发生时间
	{
		j = order[i - 1];
		for (p = G.adjlist[j].firstedge; p; p = p->next)
		{
			k = p->adjvertex;
			if (v1[k] - p->info < v1[j]) v1[j] = v1[k] - p->info;
		}
	}
	for(j=0;j<G.vertexNum;j++)//求 e,l 关键活动
		for (p = G.adjlist[j].firstedge; p; p = p->next)
		{
			k = p->adjvertex;
			e = ve[j];
			l = v1[k] - p->info;
			if (l == e)
				printf("%d->%d", j, k);//输出关键活动
		}
	return 1;
}