对于图的构造我们有三种方法，第一种邻接矩阵，第二种邻接表，第三种十字链表。在这里我们深度解析 邻接矩阵与邻接表 的构造方法！

首先我们阐述第一种方法: 邻接矩阵 （邻接矩阵用于相对来说比较稠密的无向图）

例如此无向图:

相对应的邻接矩阵表示如下:

#include<iostream>#include<string>#define maxSize 10using namespace std;//在此声明 不用template 模板class Graph {public: Graph(string str[], int vertex, int arc1); ~Graph() { //由于没有动态申请内存 无法对改内存进行释放(在此处做声明) cout << "析构函数调用成功!"; }; void DFS(int v); //深度优先遍历 void FdgDFS(int v); //非递归的深度优先遍历 void BFS(int v); //广度优先遍历private: int verNum; int arcNum; string verName[maxSize]; //对于邻接矩阵构造无向图肯定少不了邻接矩阵 即二维数组 int arc[maxSize][maxSize]; //遍历时，对于没有访问过的顶点，需要建立flag 标识 int visited[maxSize] = { 0 };};Graph::Graph(string str[], int vertex, int arc1) { verNum = vertex; //顶点的赋值 for (int i = 0; i < verNum; i++) { verName[i] = str[i]; } for (int i = 0; i < verNum; i++) //初始化邻接矩阵 for (int j = 0; j < verNum; j++) arc[i][j] = arc[j][i] = 0; //对边进行构造 输入依附于边的邻接点的下标 arcNum = arc1; for (int k = 0; k < arcNum; k++) { int i = 0; int j = 0; cout << "请输入依附于边的邻接点下标 " << endl; cin >> i >> j; //无向图的邻接矩阵是对称的 arc[i][j] = arc[j][i] = 1; }}//递归的深度遍历void Graph::DFS(int v) { cout << verName[v]; visited[v] = 1; for (int j = 0; j < verNum; j++) { if (arc[v][j] == 1 && visited[j] == 0) DFS(j); }}//非递归的深度优先遍历void Graph::FdgDFS(int v){ for (int i = 0; i <= maxSize; i++) { visited[i] = 0; }  int Stack[maxSize]; int top = -1; cout << verName[v]; visited[v] = 1; Stack[++top] = v; while (top != -1) { v = Stack[top]; for (int j = 0; j < verNum; j++) { if (arc[v][j] == 1 && visited[j] == 0) { cout << verName[j]; visited[j] = 1; Stack[++top] = j; break; } if (j == verNum - 1) top--; } }}//广度优先遍历void Graph::BFS(int v) { for (int i = 0; i <= maxSize; i++) { visited[i] = 0; }  //定义队列进行遍历 int Queue[maxSize]; int front = -1; int rear = -1; cout << verName[v]; visited[v] = 1; Queue[++rear] = v; while (front != rear) { //出队 v = Queue[++front]; for (int j = 0; j < verNum; j++) if (arc[v][j] == 1 && visited[j] == 0) { cout << verName[j]; visited[j] = 1; //入队 Queue[++rear] = j; } }}int main(){ string mystr[4] = { "v0","v1","v2","v3" }; Graph myGraph(mystr, 4, 4); //深度优先遍历 myGraph.DFS(2); //非递归深度优先遍历 myGraph.FdgDFS(2); //广度优先遍历 myGraph.BFS(2); return 0;}