图的邻接表的实现以及各种基本操作（附C++实现代码）

╰半夏微凉° 2023-06-30 06:54 11阅读 0赞

## 图 ##

图的存储形式有很多，例如邻接矩阵，邻接表，多重邻接表，十字链表  
**这里将介绍图的邻接表存储形式：**

##### 邻接表的实现思想： #####

**邻接表的概念我们就不再进行赘述，主要是将实现邻接表的实现思路捋一捋。**

首先，邻接表存储的**基本思想**：对于图的每个顶点vi,我们将所有邻接vi的顶点连接成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维数组构成了顶点表。  
而邻接表有着两种格式，**一是顶点表节点，另外一种是边表节点。**  
**顶点表节点由存储数据的数据域和存储边表头结点的指针域所组成。** **边表节点则是由存储边的终点在顶点表中的下标的数据域和指向下一个节点的指针域组成。**

#### 接下来是具体代码的实现： ####

##### 一、首先是边表节点的定义 #####

typedef char VexTexType;
    typedef int OtherInfo;
    
    #define MaxVexNum 100 //定义最大顶点数为100
    
    class ArcNode{//边
    public:
    	int adjVex;//该边所指向的顶点的位置
    	ArcNode* next;//指向下一条边
    	OtherInfo info;//其他信息，如权值
    	ArcNode(int adjvex) {
    		this->adjVex = adjvex;
    		this->next = NULL;
    	}
    	//构造函数
    	ArcNode(int adjvex, OtherInfo info) {
    		this->adjVex = adjVex;
    		this->info = info;
    	}
    };

##### 二、顶点的节点定义 #####

class VexNode{//顶点
    public:
    	char data;//值
    	ArcNode* firstArc;//指向该点的第一条邻接点
    };

##### 三、图结构的定义 #####

**图的结构由顶点和边构成**

class MyGraph {//定义图结构
    public:
    	VexNode vex[MaxVexNum];//顶点集
    	int curVexNum;
    	int curArcNum;//当前图的边数和顶点数
    	
    	//构造函数
    	MyGraph() {
    		this->vex[MaxVexNum] = {0};
    		this->curArcNum = 0;
    		this->curVexNum = 0;
    	}
    		void initMyGraph();//初始化图，根据输入生成一个图
    	    int locateVex(char v);//返回顶点v的位置
    };

##### 接下来是实现图的基本方法 #####

**初始化图，根据输入生成一个图**

void MyGraph::initMyGraph() {
    	cout << "请输入图的顶点数和边数" << endl;
    	cin >> this->curVexNum >> this->curArcNum;
    	
    	cout << "请输入顶点：" << endl;//初始化顶点集
    	//通过for循环来输入边之间的关系
    	for (int i = 0; i < this->curVexNum; i++) {
    		cin >> this->vex[i].data;
    		this->vex[i].firstArc = NULL;
    	}
    
    	cout << "请输入边及其依附的顶点" << endl;
    	char temp_v1 = '0';
    	char temp_v2 = '0';
    	for (int i = 0; i < this->curArcNum; i++) {
    		cin >> temp_v1 >> temp_v2;
    		int index_v1 = this->locateVex(temp_v1);
    		int index_v2 = this->locateVex(temp_v2);//找到位置之后 生成边节点
    
    		//生成一个边表节点，然后将新的边表节点插入到对应顶点的后面
    		ArcNode* p1 = new ArcNode(index_v2);
    		p1->next = this->vex[index_v1].firstArc;
    		this->vex[index_v1].firstArc = p1;
    	
    		//对称插入
    		ArcNode* p2 = new ArcNode(index_v1);
    		p2->next = this->vex[index_v2].firstArc;
    		this->vex[index_v2].firstArc = p2;
    	}
    	cout << "初始化成功!" << endl;
    }

**输入顶点v，然后返回顶点v在顶点v中的位置**

int MyGraph::locateVex(char v) {
    	//返回顶点v的位置
    	for (int i = 0; i < this->curVexNum; i++) {
    		if (this->vex[i].data == v) {
    			return i;
    		}
    	}
    	cout << "并不存在这个点" << endl;
    	return -1;
    }

##### 创建图的实际运行效果（打印函数我并没有放到这上面） #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09uZV9jYXN0bGU_size_16_color_FFFFFF_t_70]

### 如有错误欢迎大家和我一起讨论。谢谢 ###

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09uZV9jYXN0bGU_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200115165923583.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09uZV9jYXN0bGU=,size_16,color_FFFFFF,t_70