数据结构学习笔记 --- 图（邻接表）

概述1. 图（邻接表） #include "ds.h"// 图的数组(邻接矩阵)存储表示#define INFINITY INT_MAX // 用整型最大值代替∞#define MAX_VERTEX_NUM 20 // 最大顶点个数#define MAX_NAME 5 // 顶点字符串的最大长度+1#define MAX_INFO 20 // 相关信息

1.图（邻接表）

#include "ds.h"// 图的数组(邻接矩阵)存储表示#define 	INFINITY		INT_MAX		// 用整型最大值代替∞#define 	MAX_VERTEX_NUM	20			// 最大顶点个数#define 	MAX_name 		5 			// 顶点字符串的最大长度+1#define 	MAX_INFO 		20 			// 相关信息字符串的最大长度+1typedef 	int 			VRType; 	// 顶点关系类型typedef 	int 			InfoType; 	// 网的权值类型typedef 	char 			VertexType[MAX_name]; // 顶点类型为字符串enum		GraphKind{DG,DN,UDG,UDN};// {有向图,有向网,无向图,无向网}struct ElemType{	int 		adjvex; 	// 该弧所指向的顶点的位置	InfoType	*info;		// 网的权值指针};struct ArcNode{	ElemType	data;		// 除指针以外的部分都属于ElemType	ArcNode		*nextarc;	// 指向下一条弧的指针};	// 表结点typedef struct{	VertexType	data;		// 顶点信息	ArcNode		*firstarc;	// 第一个表结点的地址，指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];// 头结点struct ALGraph{	AdjList 	vertices;	int			vexnum,arcnum;	// 图的当前顶点数和弧数	int 		kind;			// 图的种类标志};Boolean visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量)voID(*VisitFunc)(VertexType); // 函数变量#define 	LNode 		ArcNode		// 加，定义单链表的结点类型是图的表结点的类型#define		next		nextarc		// 加，定义单链表结点的指针域是表结点指向下一条弧的指针域typedef 	ArcNode*	linkList;	// 加，定义指向单链表结点的指针是指向图的表结点的指针// 不带头结点的单链表基本 *** 作#define DestroyList ClearList // DestroyList()和ClearList()的 *** 作是一样的 voID InitList(linkList &L) { //  *** 作结果：构造一个空的线性表L   L=NulL; // 指针为空 } voID ClearList(linkList &L) { // 初始条件：线性表L已存在。 *** 作结果：将L重置为空表   linkList p;   while(L) // L不空   {     p=L; // p指向首元结点     L=L->next; // L指向第2个结点(新首元结点)     free(p); // 释放首元结点   } } Status listempty(linkList L) { // 初始条件：线性表L已存在。 *** 作结果：若L为空表，则返回TRUE，否则返回FALSE   if(L)     return FALSE;   else     return TRUE; } int ListLength(linkList L) { // 初始条件：线性表L已存在。 *** 作结果：返回L中数据元素个数   int i=0;   linkList p=L;   while(p) // p指向结点(没到表尾)   {     p=p->next; // p指向下一个结点     i++;   }   return i; } Status GetElem(linkList L,int i,ElemType &e) { // L为不带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR   int j=1;   linkList p=L;   if(i<1) // i值不合法     return ERROR;   while(j<i&&p) // 没到第i个元素，也没到表尾   {     j++;     p=p->next;   }   if(j==i) // 存在第i个元素   {     e=p->data;     return OK;   }   else     return ERROR; } int LocateElem(linkList L,ElemType e,Status(*compare)(ElemType,ElemType)) { // 初始条件：线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0)   //  *** 作结果：返回L中第1个与e满足关系compare()的数据元素的位序。   //           若这样的数据元素不存在，则返回值为0   int i=0;   linkList p=L;   while(p)   {     i++;     if(compare(p->data,e)) // 找到这样的数据元素       return i;     p=p->next;   }   return 0; } Status ListInsert(linkList &L,ElemType e) { // 在不带头结点的单链线性表L中第i个位置之前插入元素e   int j=1;   linkList p=L,s;   if(i<1) // i值不合法     return ERROR;   s=(linkList)malloc(sizeof(LNode)); // 生成新结点   s->data=e; // 给s的data域赋值   if(i==1) // 插在表头   {     s->next=L;     L=s; // 改变L   }   else   { // 插在表的其余处     while(p&&j<i-1) // 寻找第i-1个结点     {       p=p->next;       j++;     }     if(!p) // i大于表长+1       return ERROR;     s->next=p->next;     p->next=s;   }   return OK; } Status ListDelete(linkList &L,ElemType &e) { // 在不带头结点的单链线性表L中，删除第i个元素，并由e返回其值   int j=1;   linkList p=L,q;   if(i==1) // 删除第1个结点   {     L=p->next; // L由第2个结点开始     e=p->data;     free(p); // 删除并释放第1个结点   }   else   {     while(p->next&&j<i-1) // 寻找第i个结点，并令p指向其前趋     {       p=p->next;       j++;     }     if(!p->next||j>i-1) // 删除位置不合理       return ERROR;     q=p->next; // 删除并释放结点     p->next=q->next;     e=q->data;     free(q);   }   return OK; }  voID ListTraverse(linkList L,voID(*vi)(ElemType)) { // 初始条件：线性表L已存在。 *** 作结果：依次对L的每个数据元素调用函数vi()   linkList p=L;   while(p)   {     vi(p->data);     p=p->next;   }   printf("\n"); } linkList Point(linkList L,Status(*equal)(ElemType,ElemType),linkList &p) { // 查找表L中满足条件的结点。如找到，返回指向该结点的指针，p指向该结点的前驱(若该结点是   // 首元结点，则p=NulL)。如表L中无满足条件的结点，则返回NulL，p无定义。   // 函数equal()的两形参的关键字相等，返回OK；否则返回ERROR   int i,j;   i=LocateElem(L,e,equal);   if(i) // 找到   {     if(i==1) // 是首元结点     {       p=NulL;       return L;     }     p=L;     for(j=2;j<i;j++)       p=p->next;     return p->next;   }   return NulL; // 没找到 } Status DeleteElem(linkList &L,ElemType &e,ElemType)) { // 删除表L中满足条件的结点，并返回TRUE；如无此结点，则返回FALSE。   // 函数equal()的两形参的关键字相等，返回OK；否则返回ERROR   linkList p,q;   q=Point(L,equal,p);   if(q) // 找到此结点，且q指向该结点   {     if(p) // 该结点不是首元结点，p指向其前驱       ListDelete(p,2,e); // 将p作为头指针,删除第2个结点     else // 该结点是首元结点       ListDelete(L,1,e);     return TRUE;   }   return FALSE; } 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;}// bo7-2.cpp 图的邻接表存储(存储结构由c7-21.h定义)的基本 *** 作(15个)，包括算法7.4～7.6// 初始条件：图G存在，u和G中顶点有相同特征//  *** 作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1int LocateVex(ALGraph G,VertexType u){	int 	i;	for (i = 0; i < G.vexnum; ++i)		if (strcmp(u,G.vertices[i].data) == 0)			return i;	return -1;}// 采用邻接表存储结构，构造没有相关信息图或网G(用一个函数构造4种图)voID CreateGraph(ALGraph &G){	int 		i,j,k,w;	// w是权值	VertexType	va,vb;	ElemType	e;		printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");   	scanf("%d",&G.kind);	printf("请输入图的顶点数,边数: ");   	scanf("%d,%d",&G.vexnum,&G.arcnum);		printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_name);	for (i = 0; i < G.vexnum; ++i)			// 构造顶点向量	{		scanf("%s",G.vertices[i].data);		G.vertices[i].firstarc = NulL;		// 初始化与该顶点有关的出弧链表	}		if (G.kind % 2)	// 网		printf("请输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");	else		printf("请输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");		for (k = 0; k < G.arcnum; ++k)	// 构造相关弧链表	{		if(G.kind%2) // 网			scanf("%d%s%s",&w,va,vb);		else // 图			scanf("%s%s",vb);					i = LocateVex(G,va);	// 弧尾		j = LocateVex(G,vb);	// 弧头				e.info = NulL;			// 给待插表结点e赋值，图无权		e.adjvex = j;			// 弧头				if (G.kind % 2)			// 网		{			e.info = (int*)malloc(sizeof(int));			*(e.info) = w;		}				ListInsert(G.vertices[i].firstarc,e);		if (G.kind >= 2)	// 无向图或网，产生第2个表结点，并插在第j个元素(入弧)的表头		{			e.adjvex = i;	// e.info不变，不必再赋值			ListInsert(G.vertices[j].firstarc,e);	// 插在第j个元素的表头，在bo2-8.cpp中		}	}}// 采用邻接表存储结构，由文件构造没有相关信息图或网G(用一个函数构造4种图)voID CreateGraphF(ALGraph &G){	int 		i,vb;	ElemType	e;	char		filename[13];	file		*graphList;		printf("请输入数据文件名(f7-1.txt或f7-2.txt)：");   	scanf("%s",filename);   	printf("请输入图的类型(有向图:0,&G.kind);	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.vertices[i].data);     	G.vertices[i].firstarc=NulL; // 初始化与该顶点有关的出弧链表   	}	for(k = 0; k < G.arcnum; ++k) 	// 构造相关弧链表   	{     	if(G.kind%2) // 网       		fscanf(graphList,"%d%s%s",vb);     	else // 图       		fscanf(graphList,"%s%s",vb);     	i = LocateVex(G,va); // 弧尾     	j = LocateVex(G,vb); // 弧头     	e.info = NulL; // 给待插表结点e赋值，图无权     	e.adjvex = j; // 弧头     	if(G.kind%2) // 网     	{       		e.info=(int *)malloc(sizeof(int)); // 动态生成存放权值的空间       		*(e.info)=w;     	}     	ListInsert(G.vertices[i].firstarc,e); // 插在第i个元素(出弧)的表头，在bo2-8.cpp中     	if(G.kind>=2) // 无向图或网，产生第2个表结点，并插在第j个元素(入弧)的表头     	{       		e.adjvex=i; // e.info不变，不必再赋值       		ListInsert(G.vertices[j].firstarc,e); // 插在第j个元素的表头，在bo2-8.cpp中     	}   	}   	fclose(graphList); // 关闭数据文件}// 初始条件：图G存在。 *** 作结果：销毁图GvoID DestroyGraph(ALGraph &G){    	int i;   	ElemType e;   	for(i=0;i<G.vexnum;++i) // 对于所有顶点    {     	if(G.kind%2) // 网       		while(G.vertices[i].firstarc) // 对应的弧或边链表不空       		{	 			ListDelete(G.vertices[i].firstarc,e); // 删除链表的第1个结点，并将值赋给e	 			if(e.adjvex>i) // 顶点序号>i(保证动态生成的权值空间只释放1次)	   				free(e.info);       		}     	else // 图       		DestroyList(G.vertices[i].firstarc); // 销毁弧或边链表，在bo2-8.cpp中   	}   	G.vexnum=0; // 顶点数为0   	G.arcnum=0; // 边或弧数为0}// 初始条件：图G存在，v是G中某个顶点的序号。 *** 作结果：返回v的值VertexType& GetVex(ALGraph G,int v){    	if(v>=G.vexnum||v<0)     	exit(ERROR);   	return G.vertices[v].data;}// 初始条件：图G存在，v是G中某个顶点。 *** 作结果：对v赋新值valueStatus PutVex(ALGraph &G,VertexType v,VertexType value){    int i;   i=LocateVex(G,v);   if(i>-1) // v是G的顶点   {     strcpy(G.vertices[i].data,value);     return OK;   }   return ERROR; }// 初始条件：图G存在，v是G中某个顶点//  *** 作结果：返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1int FirstAdjVex(ALGraph G,VertexType v){	ArcNode 	*p;	int			v1;		v1 = LocateVex(G,v);	// v1为顶点v在图G中的序号	p = G.vertices[v1].firstarc;	if (p)		return p->data.adjvex;	else		return -1;} // DeleteArc()、DeleteVex()和NextAdjVex()要调用的函数Status equalvex(ElemType a,ElemType b){    	if(a.adjvex == b.adjvex)     	return OK;   	else     	return ERROR;}// 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点//  *** 作结果：返回v的(相对于w的)下一个邻接顶点的序号。若w是v的最后一个邻接点，则返回-1int NextAdjVex(ALGraph G,VertexType w){    	linkList 	p,p1; // p1在Point()中用作辅助指针，Point()在func2-1.cpp中   	ElemType	e;   	int 		v1;   	   	v1 = LocateVex(G,v);	// v1为顶点v在图G中的序号   	e.adjvex = LocateVex(G,w);	// e.adjvex为顶点w在图G中的序号   	   	p = Point(G.vertices[v1].firstarc,equalvex,p1);	// p指向顶点v的链表中邻接顶点为w的结点   	if (!p || !p->next)	// 没找到w或w是最后一个邻接点   		return -1;   	else   		return p->next->data.adjvex;}// 初始条件：图G存在，v和图中顶点有相同特征//  *** 作结果：在图G中增添新顶点v(不增添与顶点相关的弧，留待InsertArc()去做)voID InsertVex(ALGraph &G,VertexType v){	strcpy(G.vertices[G.vexnum].data,v);	// 构造新顶点向量	G.vertices[G.vexnum].firstarc = NulL;	G.vexnum++;								// 图G的顶点数加1}// 初始条件：图G存在，v是G中某个顶点。 *** 作结果：删除G中顶点v及其相关的弧Status DeleteVex(ALGraph &G,VertexType v){	int 		i,k;	ElemType	e;	linkList	p,p1;		j = LocateVex(G,v); 	// j是顶点v的序号   	if (j < 0) // v不是图G的顶点     	return ERROR;	i = ListLength(G.vertices[j].firstarc);	// 以v为出度的弧或边数，在bo2-8.cpp中		G.arcnum -= i;	// 边或弧数		if (G.kind % 2)	// 网		while (G.vertices[j].firstarc)	// 对应的弧或边链表不空		{			ListDelete(G.vertices[j].firstarc,e);	// 删除链表的第1个结点，并将值赋给e			free(e.info);		}	else		// 图		DestroyList(G.vertices[j].firstarc);	// 销毁弧或边链表		G.vexnum--;		// 顶点数减1		for (i = j; i < G.vexnum; i++)	// 顶点v后面的顶点前移		G.vertices[i] = G.vertices[i+1];	for(i=0;i<G.vexnum;i++) // 删除以v为入度的弧或边且必要时修改表结点的顶点位置值	{		e.adjvex = j;		p = Point(G.vertices[i].firstarc,p1);		if(p) // 顶点i的邻接表上有v为入度的结点     	{			if (p1)	// p1指向p所指结点的前驱				p1->next = p->next;	// 从链表中删除p所指结点			else	// p指向首元结点				G.vertices[i].firstarc = p->next;	// 头指针指向下一结点						if (G.kind < 2)	// 有向			{				G.arcnum--;			// 边或弧数-1				if (G.kind == 1)	// 有向网					free(p->data.info);	// 释放动态生成的权值空间			}			free(p);	// 释放v为入度的结点		}				for (k = j + 1; k <= G.vexnum; k++)		{			e.adjvex = k;			p = Point(G.vertices[i].firstarc,p1);			if (p)				p->data.adjvex--;		}	}		return OK;}// 初始条件：图G存在，v和w是G中两个顶点//  *** 作结果：在G中增添弧<v,w>，若G是无向的，则还增添对称弧<w,v>Status InsertArc(ALGraph &G,VertexType w){    	ElemType e;   	int i,j;   	i = LocateVex(G,v); // 弧尾或边的序号   	j = LocateVex(G,w); // 弧头或边的序号   	if(i<0||j<0)     	return ERROR;   	G.arcnum++; // 图G的弧或边的数目加1   	e.adjvex=j;   	e.info=NulL; // 初值   	if(G.kind%2) // 网   	{     	e.info=(int *)malloc(sizeof(int)); // 动态生成存放权值的空间     	printf("请输入弧(边)%s→%s的权值: ",v,w);     	scanf("%d",e.info);   	}   	ListInsert(G.vertices[i].firstarc,e); // 将e插在弧尾的表头，在bo2-8.cpp中   	if(G.kind>=2) // 无向，生成另一个表结点   	{     	e.adjvex=i; // e.info不变     	ListInsert(G.vertices[j].firstarc,e); // 将e插在弧头的表头   	}   	return OK;}// 初始条件：图G存在，v和w是G中两个顶点//  *** 作结果：在G中删除弧<v,w>，若G是无向的，则还删除对称弧<w,v>Status DeleteArc(ALGraph &G,VertexType w){ 	int i,j;   	Status k;   	ElemType e;   	i = LocateVex(G,v); // i是顶点v(弧尾)的序号   	j = LocateVex(G,w); // j是顶点w(弧头)的序号   	if(i<0||j<0||i==j)     	return ERROR;   	e.adjvex=j;   	k = DeleteElem(G.vertices[i].firstarc,equalvex); // 在func2-1.cpp中   	if(k) // 删除成功   	{     	G.arcnum--; // 弧或边数减1     	if(G.kind%2) // 网       		free(e.info);     	if(G.kind>=2) // 无向，删除对称弧<w,v>     	{       		e.adjvex=i;       		DeleteElem(G.vertices[j].firstarc,equalvex);     	}     	return OK;   	}   	else // 没找到待删除的弧     	return ERROR;}// 从第v个顶点出发递归地深度优先遍历图G。算法7.5voID DFS(ALGraph G,int v){   	int w;   	visited[v]=TRUE; // 设置访问标志为TRUE(已访问)   	VisitFunc(G.vertices[v].data); // 访问第v个顶点   	for(w=FirstAdjVex(G,G.vertices[v].data);w>=0;w=NextAdjVex(G,G.vertices[v].data,G.vertices[w].data))     	if(!visited[w])       		DFS(G,w); // 对v的尚未访问的邻接点w递归调用DFS}// 对图G作深度优先遍历。算法7.4voID DFSTraverse(ALGraph G,voID(*Visit)(char*)){    	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); // 对尚未访问的顶点调用DFS   	printf("\n");}typedef int QElemType; // 队列元素类型//按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。算法7.6voID BFSTraverse(ALGraph G,voID(*Visit)(char*)){	int			v,u,w;	linkQueue	Q;	for (v = 0; v < G.vexnum; ++v)		visited[v] = FALSE;	// 置初值		InitQueue(Q);			// 置空的辅助队列Q	for (v = 0; v < G.vexnum; ++v)	// 如果是连通图，只v=0就遍历全图	{		if (!visited[v])		{			visited[v] = TRUE;			Visit(G.vertices[v].data);			EnQueue(Q,v);	// 入队			while (!QueueEmpty(Q))	// 队列不空			{				DeQueue(Q,u); // 队头元素出队并置为u				for (w = FirstAdjVex(G,G.vertices[u].data); w > 0; w = NextAdjVex(G,G.vertices[u].data,G.vertices[w].data))					if (!visited[w])					{						visited[w] = TRUE;						Visit(G.vertices[w].data);						EnQueue(Q,w);	// w入队					}			}		}	}	printf("\n");}// 从第v个顶点出发递归地深度优先遍历图G。仅适用于邻接表存储结构voID DFS1(ALGraph G,int v,voID(*Visit)(char*)){	ArcNode *p;	visited[v] = TRUE;			// 设置访问标志为TRUE(已访问)	Visit(G.vertices[v].data);	// 访问该顶点	for (p = G.vertices[v].firstarc; p; p = p->next)		if (!visited[p->data.adjvex])			DFS1(G,p->data.adjvex,Visit);	// 对v的尚未访问的邻接点递归调用DFS1}// 对图G作深度优先遍历。DFS1设函数指针参数voID DFSTraverse1(ALGraph G,voID(*Visit)(char*)){	int v;	for (v = 0; v < G.vexnum; v++)		visited[v] = FALSE;	for (v = 0; v < G.vexnum; v++)		// 如果是连通图，只v=0就遍历全图		if (!visited[v])				// v尚未被访问			DFS1(G,Visit);			// 对v调用DFS1	printf("\n"); }// 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。仅适用于邻接表结构voID BFSTraverse1(ALGraph G,voID(*Visit)(char*)){    int v,u;   ArcNode *p; 	// p指向表结点   linkQueue Q; // 链队列类型   for(v = 0; v < G.vexnum; ++v)     	visited[v] = FALSE; // 置初值为未被访问   InitQueue(Q); // 初始化辅助队列Q   for(v = 0; v < G.vexnum; v++) // 如果是连通图，只v=0就遍历全图     	if(!visited[v]) // v尚未被访问     	{       		visited[v]=TRUE; // 设v为已被访问       		Visit(G.vertices[v].data); // 访问v       		EnQueue(Q,v); // v入队列       		while(!QueueEmpty(Q)) // 队列不空       		{         		DeQueue(Q,u); // 队头元素出队并置为u         		for(p=G.vertices[u].firstarc;p;p=p->next) // p依次指向u的邻接顶点           			if(!visited[p->data.adjvex]) // u的邻接顶点尚未被访问           			{             			visited[p->data.adjvex]=TRUE; // 该邻接顶点设为已被访问             			Visit(G.vertices[p->data.adjvex].data); // 访问该邻接顶点             			EnQueue(Q,p->data.adjvex); // 入队该邻接顶点序号           			}       		}     	}   	printf("\n");}voID display(ALGraph G){ // 输出图的邻接矩阵G   int i;   ArcNode *p;   switch(G.kind)   {     case DG: printf("有向图\n");	      break;     case DN: printf("有向网\n");	      break;     case UDG:printf("无向图\n");	      break;     case UDN:printf("无向网\n");   }   printf("%d个顶点：\n",G.vexnum);   for(i=0;i<G.vexnum;++i)     printf("%s ",G.vertices[i].data);   printf("\n%d条弧(边):\n",G.arcnum);   for(i=0;i<G.vexnum;i++)   {     p=G.vertices[i].firstarc;     while(p)     {       if(G.kind<=1||i<p->data.adjvex) // 有向或无向两次中的一次       {         printf("%s→%s ",G.vertices[i].data,G.vertices[p->data.adjvex].data);         if(G.kind%2) // 网           printf(":%d ",*(p->data.info));       }       p=p->nextarc;     }     printf("\n");   }} voID print(char *i) {   printf("%s ",i); }int main(){   int i,n;   ALGraph g;   VertexType v1,v2;   printf("请顺序选择有向图,无向网\n");   for(i=0;i<4;i++) // 验证4种情况   {     CreateGraph(g);     display(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)	   InsertArc(g,v2,v1);	 else	   InsertArc(g,v1,v2);       }       else // 无向	 InsertArc(g,v2);     }     display(g);     if(i==3)     {       printf("删除一条边或弧，请输入待删除边或弧的弧尾 弧头：");       scanf("%s%s",v2);       DeleteArc(g,v2);       printf("修改顶点的值，请输入原值 新值: ");       scanf("%s%s",v2);       PutVex(g,v2);     }     printf("删除顶点及相关的弧或边，请输入顶点的值: ");     scanf("%s",v1);     DeleteVex(g,v1);     display(g);     DestroyGraph(g);   }}

总结

以上是内存溢出为你收集整理的数据结构学习笔记 --- 图（邻接表）全部内容，希望文章能够帮你解决数据结构学习笔记 --- 图（邻接表）所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。