数据结构学习笔记 --- 图（数组表示法）

VB 前端之家
前端之家收集整理的这篇文章主要介绍了数据结构学习笔记 --- 图（数组表示法），前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

1. 图的数组表示法

2. 代码

#include "ds.h"

// 图的数组(邻接矩阵)存储表示

#define 	INFINITY		INT_MAX		// 用整型最大值代替∞
#define 	MAX_VERTEX_NUM	26			// 最大顶点个数
#define 	MAX_NAME 		5 			// 顶点字符串的最大长度+1
#define 	MAX_INFO 		20 			// 相关信息字符串的最大长度+1
typedef 	int 			VRType; 	// 顶点关系类型
typedef 	char 			InfoType; 	// 相关信息类型
typedef 	char 			VertexType[MAX_NAME]; // 顶点类型

enum		GraphKind{DG,DN,UDG,UDN};// {有向图,有向网,无向图,无向网}

typedef struct
{
	VRType 		adj;	// 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；对带权图，则为权值
	InfoType	*info;	// 该弧相关信息的指针(可无)
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];	// 二维数组

struct MGraph
{
	VertexType 	vexs[MAX_VERTEX_NUM];		// 顶点向量
	AdjMatrix	arcs;						// 邻接矩阵
	int			vexnum,arcnum;				// 图的当前顶点数和弧数
	GraphKind	kind;						// 图的种类标志
};

Boolean visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量)
void(*VisitFunc)(VertexType); // 函数变量
typedef VRType QElemType; // 队列元素类型
//队列的链式存储结构
typedef struct QNode{
	QElemType 		data;
	struct QNode 	*next;
}*QueuePtr;

typedef struct LinkQueue{
	QueuePtr 	front,rear;
}LinkQueue;

// 带头结点的单链队列
void InitQueue(LinkQueue &Q);
void DestroyQueue(LinkQueue &Q);
void ClearQueue(LinkQueue &Q);
Status QueueEmpty(LinkQueue Q);
int QueueLength(LinkQueue Q);
Status GetHead(LinkQueue Q,QElemType &e);
void EnQueue(LinkQueue &Q,QElemType e);
Status DeQueue(LinkQueue &Q,QElemType &e);

// 带头结点的单链队列
void InitQueue(LinkQueue &Q)
{
	Q.front = (QueuePtr)malloc(sizeof(QNode));
	if (!Q.front) exit(OVERFLOW);
	
	Q.front->next = NULL;
	Q.rear = Q.front;
		
}
void DestroyQueue(LinkQueue &Q)
{
	QueuePtr q,p = Q.front;
	
	while (p)
	{
		q = p->next;
		free(p);
		p = q;
	}
	
	Q.front = Q.rear = NULL;
}
void ClearQueue(LinkQueue &Q)
{
	QueuePtr q,p = Q.front->next;
	
	while (p)
	{
		q = p->next;
		free(p);
		p = q;
	}
	Q.front->next = NULL;
	Q.rear = Q.front;
}
Status QueueEmpty(LinkQueue Q)
{
	if (Q.front == Q.rear)
		return TRUE;
	else
		return FALSE;
}
int QueueLength(LinkQueue Q)
{
	int i = 0;
	QueuePtr p = Q.front->next;
	
	while (p)
	{
		i++;
		p = p->next;
	}
	
	return i;
}
Status GetHead(LinkQueue Q,QElemType &e)
{
	if (Q.front->next)
	{
		memcpy(&e,&(Q.front->next->data),sizeof(QElemType));
		return OK;
	}
	else
	{
		return FALSE;
	}
}
void EnQueue(LinkQueue &Q,QElemType e)
{
	QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
	if (!p) exit(OVERFLOW);
	
	p->next = NULL;
	memcpy(&(p->data),&e,sizeof(QElemType));
	Q.rear->next = p;
	Q.rear = p;
}
Status DeQueue(LinkQueue &Q,QElemType &e)
{
	QueuePtr p = Q.front,q;
	if (Q.front == Q.rear)
		return FALSE;
	
	q = p->next;
	memcpy(&e,&(q->data),sizeof(QElemType));
	p->next = q->next;
	if (Q.rear == q)
		Q.rear = Q.front;
	free(q);
	
	return OK;
}
// 图的数组(邻接矩阵)存储(存储结构由c7-1.h定义)的基本操作(21个)，包括算法7.1、
// 7.2、算法7.4～7.6

// 初始条件：图G存在，u和G中顶点有相同特征
// 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1
int LocateVex(MGraph G,VertexType u)
{
	int i;
	for (i = 0; i < G.vexnum; ++i)
	{
		if (strcmp(u,G.vexs[i]) == 0)
			return i;
	}
	return -1;
}

// 采用数组(邻接矩阵)表示法，由文件构造没有相关信息的无向图G
void CreateFUDG(MGraph &G)
{
	int 		i,j,k;
	char		filename[13];
	VertexType	va,vb;
	FILE		*graphlist;
	
	printf("请输入数据文件名(f7-1.txt或f7-2.txt)：");
   	scanf("%s",filename);
   	
   	graphlist = fopen(filename,"r");		// 打开数据文件，并以graphlist表示
   	fscanf(graphlist,"%d",&G.vexnum);
   	fscanf(graphlist,&G.arcnum);
   	
   	for (i = 0; i < G.vexnum; ++i)
   		fscanf(graphlist,"%s",G.vexs[i]);	// 构造顶点向量
   		
   	for (i = 0; i < G.vexnum; ++i)			// 初始化邻接矩阵
   		for (j = 0; j < G.vexnum; ++j)
   		{
   			G.arcs[i][j].adj  = 0;		// 图
   			G.arcs[i][j].info = NULL;	// 没有相关信息
   		}
   	
   	for (k = 0; k < G.arcnum; ++k)
   	{
   		fscanf(graphlist,"%s%s",va,vb);
   		i = LocateVex(G,va);
   		j = LocateVex(G,vb);
   		G.arcs[i][j].adj = G.arcs[j][i].adj = 1;	// 无向图
   	}
   	
   	fclose(graphlist);		// 关闭数据文件
   	G.kind = UDG;
}

// 采用数组(邻接矩阵)表示法，由文件构造没有相关信息的无向网G
void CreateFUDN(MGraph &G)
{
	int 		i,k,w;
	char 		filename[13];
	VertexType	va,vb;
	FILE		*graphlist;
	
	printf("请输入数据文件名：");
	scanf("%s",filename);
	
	graphlist = fopen(filename,"r");
 	fscanf(graphlist,G.vexs[i]);	// 构造顶点向量
   	
   	for (i = 0; i < G.vexnum; ++i)
   		for (j = 0; j < G.vexnum; ++j)
   		{
   			G.arcs[i][j].adj  = INFINITY;	// 网
   			G.arcs[i][j].info = NULL;
   		}
   	
   	for (k = 0; k < G.arcnum; ++k)
   	{
   		fscanf(graphlist,"%s%s%d",vb,&w);
   		i = LocateVex(G,vb);
   		G.arcs[i][j].adj = G.arcs[j][i].adj = w;	// 无向网
   	}
   	
   	fclose(graphlist); // 关闭数据文件
   	G.kind = UDN;
}

// 采用数组(邻接矩阵)表示法，构造有向图G
void CreateDG(MGraph &G)
{
	int 		i,l,IncInfo;
	char		s[MAX_INFO];
	VertexType	va,vb;
	
	printf("请输入有向图G的顶点数,弧数,弧是否含其它信息(是:1,否:0): ");
	scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo);
	
	printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);
	for (i = 0; i < G.vexnum; ++i)	// 构造顶点向量
		scanf("%s",G.vexs[i]);
	for (i = 0; i < G.vexnum; ++i)	// 初始化邻接矩阵
		for (j = 0; j < G.vexnum; ++j)
		{
			G.arcs[i][j].adj  = 0;	// 图
			G.arcs[i][j].info = NULL;
		}
	
	printf("请输入%d条弧的弧尾 弧头(以空格作为间隔): \n",G.arcnum);
	for (k = 0; k < G.arcnum; ++k)
	{
		scanf("%s%s%*c",vb);	// %*c吃掉回车符
		i = LocateVex(G,va);
		j = LocateVex(G,vb);
		G.arcs[i][j].adj = 1; 		// 有向图
		
		if (IncInfo)
		{
			printf("请输入该弧的相关信息(<%d个字符): ",MAX_INFO);
			gets(s);
			l = strlen(s);
			if (l)
			{
				G.arcs[i][j].info = (char*)malloc((l + 1)*sizeof(char)); // 有向
				strcpy(G.arcs[i][j].info,s);
			}
		}
	}
	
	G.kind = DG;
}

// 采用数组(邻接矩阵)表示法，构造有向网G
void CreateDN(MGraph &G)
{
	int 		i,w,IncInfo;
	char 		s[MAX_INFO];
	VertexType	va,vb;
	
	printf("请输入有向网G的顶点数,否:0): ");
   	scanf("%d,&IncInfo);
   	
   	printf("请输入%d个顶点的值(<%d个字符):\n",G.vexs[i]);
	for (i = 0; i < G.vexnum; ++i)	// 初始化邻接矩阵
		for (j = 0; j < G.vexnum; ++j)
		{
			G.arcs[i][j].adj  = INFINITY; // 网
			G.arcs[i][j].info = NULL;
		}
	
	printf("请输入%d条弧的弧尾 弧头 权值(以空格作为间隔): \n",G.arcnum);
	for(k = 0; k < G.arcnum; ++k)
   	{
     	scanf("%s%s%d%*c",&w);  // %*c吃掉回车符
     	i = LocateVex(G,va);
     	j = LocateVex(G,vb);
     	G.arcs[i][j].adj = w; // 有向网
     	if(IncInfo)
     	{
       		printf("请输入该弧的相关信息(<%d个字符): ",MAX_INFO);
       		gets(s);
       		w = strlen(s);
       		if(w)
       		{
         		G.arcs[i][j].info=(char*)malloc((w+1)*sizeof(char)); // 有向
         		strcpy(G.arcs[i][j].info,s);
       		}
     	}
   }
   G.kind = DN;
}

// 采用数组(邻接矩阵)表示法，构造无向图G
void CreateUDG(MGraph &G)
{ 
   	int 			i,IncInfo;
   	char 			s[MAX_INFO];
   	VertexType 		va,vb;
   	printf("请输入无向图G的顶点数,边数,边是否含其它信息(是:1,&IncInfo);
   	printf("请输入%d个顶点的值(<%d个字符):\n",MAX_NAME);
   	for(i = 0; i < G.vexnum; ++i) // 构造顶点向量
     	scanf("%s",G.vexs[i]);
   	for(i = 0; i < G.vexnum; ++i) // 初始化邻接矩阵
     	for(j = 0; j < G.vexnum; ++j)
     	{
       		G.arcs[i][j].adj  = 0; // 图
       		G.arcs[i][j].info = NULL;
     	}
   	printf("请输入%d条边的顶点1 顶点2(以空格作为间隔): \n",G.arcnum);
	for (k = 0; k < G.arcnum; ++k)
   	{
     	scanf("%s%s%*c",vb); // %*c吃掉回车符
     	i = LocateVex(G,vb);
     	G.arcs[i][j].adj = G.arcs[j][i].adj = 1; // 无向图
      	if (IncInfo)
     	{
        	printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO);
       		gets(s);
       		l = strlen(s);
       		if(l)
       		{
         		G.arcs[i][j].info=G.arcs[j][i].info = (char*)malloc((l+1)*sizeof(char));
	 			// 无向，两个指针指向同一个信息
	  			strcpy(G.arcs[i][j].info,s);
       		}
     	}
   	}
   	G.kind = UDG;
}

// 采用数组(邻接矩阵)表示法，构造无向网G。算法7.2
void CreateUDN(MGraph &G)
{
   	int 			i,vb;
   	printf("请输入无向网G的顶点数,MAX_NAME);
   	for(i=0;i<G.vexnum;++i) // 构造顶点向量
     	scanf("%s",G.vexs[i]);
   	for(i=0;i<G.vexnum;++i) // 初始化邻接矩阵
     	for(j=0;j<G.vexnum;++j)
     	{
       		G.arcs[i][j].adj=INFINITY; // 网
       		G.arcs[i][j].info=NULL;
     	}
   	printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n",G.arcnum);
   	for(k=0;k<G.arcnum;++k)
   	{
     	scanf("%s%s%d%*c",&w); // %*c吃掉回车符
     	i=LocateVex(G,va);
     	j=LocateVex(G,vb);
     	G.arcs[i][j].adj=G.arcs[j][i].adj=w; // 无向
     	if(IncInfo)
     	{
       		printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO);
       		gets(s);
       		w=strlen(s);
       		if(w)
       		{
         		G.arcs[i][j].info=G.arcs[j][i].info=(char*)malloc((w+1)*sizeof(char));
         		// 无向，两个指针指向同一个信息
         		strcpy(G.arcs[i][j].info,s);
       		}
     	}
   	}
   	G.kind = UDN;
}

// 采用数组(邻接矩阵)表示法，构造图G。算法7.1改
void CreateGraph(MGraph &G)
{ 
   	printf("请输入图G的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
   	scanf("%d",&G.kind);
   	switch(G.kind)
   	{
     	case DG: CreateDG(G); // 构造有向图
              break;
     	case DN: CreateDN(G); // 构造有向网
              break;
     	case UDG:CreateUDG(G); // 构造无向图
              break;
     	case UDN:CreateUDN(G); // 构造无向网
   	}
}

// 初始条件：图G存在。操作结果：销毁图G
void DestroyGraph(MGraph &G)
{
	int 	i,k = 0;
	if (G.kind %2)		// 网
		k = INFINITY;	// k为两顶点之间无边或弧时邻接矩阵元素的值

	for (i = 0; i < G.vexnum; ++i)	// 释放弧或边的相关信息(如果有的话)
	{
		if (G.kind < 2)	// 有向
		{
			for (j = 0; j < G.vexnum; j++)
			{
				if (G.arcs[i][j].adj != k) 	// 有弧
				{
					if (G.arcs[i][j].info)	// 有相关信息
					{
						free(G.arcs[i][j].info);
						G.arcs[i][j].info = NULL;
					}
				}
			}
		}
		else			// 无向
		{
			for (j = i+1; j < G.vexnum; j++)	// 只查上三角
			{
				if (G.arcs[i][j].adj != k) 		// 有边
				{
					if (G.arcs[i][j].info)		// 有相关信息
					{
						free(G.arcs[i][j].info);
						G.arcs[i][j].info = G.arcs[j][i].info = NULL;
					}
				}
			}
		}
	}
	
	G.vexnum = 0;	// 顶点数为0
	G.arcnum = 0;	// 边数为0
}

// 初始条件：图G存在，v是G中某个顶点的序号。操作结果：返回v的值
VertexType& GetVex(MGraph G,int v)
{
	if (v >= G.vexnum || v < 0)
		exit(ERROR);
	return G.vexs[v];
}

// 初始条件：图G存在，v是G中某个顶点。操作结果：对v赋新值value
Status PutVex(MGraph &G,VertexType v,VertexType value)
{
	int 	k;
	k = LocateVex(G,v);
	
	if (k < 0)
		return ERROR;
	strcpy(G.vexs[k],value);
	return OK;
}

// 初始条件：图G存在，v是G中某个顶点
// 操作结果：返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1
int FirstAdjVex(MGraph G,VertexType v)
{
	int 	i,j = 0,k;
	k = LocateVex(G,v);
	if (k < 0)
		return ERROR;
	if (G.kind % 2)	// 网
		j = INFINITY;
	for (i = 0; i < G.vexnum; i++)
		if (G.arcs[k][i].adj != j)
			return i;
	return -1;
}

// 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点
// 操作结果：返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1
int NextAdjVex(MGraph G,VertexType w)
{
	int 	i,k1,k2;
	k1 = LocateVex(G,v);	// k1为顶点v在图G中的序号
	k2 = LocateVex(G,w);	// k2为顶点v在图G中的序号
	if (G.kind%2) 	// 网
		j = INFINITY;
	for (i = k2+1; i < G.vexnum; i++)	
		if (G.arcs[k1][j].adj != j)
			return i;
	return -1;
}

// 初始条件：图G存在，v和图G中顶点有相同特征
// 操作结果：在图G中增添新顶点v(不增添与顶点相关的弧，留待InsertArc()去做)
void InsertVex(MGraph &G,VertexType v)
{
	int i,j = 0;
   	if(G.kind%2) // 网
     	j = INFINITY;
     
     strcpy(G.vexs[G.vexnum],v);	 // 构造新顶点向量
     for (i = 0; i <= G.vexnum; i++)
     {
     	G.arcs[G.vexnum][i].adj = G.arcs[i][G.vexnum].adj = j;
     	// 初始化新增行、新增列邻接矩阵的值(无边或弧)
     	G.arcs[G.vexnum][i].info = G.arcs[i][G.vexnum].info = NULL; // 初始化相关信息指针
     }
     G.vexnum++;
}

// 初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的弧
Status DeleteVex(MGraph &G,VertexType v)
{
 	int i,k;
   	VRType m=0;
   	if(G.kind%2) // 网
     	m = INFINITY;
   	k = LocateVex(G,v); // k为待删除顶点v的序号
   	if(k < 0) // v不是图G的顶点
     	return ERROR;
   	for(j = 0; j < G.vexnum; j++)
     	if(G.arcs[j][k].adj != m) // 有入弧或边
     	{
       		if(G.arcs[j][k].info) // 有相关信息
         	free(G.arcs[j][k].info); // 释放相关信息
       		G.arcnum--; // 修改弧数
     	}
   
   	if(G.kind < 2) // 有向
     	for(j=0;j<G.vexnum;j++)
       		if(G.arcs[k][j].adj!=m) // 有出弧
       		{
	 			if(G.arcs[k][j].info) // 有相关信息
           		free(G.arcs[k][j].info); // 释放相关信息
         		G.arcnum--; // 修改弧数
       		}
       		
   	for(j=k+1;j<G.vexnum;j++) // 序号k后面的顶点向量依次前移
     	strcpy(G.vexs[j-1],G.vexs[j]);
   	for(i=0;i<G.vexnum;i++)
     	for(j=k+1;j<G.vexnum;j++)
       		G.arcs[i][j-1]=G.arcs[i][j]; // 移动待删除顶点之右的矩阵元素
   	for(i=0;i<G.vexnum;i++)
     	for(j=k+1;j<G.vexnum;j++)
       	G.arcs[j-1][i]=G.arcs[j][i]; // 移动待删除顶点之下的矩阵元素
   	G.vexnum--; // 更新图的顶点数
   	return OK; 
}

// 初始条件：图G存在，v和w是G中两个顶点
// 操作结果：在G中增添弧<v,w>，若G是无向的，则还增添对称弧<w,v>
Status InsertArc(MGraph &G,VertexType w)
{  
	int i,v1,w1;
   	char s[MAX_INFO];
   	v1=LocateVex(G,v); // 尾
   	w1=LocateVex(G,w); // 头
   	if(v1<0||w1<0)
     	return ERROR;
   	G.arcnum++; // 弧或边数加1
   	if(G.kind%2) // 网
   	{
     	printf("请输入此弧或边的权值: ");
     	scanf("%d",&G.arcs[v1][w1].adj);
   	}
   	else // 图
     	G.arcs[v1][w1].adj=1;
   	printf("是否有该弧或边的相关信息(0:无 1:有): ");
   	scanf("%d%*c",&i);
   	if(i)
   	{
     	printf("请输入该弧或边的相关信息(<%d个字符)：",MAX_INFO);
     	gets(s);
     	l=strlen(s);
     	if(l)
     	{
       		G.arcs[v1][w1].info=(char*)malloc((l+1)*sizeof(char));
       		strcpy(G.arcs[v1][w1].info,s);
     	}
   	}
   	if(G.kind>1) // 无向
   	{
     	G.arcs[w1][v1].adj=G.arcs[v1][w1].adj;
     	G.arcs[w1][v1].info=G.arcs[v1][w1].info; // 指向同一个相关信息
   	}
   	return OK;
}

// 初始条件：图G存在，v和w是G中两个顶点
// 操作结果：在G中删除弧<v,w>，若G是无向的，则还删除对称弧<w,v>
Status DeleteArc(MGraph &G,VertexType w)
{ 
	int v1,w1,j=0;
   	if(G.kind%2) 	// 网
     	j=INFINITY;
   	v1=LocateVex(G,w); // 头
   	if(v1<0||w1<0) // v1、w1的值不合法
     	return ERROR;
   	G.arcs[v1][w1].adj=j;
   	if(G.arcs[v1][w1].info) // 有其它信息
   	{
     	free(G.arcs[v1][w1].info);
     	G.arcs[v1][w1].info=NULL;
   	}
   	if(G.kind>=2) // 无向，删除对称弧<w,v>
   	{
     	G.arcs[w1][v1].adj=j;
     	G.arcs[w1][v1].info=NULL;
   	}
   	G.arcnum--; // 弧数-1
   	return OK;
}

// 从第v个顶点出发递归地深度优先遍历图G。算法7.5
void DFS(MGraph G,int v)
{
   int w;
   visited[v] = TRUE;    // 设置访问标志为TRUE(已访问)
   VisitFunc(G.vexs[v]); // 访问第v个顶点
   for(w = FirstAdjVex(G,G.vexs[v]); w >= 0; w = NextAdjVex(G,G.vexs[v],G.vexs[w]))
     	if(!visited[w])
       		DFS(G,w); 	 // 对v的尚未访问的序号为w的邻接顶点递归调用DFS
}

// 初始条件：图G存在，Visit是顶点的应用函数。算法7.4
// 操作结果：从第1个顶点起，深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次
void DFSTraverse(MGraph G,void(*Visit)(VertexType))
{ 
   	int v;
   	VisitFunc=Visit; // 使用全局变量VisitFunc，使DFS不必设函数指针参数
   	for(v=0;v<G.vexnum;v++)
     	visited[v]=FALSE; // 访问标志数组初始化(未被访问)
   	for(v=0;v<G.vexnum;v++)
     	if(!visited[v])
       		DFS(G,v); // 对尚未访问的顶点v调用DFS
   	printf("\n");
}

// typedef VRType QElemType; // 队列元素类型

// 初始条件：图G存在，Visit是顶点的应用函数。算法7.6
// 操作结果：从第1个顶点起，按广度优先非递归遍历图G,并对每个顶点调用函数Visit一次且仅一次
void BFSTraverse(MGraph G,void(*Visit)(VertexType))
{ 
    int v,u,w;
   	LinkQueue Q; // 使用辅助队列Q和访问标志数组visited
   	for(v=0;v<G.vexnum;v++)
     	visited[v]=FALSE; // 置初值
   	InitQueue(Q); // 置空的辅助队列Q
   	for(v=0;v<G.vexnum;v++)
     	if(!visited[v]) // v尚未访问
     	{
       		visited[v]=TRUE; // 设置访问标志为TRUE(已访问)
       		Visit(G.vexs[v]);
       		EnQueue(Q,v); // v入队列
       		while(!QueueEmpty(Q)) // 队列不空
       		{
	 			DeQueue(Q,u); // 队头元素出队并置为u
	 			for(w = FirstAdjVex(G,G.vexs[u]); w >= 0; w=NextAdjVex(G,G.vexs[u],G.vexs[w]))
	   			if(!visited[w]) // w为u的尚未访问的邻接顶点的序号
           		{
             		visited[w]=TRUE;
             		Visit(G.vexs[w]);
             		EnQueue(Q,w);
           		}
       		}
     	}
   printf("\n");
}

// 输出邻接矩阵存储表示的图G
void Display(MGraph G)
{ 
   	int 	i,j;
   	char s[7];
   	switch(G.kind)
   	{
     case DG: strcpy(s,"有向图");
              break;
     case DN: strcpy(s,"有向网");
              break;
     case UDG:strcpy(s,"无向图");
              break;
     case UDN:strcpy(s,"无向网");
   	}
   	printf("%d个顶点%d条边或弧的%s。顶点依次是: ",G.arcnum,s);
   	for(i=0;i<G.vexnum;++i) // 输出G.vexs
     	printf("%s ",G.vexs[i]);
   	printf("\nG.arcs.adj:\n"); // 输出G.arcs.adj
   	for(i=0;i<G.vexnum;i++)
   	{
     	for(j=0;j<G.vexnum;j++)
       		printf("%11d",G.arcs[i][j].adj);
     	printf("\n");
   	}
   	printf("G.arcs.info:\n"); // 输出G.arcs.info
   	printf("顶点1(弧尾) 顶点2(弧头) 该边或弧的信息：\n");
   	for(i=0;i<G.vexnum;i++)
     	if(G.kind<2) // 有向
     	{
       		for(j=0;j<G.vexnum;j++)
         	if(G.arcs[i][j].info)
           	printf("%5s %11s     %s\n",G.vexs[i],G.vexs[j],G.arcs[i][j].info);
     	} // 加括号为避免if-else对配错
     	else // 无向,输出上三角
       	for(j=i+1;j<G.vexnum;j++)
         	if(G.arcs[i][j].info)
           		printf("%5s %11s     %s\n",G.arcs[i][j].info);
}

void visit(VertexType i)
{
   	printf("%s ",i);
}

int main()
{
   int i,n;
   MGraph g;
   VertexType v1,v2;
   printf("请顺序选择有向图,无向网\n");
   for(i=0;i<4;i++) // 验证4种情况
   {
     CreateGraph(g); // 构造图g
     Display(g); // 输出图g
     printf("插入新顶点，请输入顶点的值: ");
     scanf("%s",v1);
     InsertVex(g,v1);
     printf("插入与新顶点有关的弧或边，请输入弧或边数: ");
     scanf("%d",&n);
     for(k=0;k<n;k++)
     {
       printf("请输入另一顶点的值: ");
       scanf("%s",v2);
       if(g.kind<=1) // 有向
       {
         printf("对于有向图或网，请输入另一顶点的方向(0:弧头 1:弧尾): ");
         scanf("%d",&j);
         if(j) // v2是弧尾
           InsertArc(g,v2,v1);
         else // v2是弧头
           InsertArc(g,v2);
       }
       else // 无向
         InsertArc(g,v2);
     }
     Display(g); // 输出图g
     printf("删除顶点及相关的弧或边，请输入顶点的值: ");
     scanf("%s",v1);
     DeleteVex(g,v1);
     Display(g); // 输出图g
   }
   DestroyGraph(g); // 销毁图g
}

猜你在找的VB相关文章

VB Format函数
Format[$] ( expr [ , fmt ] ) format 返回变体型 format$ 强制返回为文本 --------------...
vb6/ASP FORMAT MM/DD/YYYY
VB6或者ASP 格式化时间为 MM/dd/yyyy 格式，竟然没有好的办法， Format 或者FormatDateTi...
VB.net 捕获项目全局异常
在项目中添加如下代码：新建窗口来显示异常信息。 Namespace My ‘全局错误处理，新的...
实现用VB.Net/(C#)开发K/3 BOS 插件的真正可行方法
转了这一篇文章，原来一直想用C#做k3的插件开发，vb没有C#用的爽呀，这篇文章写与2011年，...
vb，wps，excel 分裂
Sub 分列() ‘以空格为分隔符，连续空格只算1个。对所选中的单元格进行处理 Dim m...
VB.NET MYSQL DataGridView 增删改查（INSERT,SELECT,UPDATE,DELETE）
  Imports MySql.Data.MySqlClient Public Class Form1 ‘ GLOBAL DECLARATIONS ...
VB.NET 使用ADODB連接資料庫滙出到EXCEL
‘導入命名空間 Imports ADODB Imports Microsoft.Office.Interop   Private Sub A1() Di...
vb.net 多线程運用 ping
Imports System.IO Imports System.Threading Imports System.Diagnostics Public Class F...
VB等待进程结束
VB运行EXE程序，并等待其运行结束 参考：https://blog.csdn.net/useway/article/details/5...
vb中去掉string数组的一部分
今天碰到一个问题，登陆的时候，如果不需要验证手机号为空，则不去验证手机号 因为登陆的时...
PHPJavaJava SEPythonC#C&C++RubyVBasp.NetGoPerlnettyDjangoDelphiJsp.NET CoreSpringFlaskSpringbootSpringMVCLuaLaravelMybatisAspGroovyThinkPHPYiiswoole
文件时间pythonm相等性PHP Warning时间问题问题解决pcntl_signal采样点wav模块动态文本调用频率限制对外暴露多个访问请求更新数据表模型结构type()方法比较速度手写体sobel算子保存模型Image类nn.Conv2dpytorch1.0kaggleDCGAN交并比range()用法打印模型反卷积卷积