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

/*
 *无向网的基本操作(邻接矩阵存储)
 */
#include<stdio.h>
#define MAX_VERTEX_NUM 20

typedef 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];
		else
			m=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");
}