c/c++ 图相关的函数(二维数组法)
- 遍历图
- 插入顶点
- 添加顶点间的线
- 删除顶点
- 删除顶点间的线
- 摧毁图
- 取得与v顶点有连线的第一个顶点
- 取得与v1顶点,v1顶点之后的v2顶点的之后的有连线的第一个顶点
graph_mtx.h
#ifndef __graph_mtx__
#define __graph_mtx__
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include <memory.h>
#define Default_vertex_size 10
#define T char//dai biao ding dian de lei xing
typedef struct GraphMtx{
int MaxVertices;//zui da ding dian shu liang]
int NumVertices;//shi ji ding dian shu liang
int NumEdges;//bian de shu lian
T* VerticesList;//ding dian list
int** Edge;//bian de lian jie xin xi, bu shi 0 jiu shi 1
}GraphMtx;
//chu shi hua tu
void init_graph(GraphMtx* gm);
//打印二维数组
void show_graph(GraphMtx* gm);
//插入顶点
void insert_vertex(GraphMtx* gm, T v);
//添加顶点间的线
void insert_edge(GraphMtx* gm, T v1, T v2);
//删除顶点
void remove_vertex(GraphMtx* gm, T v);
//删除顶点间的线
void remove_edge(GraphMtx* gm, T v1, T v2);
//摧毁图
void destroy_graph(GraphMtx* gm);
//取得与v顶点有连线的第一个顶点
int getNeighbor(GraphMtx* gm, T v);
//取得与v1顶点,v1顶点之后的v2顶点的之后的有连线的第一个顶点
int getNextNeighbor(GraphMtx* gm, T v1, T v2);
#endif
graph_mtx.c
#include "graph_mtx.h"
void init_graph(GraphMtx* gm){
gm->MaxVertices = Default_vertex_size;
gm->NumEdges = gm->NumVertices = 0;
//kai pi ding dian de nei cun kong jian
gm->VerticesList = (T*)malloc(sizeof(T) * (gm->MaxVertices));
assert(NULL != gm->VerticesList);
//创建二维数组
//让一个int的二级指针,指向一个有8个int一级指针的数组
//开辟一个能存放gm->MaxVertices个int一级指针的内存空间
gm->Edge = (int**)malloc(sizeof(int*) * (gm->MaxVertices));
assert(NULL != gm->Edge);
//开辟gm->MaxVertices组,能存放gm->MaxVertices个int的内存空间
for(int i = 0; i < gm->MaxVertices; ++i){
gm->Edge[i] = (int*)malloc(sizeof(int) * gm->MaxVertices);
}
//初始化二维数组
//让每个顶点之间的边的关系都为不相连的
for(int i = 0; i < gm->MaxVertices; ++i){
for(int j = 0; j < gm->MaxVertices; ++j){
gm->Edge[i][j] = 0;
}
}
}
//打印二维数组
void show_graph(GraphMtx* gm){
printf(" ");
for(int i = 0; i < gm->NumVertices; ++i){
printf("%c ", gm->VerticesList[i]);
}
printf("\n");
for(int i = 0; i < gm->NumVertices; ++i){
//在行首,打印出顶点的名字
printf("%c:", gm->VerticesList[i]);
for(int j = 0; j < gm->NumVertices; ++j){
printf("%d ", gm->Edge[i][j]);
}
printf("\n");
}
printf("\n");
}
//插入顶点
void insert_vertex(GraphMtx* gm, T v){
//顶点空间已满,不能再插入顶点了
if(gm->NumVertices >= gm->MaxVertices){
return;
}
gm->VerticesList[gm->NumVertices++] = v;
}
int getVertexIndex(GraphMtx* gm, T v){
for(int i = 0; i < gm->NumVertices; ++i){
if(gm->VerticesList[i] == v)return i;
}
return -1;
}
//添加顶点间的线
void insert_edge(GraphMtx* gm, T v1, T v2){
if(v1 == v2)return;
//查找2个顶点的下标
int j = getVertexIndex(gm, v1);
int k = getVertexIndex(gm, v2);
//说明找到顶点了,并且点之间还没有线
if(j != -1 && k != -1 && gm->Edge[j][k] != 1){
//因为是无方向,所以更新2个值
gm->Edge[j][k] = gm->Edge[k][j] = 1;
//边数加一
gm->NumEdges++;
}
}
//删除顶点间的线
void remove_edge(GraphMtx* gm, T v1, T v2){
if(v1 == v2)return;
//查找2个顶点的下标
int j = getVertexIndex(gm, v1);
int k = getVertexIndex(gm, v2);
//说明找到顶点了,并且点之间还有线
if(j != -1 && k != -1 && gm->Edge[j][k] == 1){
//因为是无方向,所以更新2个值
gm->Edge[j][k] = gm->Edge[k]