图的操作(邻接表形式).cpp

对图的操作

#include<stdio.h>    //包含基本输入输出函数
#include<string.h>   //包含字符串函数
#include<stdlib.h>  //包含exit()及动态存储分配等函数
#include<malloc.h>
#define NULL 0
#define OK 1
#define  INFINITY         INT_MAX
#define  Maxsize   20
typedef int VertexType;
typedef int AdjMatrix[Maxsize][Maxsize];
typedef int Status;

struct ArcNode                          //定义边结点
{
	int            adjvex;              //该弧所指向的顶点的位置
	struct ArcNode *nextarc;            //指向下一条弧的指针
};
struct Vnode
{
	int            data;                //顶点信息 
	struct ArcNode *firstarc;           //指向第一条依附该顶点的弧的指针
}Vnode,AdjList[Maxsize];
int anum,vnum,v,cord;

int duiying(struct Vnode AdjList[Maxsize],int v)//找出顶点对应的位置
{
	int k;
	for(k=0;k<vnum;k++)
       	  if(AdjList[k].data==v)
			  return k;
}

void creatgraph(struct Vnode AdjList[Maxsize])
{
	int i,j,k,h;
	struct ArcNode *p;
	printf("输入图的顶点数和边数:");
	scanf("%d %d",&vnum,&anum);          //输入图的边数和顶点数 
    printf("输入图的各个顶点:");
    for(k=0;k<vnum;k++)
	{   
		scanf("%d",&v);
		AdjList[k].data=v;
		AdjList[k].firstarc=NULL;
	}
    printf("\n输入每条边关联的顶点:\n");    //输入和边关联的顶点号，建立相应的链表
	for(k=0;k<anum;k++)
	{
		scanf("%d,%d",&i,&j);
		p=(struct ArcNode *) malloc(sizeof(struct ArcNode));
		p->adjvex=j;
		h=duiying(AdjList,i);
		p->nextarc=AdjList[h].firstarc;     //每一个边结点均插入在链表的首部
		AdjList[h].firstarc=p;
		p=(struct ArcNode *) malloc (sizeof(struct ArcNode));
		p->adjvex=i;
		h=duiying(AdjList,j);
	    p->nextarc=AdjList[h].firstarc;
		AdjList[h].firstarc=p;
	}
	printf("\n");
}
void printcreatgraph(struct Vnode AdjList[Maxsize])   //显示已建立的邻接表信息
{
	int k;struct ArcNode *p;
	for(k=0;k<vnum;k++)   
	{
		printf("%d",AdjList[k].data);
		p=AdjList[k].firstarc;
		while (p)
		{  printf("->%d",p->adjvex);
		   p=p->nextarc;}
		printf("\n");
	}
}
void bianli(int visited[],struct ArcNode *p)  //遍历各个顶点
{int y,l;
	while (p!= NULL)
		{
			y=p->adjvex;
			l=duiying(AdjList,y);
			if(visited[l]==0)
			{
				visited[l]=1;        //若未遍历过，则遍历，并且把下一个顶点进栈，从本顶点出发继续按深度遍历
				printf("->%d",y);
				p=p->nextarc;
				p=AdjList[l].firstarc;
                bianli(visited,p);	 //递归遍历
			}
			else p=p->nextarc;
		}
}
void dfs(struct Vnode AdjList[Maxsize])
{
	struct ArcNode *q;           //定义指针
	int x,i,h;
	int visited[Maxsize];        //用作存放已遍历过顶点的标记
	do
	{
	    for (i=0;i<vnum;i++)
		visited[i]=0;
	    printf("\n输入图遍历的始顶点(按0退出遍历):");
		scanf("%d",&x);            //输入图遍历的始顶点
		printf("%d",x);
		h=duiying(AdjList,x);
		visited[h]=1;
		q=AdjList[h].firstarc;     //下一个要遍历的顶点所关联的边结点，向量表的下标从0开始
		while (q!= NULL)
		{bianli(visited,q);		
		 q=q->nextarc;}
	}while (x!=0);
}
void main()
{ 
	creatgraph(AdjList);
	printf("输出已建立的邻接表如下:\n");
	printcreatgraph(AdjList);
  	dfs(AdjList);
}