邻接矩阵存储的无向网的基本操作（C语言实现）

/* *无向网的基本操作(邻接矩阵存储) */#include<stdio.h>#define MAX_VERTEX_NUM 20typedef char VertexType;typedef struct {int vertexNum;//顶点个数VertexType vertex[MAX_VERTEX_NUM];//顶点信息int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵 }GraphMatrix,*PGraphMatrix;//用数组vertex按序存放遍历的各个顶点，广度遍历时看成队列，深度遍历时看成栈VertexType vertex[MAX_VERTEX_NUM];//建立无向网void createGraph(PGraphMatrix pGraph){int i,j,arcNum,from,to,weight;printf("please enter the numbers of vertex(顶点):\n");scanf("%d",&pGraph->vertexNum);    for(i=0;i<pGraph->vertexNum;i++)        pGraph->vertex[i]='a'+i;for(i=0;i<pGraph->vertexNum;i++)for(j=0;j<pGraph->vertexNum;j++)            pGraph->arcs[i][j]=0;printf("please enter the numbers of arcs(弧):\n");scanf("%d",&arcNum);for(i=0;i<arcNum;i++){    printf("please enter the information of arcs(弧),(起始点  终点  权值):\n");        scanf("%d%d%d",&from,&to,&weight);pGraph->arcs[from][to]=weight;pGraph->arcs[to][from]=weight;}}//求指定顶点VertexType getVertexByIndex(PGraphMatrix pGraph,int index){return pGraph->vertexNum==0?'0':pGraph->vertex[index];}//求第一个顶点VertexType getFirstVertex(PGraphMatrix pGraph){return pGraph->vertexNum==0?'0':pGraph->vertex[0];}//求图中顶点index的下一个顶点VertexType getVertexAfterIndex(PGraphMatrix pGraph,int index){    return (index>=0 && index+1 < pGraph->vertexNum) ? pGraph->vertex[index+1] : '0';}//求第一个与顶点index相邻的顶点VertexType getVertexNextIndex(PGraphMatrix pGraph,int index){int j;if(index>=0&&index<pGraph->vertexNum){        for(j=0;j<pGraph->vertexNum;j++)            if(j!=index&&pGraph->arcs[index][j]!=0)return pGraph->vertex[j];}return '0';}//根据顶点信息寻返回顶点在图中的位置int findVertex(PGraphMatrix pGraph,VertexType vertex){int i;for(i=0;i<pGraph->vertexNum;i++)if(pGraph->vertex[i]==vertex)return i;return -1;}//返回任一顶点的边的个数int getArcsNum(PGraphMatrix pGraph,int index){int j,k=0;if(index>=0&&index<pGraph->vertexNum){        for(j=0;j<pGraph->vertexNum;j++)            if(pGraph->arcs[index][j]!=0)k++;return k;}return -1;}//广度优先遍历void breadthTraverse(PGraphMatrix pGraph){int i,j,k;int flag[MAX_VERTEX_NUM];//记录顶点的下标int front,rear;front=rear=0;for(i=0;i<MAX_VERTEX_NUM;i++)flag[i]=-1;//从第一个顶点开始front=rear=0;vertex[rear++]=pGraph->vertex[0];flag[0]=0;while(front<rear){i=flag[front];for(j=0;j<pGraph->vertexNum;j++){//遍历i为下标的那一行for(k=0;k<rear;k++)//判断此顶点是否在队列中if(flag[k]==j)break;            if(k==rear && i!=j && pGraph->arcs[i][j]!=0){vertex[rear]=pGraph->vertex[j];flag[rear++]=j;}} front++;}}//深度优先遍历void depthTraverse(PGraphMatrix pGraph){int i,j,top=0,k,m;int flag[MAX_VERTEX_NUM];//记录顶点的下标for(i=0;i<MAX_VERTEX_NUM;i++)flag[i]=-1;//从第一个顶点开始vertex[top++]=pGraph->vertex[0];flag[0]=0;while(top>0 && top<pGraph->vertexNum){if(j==pGraph->vertexNum)//退栈，从上一个顶点开始i=flag[--m];elsem=i=flag[top-1];for(j=0;j<pGraph->vertexNum;j++){for(k=0;k<top;k++)if(flag[k]==j)break;            if(k==top && i!=j && pGraph->arcs[i][j]!=0){vertex[top]=pGraph->vertex[j];flag[top++]=j;break;}} }}//测试void main(){int i;GraphMatrix graph;    createGraph(&graph);printf("指定顶点：%c\n",getVertexByIndex(&graph,1));printf("第一个顶点：%c\n",getFirstVertex(&graph));printf("index的下一个顶点：%c\n",getVertexAfterIndex(&graph,0));printf("第一个与顶点index相邻的顶点：%c\n",getVertexNextIndex(&graph,1));printf("根据顶点信息寻返回顶点在图中的位置：%d\n",findVertex(&graph,'b'));printf("返回任一顶点的边的个数：%d\n",getArcsNum(&graph,0));    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");}

?