邻接表存储的有向图的基本操作(C语言实现)

/*
 * 邻接表存储的有向图的基本操作
 */
#include<stdio.h>
#include<stdlib.h>

#define MAX_VERTEX 20
typedef char VertexType;

//用数组vertex按序存放遍历的各个顶点，广度遍历时看成队列，深度遍历时看成栈
VertexType vertex[MAX_VERTEX];

//图的边的定义
typedef struct EdgeNode
{
	int nextToVertex;           //相邻顶点
    struct EdgeNode * nextEdge; //下一条边
}EdgeNode,*PEdgeNode;

//图的顶点的定义
typedef struct
{
	VertexType vertex;      //顶点信息
    PEdgeNode  firstEdge;   //第一条边（出度）
}VertexNode,*PVertexNode;

//图的定义 
typedef struct 
{
    int vertexNum;         //顶点个数
	int edgeNum;           //边的个数
	VertexNode vertexNode[MAX_VERTEX]; //顶点信息数组
}GraphList,*PGraphList;

//建立有向图
void createGraph(PGraphList pGraph)
{
	int i,from,to;
	PEdgeNode p,pEdge;
    
	printf("请输入有向图顶点个数：\n");
	scanf("%d",&pGraph->vertexNum);
	for(i=0;i<pGraph->vertexNum;i++){
        pGraph->vertexNode[i].vertex='a'+i; 
		pGraph->vertexNode[i].firstEdge=NULL;
	}
	printf("请输入有向图边的个数：\n");
	scanf("%d",&pGraph->edgeNum);
	printf("请输入有向图边的信息：\n");
	printf("起始点   终点\n");
	for(i=0;i<pGraph->edgeNum;i++){
		scanf("%d%d",&from,&to);

		pEdge=(PEdgeNode)malloc(sizeof(EdgeNode));
		pEdge->nextEdge=NULL;
		pEdge->nextToVertex=to;

		p=pGraph->vertexNode[from].firstEdge;
		if(!p)
           pGraph->vertexNode[from].firstEdge=pEdge;
        else{
			while(p->nextEdge){
               p=p->nextEdge;
			}
			p->nextEdge=pEdge;
		}
	}
}

//求指定顶点
VertexType getVertexByIndex(PGraphList pGraph,int index)
{
	return pGraph->vertexNum==0?'0':pGraph->vertexNode[index].vertex;
}

//求第一个顶点
VertexType getFirstVertex(PGraphList pGraph)
{
	return pGraph->vertexNum==0?'0':pGraph->vertexNode[0].vertex;
}

//求图中顶点index的下一个顶点
VertexType getVertexAfterIndex(PGraphList pGraph,int index)
{
    return (index>=0 && index+1 < pGraph->vertexNum) ? pGraph->vertexNode[index+1].vertex : '0';
}

//求第一个与顶点index相邻的顶点
VertexType getVertexNextIndex(PGraphList pGraph,int index)
{
	if(index>=0&&index<pGraph->vertexNum){
        if(pGraph->vertexNode[index].firstEdge)
			return pGraph->vertexNode[pGraph->vertexNode[index].firstEdge->nextToVertex].vertex;
	}
	return '0';
}

//根据顶点信息寻返回顶点在图中的位置
int findVertex(PGraphList pGraph,VertexType vertex)
{
	int i;
	for(i=0;i<pGraph->vertexNum;i++)
		if(pGraph->vertexNode[i].vertex==vertex)
			return i;
	return -1;
}

//返回任一顶点的出度
int getArcsNum(PGraphList pGraph,int index)
{
	int k=0;
	PEdgeNode p=pGraph->vertexNode[index].firstEdge; 
	if(index>=0&&index<pGraph->vertexNum){
		while(p){
			k++;
			p=p->nextEdge;
		}
		return k;
	}
	return -1;
}

//判断任意两个顶点之间是否有边
int connected(PGraphList pGraph,int from,int to)
{
	PEdgeNode p=pGraph->vertexNode[from].firstEdge;
    if((from<0 || from>=pGraph->vertexNum) || (to<0 && to>=pGraph->vertexNum))
		return 0;
	while(p){
		if(p->nextToVertex==to)
			return 1;
		p=p->nextEdge;
	}
	return 0;
}

//广度优先遍历
void breadthTraverse(PGraphList pGraph)
{
	int i,k;
	int flag[MAX_VERTEX];//记录顶点的下标
	int front,rear;
    PEdgeNode p;
	front=rear=0;
	for(i=0;i<MAX_VERTEX;i++)
		flag[i]=-1;
	//从第一个顶点开始
	front=rear=0;
	vertex[rear++]=pGraph->vertexNode[0].vertex;
	flag[0]=0;

	while(front<rear){
		i=flag[front];
		p=pGraph->vertexNode[i].firstEdge;
		while(p){
			for(k=0;k<rear;k++)//判断此顶点是否在队列中
				if(flag[k]==p->nextToVertex)
					break;
            if(k==rear){
				vertex[rear]=pGraph->vertexNode[p->nextToVertex].vertex;
				flag[rear++]=p->nextToVertex;
			}
			p=p->nextEdge;
		}
		front++;
	}
}

//深度优先遍历
void depthTraverse(PGraphList pGraph)
{
	int i,top=0,k,m;
	int flag[MAX_VERTEX];//记录顶点的下标
	PEdgeNode p;
	for(i=0;i<MAX_VERTEX;i++)
		flag[i]=-1;
	//从第一个顶点开始
	vertex[top++]=pGraph->vertexNode[0].vertex;
	flag[0]=0;

	while(top>0 && top<pGraph->vertexNum){
		if(!p)//退栈，从上一个顶点开始
			i=flag[--m];
		else
			m=i=flag[top-1];
       
		p=pGraph->vertexNode[i].firstEdge;
        while(p){
        	for(k=0;k<top;k++)
				if(flag[k]==p->nextToVertex)
					break;
            if(k==top){
				vertex[top]=pGraph->vertexNode[p->nextToVertex].vertex;
				flag[top++]=p->nextToVertex;
				break;
			}
			p=p->nextEdge;
		} 
	}
}

//测试
void main()
{
	int i;
    GraphList  graph;
    createGraph(&graph);
	printf("指定顶点：%c\n",getVertexByIndex(&graph,0));
	printf("第一个顶点：%c\n",getFirstVertex(&graph));
	printf("index的下一个顶点：%c\n",getVertexAfterIndex(&graph,0));
	printf("第一个与顶点index相邻的顶点：%c\n",getVertexNextIndex(&graph,0));
	printf("根据顶点信息寻返回顶点在图中的位置：%d\n",findVertex(&graph,'b'));
	printf("返回任一顶点的出度：%d\n",getArcsNum(&graph,0));
	printf("判断任意两个顶点之间是否有边：%d\n",connected(&graph,0,1));

    printf("-----------广度优先遍历-----------------\n\n");
	breadthTraverse(&graph);
	for(i=0;i<graph.vertexNum;i++)
    	printf("%-3c",vertex[i]);

    printf("\n\n-------深度优先遍历------------------\n\n");
	depthTraverse(&graph);
	for(i=0;i<graph.vertexNum;i++)
    	printf("%-3c",vertex[i]);
	printf("\n\n");
}