图的所有数据结构函数

@hey_超级巨星
图的所有数据结构
```cpp
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef int Elemtype;
#define ok 1
#define ERROR 0
#define MAXSIZE 10
typedef struct GraphNode
{
	Elemtype vertex[MAXSIZE];
	Elemtype arc[MAXSIZE][MAXSIZE];//不带权
	int vernum;
	int arcnum;
	int matrix[MAXSIZE][MAXSIZE];//带权的边
}GraphNode,*Graph;
int IsRead[MAXSIZE];
//深度优先搜索
void DFS(Graph G,int pos)
{
	if (IsRead[pos] == 0)
	{
		IsRead[pos] = 1;
		printf("%dt",G->vertex[pos]);
	}
	for (int i = 0; i < G->vernum; i++)
	{
		if (IsRead[i] == 0 && G->arc[pos][i] != INFINITY)
		{
			DFS(G,i);
		}
	}
}
typedef struct
{
	Elemtype* base;
	int front;
	int rear;
	int maxsize;
}*Queue;
int InitQueue(Queue Q)
{
	Q->base = (Elemtype*)malloc(sizeof(Elemtype)*MAXSIZE);
	if (!Q->base)
		return ERROR;
	Q->front = Q->rear = 0;
	Q->maxsize = MAXSIZE;
	return ok;
}
void EnQueue(Queue Q,int pos)
{
	if (IsFull(Q))
		printf("full");
	Q->base[Q->rear] = pos;
	Q->rear = (Q->rear + 1) % Q->maxsize;
}
int DeQueue(Queue Q)
{
	if (IsEmpty(Q))
		printf("空队列");
	Q->front= (Q->front + 1) % Q->maxsize;
}
bool IsFull(Queue Q)
{
	if (Q->rear + 1 == Q->front)
		return 1;
	else return 0;
}
bool IsEmpty(Queue Q)
{
	if (Q->front == Q->rear)
		return 1;
	else return 0;
}
//广度优先搜索
void BFS(Graph G,int pos)
{
	Queue Q;
	InitQueue(Q);
	int temp;
	if (IsRead[pos] == 0)
	{
		IsRead[pos] = 1;
		printf("%dt",G->vertex[pos]);
	}
	EnQueue(Q,pos);
	while (!IsEmpty(Q))
	{
		temp=DeQueue(Q);
		for (int i=0;i<G->vernum;i++)
		{
			if (IsRead[temp] == 0 && G->arc[temp][i] != INFINITY)
			{
				printf("%dt",G->vertex[i]);
				IsRead[i] = 1;
				EnQueue(Q,i);
			}
		}
	}
}
//最小生成树
//prim算法
int weight[];
void Prim(Graph G, int start,int prim[])
{
	int j, i;
	prim[0] = G->vertex[start];
	int index = 1;
	for (i=0;i<G->vernum;i++)
	{
		weight[i] = G->matrix[start][i];
	}
	weight[start] = 0;
	int k;
	for (j=0;j<G->vernum;j++)
	{
		if (j == start)
			continue;
		int min = INFINITY;
		for (i = 0; i < G->vernum; i++)
		{
			if (weight[i] < min&&weight[i]!=0)
			{
				min = weight[i];
				k = i;
			}
		}
		prim[index++] = G->vertex[k];
		weight[k]=0;
		//更新权值
		for (i=0;i<G->vernum;i++)
		{
			if (weight[i]!=0&&G->arc[k][i]<weight[i])
			{
				weight[i] = G->arc[k][i];
			}
		}	
	}
}
//kruskal算法
typedef struct gEdge
{
	int beign;
	int end;
	int weight;
}gEdge;
gEdge edge[];
int getEnd(int verend[],int i)
{
	while (verend[i] != 0)
	{
		i = verend[i];
	}
	return i;
}
int get_position(Graph G,int point )
{
	return G->vertex[point];
}
gEdge* get_edge(Graph G)
{
	gEdge edge[MAXSIZE];
	int i;
	for (i=0;i<G->vernum;i++)
	{
		for (int j = 0; j < G->vernum; j++)
		{
			edge[i].weight=G->matrix[i][j];
			edge[i].beign = i;
			edge[i].end = j;
		}
	}
	return edge;
}
void get_sort(gEdge *edge)
{
	int i,j,temp;
	int k;
	k = edge[0].weight;
	int p;
	for (i=0;i<MAXSIZE;i++)
	{
		for (j = 1; j < MAXSIZE; j++)
		{
			if (edge[i].weight <= edge[j].weight)
			{
				continue;
			}
			else
			{
				temp = edge[i].weight;
				edge[i].weight = edge[j].weight;
				edge[j].weight = temp;
			}
		}
	}
}
void Kruskal(Graph G)
{
	int index = 0;
	int i,m,n,p1,p2;
	int verend[MAXSIZE] = { 0 };
	gEdge rets[MAXSIZE-1];//储存结果数组
	gEdge *edge;
	//初始化
	edge = get_edge(G);
	get_sort(edge);
	for (i=1;i<G->arcnum-1;i++)
	{
		p1 = get_position(G,edge[i].beign);
		p2 = get_position(G,edge[i].end);
		m = getEnd(verend, p1);
		n = getEnd(verend, p2);
		if (m != n)
		{
			verend[m] = n;
			rets[index++] = edge[i];
		}
	}
}
//最短路径
void dijkstra(Graph G, int vs, int prev[], int dist[])
{
	int i, j,k;
	int tmp;
	int min;
	int flag[MAXSIZE];
	//初始化
	for (i = 0; i < G->vernum; i++)
	{
		flag[i] = 0;
		dist[i] = G->matrix[vs][i];
		prev[i] = 0;
	}
	flag[vs] = 1;
	dist[vs] = 0;
	//开始遍历
	for (i=0;i<G->vernum;i++)
	{
		min = INFINITY;
		for (j=0;j<G->vernum;j++)
		{
			if (flag[j]==0&&dist[j] < min)
			{
				min = dist[j];
				k = j;
			}
			flag[k] = 1;
		}
		//更新
		for (j=0;j<G->vernum;j++)
		{
			tmp = (G->matrix[k][j]==INFINITY?INFINITY:(min+G->matrix[k][j]));
			if (flag[j]==0&&tmp<dist[j])
			{
				dist[j] = tmp;
				prev[j]=k;
			}
		}
	}
}
//Floyd算法
void Floyd(Graph G)
{
	int i, j, k;
	int tmp;
	int dist[MAXSIZE][MAXSIZE];
	dist[0][0] = G->matrix[0][0];
	for (k = 0; k < G->vernum; k++)
	{
		for (i = 0; i < G->vernum; i++)
		{
			for (j = 0; j < G->vernum; j++)
			{
				tmp = (dist[i][k]==INFINITY|| dist[k][j]==INFINITY?INFINITY:(dist[i][k]+ dist[k][j]));
				if (dist[i][j]>tmp)
				{
					dist[i][j] = tmp;
				}
			}
		}
	}
}
//拓扑排序
//一个一个输出入度为0的点
int ins[MAXSIZE];//save the in_edge of every vertex
struct Node //出边队列
{ 
	int vex;
	struct node* next_edge;
}Node;
void Dag(Graph G)
{
	Node node;
	Queue Q;
	int i;
	//将所有入度为0的点入队列
	for (i = 0; i < G->vernum; i++)
	{
		if (ins[i] == 0);
		InitQueue(Q);
		EnQueue(Q, i);
	}
	int j;
	int index;
	int  top[MAXSIZE];//to save the Order
	while (!IsEmpty(Q))
	{
		j = DeQueue(Q);
		top[index++] = G->vertex[j];
		node = G->vex[j].first_edge;//node 获取当前点的出边对列
		while (node!=NULL)//更新所有以当前输出顶点为入点的关联边
		{
			//ba guanlian de dian de ru du jianyi
			ins[node->vex]--;
			if (ins[node->vex] == 0)
				EnQueue(Q,node->vex);
			node = node->next_edge;
		}
	}
}

最后

以上就是美好鸵鸟为你收集整理的图的所有数据结构函数的全部内容，希望文章能够帮你解决图的所有数据结构函数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。