邻接表存储的有向图的基本操作(C语言实现)
/* * 邻接表存储的有向图的基本操作 */#include<stdio.h>#include<stdlib.h>#define MAX_VERTEX 20typedef 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];elsem=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");}?