struct AdjacencyMatrix//邻接矩阵
{
int inf = 0x3f3f3f3f;//设一个无穷大用来表示不连通的弧的权值
int V_num;//顶点数量
int V_max;//顶点最大ID
bool V[105];//V[i]表示顶点i是否存在
int MA[105][105];//图矩阵
void init()//初始化
{
V_num = 0;
V_max = 0;
memset(V, false, sizeof(V));
memset(MA, 0x3f, sizeof(MA));
}
void insert_vertex(int a)//插入顶点
{
if (a > V_max)
V_max = a;
if (!V[a])
{
V[a] = true;
V_num++;
}
}
void delete_vertex(int a)//删除顶点
{
if (!V[a])
return;
for (int i = 0; i <= V_max; i++)//同时将该顶点的弧删除,即权值设为无穷大
{
MA[i][a] = inf;
MA[a][i] = inf;
}
if (a == V_max)
{
for (int i = V_max - 1; i >= 0; i--)
if (V[i])
{
V_max = i;
break;
}
if (V_max == a)
V_max = 0;
}
V[a] = false;
V_num--;
}
void add_edge(int a, int b, int weight)//插入弧
{
insert_vertex(a);
insert_vertex(b);
MA[a][b] = weight;
}
void remove_edge(int a, int b)//删除弧
{
MA[a][b] = inf;
}
bool adjacent(int a, int b)//判断a,b是否连通
{
if (MA[a][b] < inf)
return true;
else
return false;
}
void neighbors(int a)//列出所有与a邻接的弧
{
for (int i = 0; i <= V_max; i++)
if (adjacent(a,i))
printf("%d---%d\n", a, i);
}
int first_neighbor(int a)//返回顶点a的第一个邻接点,没有则返回-1
{
for (int i = 0; i <= V_max; i++)
if (adjacent(a, i))
return i;
return -1;
}
int next_neighbor(int a, int b)//返回顶点a的在b之后的下一个邻接点,没有则返回-1
{
for (int i = b+1; i <= V_max; i++)
if (adjacent(a, i))
return i;
return -1;
}
int get_edge_value(int a, int b)//获取a到b的弧的权值
{
return MA[a][b];
}
void set_edge_value(int a, int b, int v)//设定a到b的弧的权值
{
MA[a][b] = v;
}
};