图的基本操作——邻接矩阵表示（网（边带权值的图）的编程没有给出，与一般的图类似）

[c++]代码库

temp1.h

#define VertexType int
#define AdjMatrix int
	typedef enum{NG, DG, NW, DW}GraphKind;
#define Status int
#define MAX_N 10
#define OK 1
#define ERROR 0

typedef struct{
	VertexType vexs[MAX_N];//表示顶点的数组;
	AdjMatrix arcs[MAX_N][MAX_N];//表示边的二维数组;
	int vexnum,arcnum;//顶点和边的个数;
	GraphKind kind;
}MGraph;//定义图MGraph；用邻接矩阵表示。





temp1.cpp

#include<iostream>
#include<fstream>
#include"temp1.h"
	using namespace std;

int LocateVex(MGraph G, VertexType v){
	//在图G的vexs(顶点）中找值为v的元素的下标，如果没有则返回-1；
	for(int i = 0; i < G.vexnum; i++){
		if(G.vexs[i] == v){
			return i;
		}
	}
	return -1;
}

Status CreateMGraph(MGraph &G){
	//创建图G,输入（读文件）的值有
	//1.图的顶点数,边/弧的数目，图的类型
	//2.依次输入顶点的值
	//3.依次输入一条边的起点和终点；
	ifstream in;
	in.open("data3.txt", ios::in);
	cout<<"下列数据从文件data3.txt读入"<<endl<<endl;
	cout<<"请输入图的顶点数,边/弧的数目，图的类型"<<endl;
	int kind;
	in>>G.vexnum>>G.arcnum>>kind;//从文件读入数据，遇到任何结束标记（如空格和换行）则停止。
	switch(kind){
	case 0 :
		G.kind = NG;
		break;
	case 1:
		G.kind = DG;
		break;
	case 2:
		G.kind = NW;
		break;
	case 3:
		G.kind = DW;
		break;
	}
	cout<<"请依次输入顶点的值"<<endl;
	for(int i = 0; i < G.vexnum; i++){
		in>>G.vexs[i];
	}
	for(int i = 0; i < G.vexnum; i++){
		for(int j = 0; j < G.vexnum; j++){
			G.arcs[i][j] = 0;
		}
	}
	cout<<"请依次输入一条边的起点和终点："<<endl;
	for(int k = 0; k < G.arcnum; k++){
		int v1, v2, i, j;
		in>>v1>>v2;
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		G.arcs[i][j] = 1;
		if(G.kind == NG)//无向图
			G.arcs[j][i] = 1;
	}
	cout<<endl;
	return OK;
}

int Degree(MGraph G, VertexType v){
	//求图G中顶点值为v的顶点的度，找到则返回v的度，如果没有顶点值为v的顶点则返回-1；
	int i = LocateVex(G, v);
	if(i == -1){
		return -1;//顶点不存在
	}
	int num = 0;
	for(int j = 0; j < G.vexnum; j++){
		if(G.arcs[i][j] == 1){
			num++;
		}
	}
	if(G.kind == DG){//有向图
		for(int j = 0; j < G.vexnum; j++){
			if(G.arcs[j][i] == 1){
				num++;
			}
		}
	}
	return num;
}

int IsAdj(MGraph G, VertexType v1, VertexType v2){
	//判断图G中的顶点v1， v2是否具有邻接关系；如果有图则返回1，带权值的网则返回“权值”；
	//没有找到这两个顶点则返回-1

	int i = LocateVex(G, v1);
	if(i == -1){
		return -1;
	}
	int j = LocateVex(G, v2);
	if(j == -1){
		return -1;
	}
	return G.arcs[i][j];
}

Status InsertVertex(MGraph &G, VertexType v){
	//在图G中插入顶点v；插在末尾；
	if(LocateVex(G, v) != -1){
		return ERROR;
	}
	if(G.vexnum >= MAX_N){
		//扩容
	}
	G.vexs[G.vexnum] = v;
	for(int i = 0; i <= G.vexnum; i++){
		G.arcs[G.vexnum][i] = 0;
		G.arcs[i][G.vexnum] = 0;
	}
	G.vexnum++;
	return OK;
}

Status InsertAdj(MGraph &G, int i, int j){
	//增加边/弧，即增加下标为i的顶点到下标为j的顶点之间的邻接关系；
	//如果边已经存在则返回ERROR。
	if(i < 0 || i >= G.vexnum || j < 0 || j >= G.vexnum){
		return ERROR;//顶点不存在
	}
	if(G.arcs[i][j] == 1){
		return ERROR;//边已经存在
	}
	G.arcs[i][j] = 1;
	if(G.kind == NG){
		G.arcs[j][i] = 1;
	}
	G.arcnum++;
	return OK;
}

Status DeleteAdj(MGraph &G, int i, int j){
	//删除边/弧，即删除下标为i的顶点到下标为j的顶点之间的邻接关系；
	//如果边已经不存在则返回ERROR。
	if(i < 0 || i > G.vexnum || j < 0 || j >= G.vexnum){
		return ERROR;//顶点不存在
	}
	if(G.arcs[i][j] == 0){
		return ERROR;//边已不存在
	}
	G.arcs[i][j] = 0;
	if(G.kind == NG){
		G.arcs[j][i] = 0;
	}
	G.arcnum--;
	return OK;
}


int main(){
	//依次测试函数CreateMGraph Degree IsAdj InsertVertex 
	//InsertAdj DeleteAdj
	MGraph G;
	CreateMGraph(G);
	int n;
	n = Degree(G, 2);
	cout<<"顶点2的度为："<<n<<endl;
	n = IsAdj(G, 3, 4);
	cout<<"顶点3, 4之间的邻接关系："<<n<<endl;
	n = IsAdj(G, 3, 2);
	cout<<"顶点3, 2之间的邻接关系："<<n<<endl;
	InsertVertex(G, 5);
	n = IsAdj(G, 5, 5);
	cout<<"顶点5，5之间的邻接关系："<<n<<endl;
	InsertAdj(G, 5, 5);
	n = IsAdj(G, 5, 5);
	cout<<"顶点5，5之间的邻接关系："<<n<<endl;
	DeleteAdj(G, 3, 4);
	n = IsAdj(G, 3, 4);
	cout<<"顶点3, 4之间的邻接关系："<<n<<endl;
	system("pause");
	return 0;
}





data3.txt

	5
	5
	0
	0
	1
	2
	3
	4
	1
	1
	1
	2
	2
	4
	3
	3
	3
	4