--并没有深究图，暂时只是简单记录。
图主要的存储方式有两种：邻接矩阵和邻接表。
一个图的邻接矩阵表示法是唯一的，邻接表表示法是不唯一的。
邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。
对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。
邻接矩阵长这样：(无向图)
两顶点之间有连接的为1，反之为0；
所以，图的类属性要有一个用来保存顶点之间关系的二维数组（adjMat）、保存顶点的数组（这里（后面的代码中）采用的是指针数组（vertexList））和保存顶点个数的变量（nVertes）。
图的遍历
深度优先遍历（DFS(Deep First Search)）和广度优先遍历（BFS(Breadth First Search)）
深度优先遍历类似于二叉树的前序遍历；
广度优先遍历类似于二叉树的层次遍历。
图的深度优先遍历和广度优先遍历结果都不唯一。
深度优先遍历（DFS）：
深度优先遍历图的方法是，从图中某顶点v出发：
（1）访问顶点v；
（2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历直至图中和v有路径相通的顶点都被访问；
（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
比如：
此图深度优先遍历结果为：A->B->E->C->D。
遍历到A->B->E->C时，此时与C连接的没有未被访问的顶点了，所以回溯到E，发现未被访问的顶点有D，所以访问D，（A->B->E->C->D），然后此时没有与D连接的没有未被访问的顶点了，所以回溯到E...再回溯到B...再回溯到A。
而本代码中是根据邻接矩阵进行深度优先遍历的，所以是这样：
代码实现时用栈（先进后出）：先访问A，并把A入栈；访问B，把B入栈；访问E，把E入栈；访问C，把C入栈；此时，与C连接的顶点都被访问了，所以C出栈，返回上一个顶点E；访问D，把D入栈；此时，与D连接的顶点都被访问了，所以D出栈，返回上一个顶点E。同理，E出栈...B、A出栈。
广度优先遍历（BFS）：
对于上面的图，广度遍历是这样的：先访问A，然后访问与A相连的B、D，再访问E，再访问C。所以结果是：A->B->D->E->C;
代码实现时用队（先进先出）：先A入栈，访问A；再A出栈，同时把与A相连的B、D入栈；再B出栈，与B相连并未被访问的E入栈；D出栈；E出栈，与E相连并未被访问的C入栈；C出栈。
我这里都是简单的实现，写的都是无向图。
邻接矩阵代码：
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
#define MAX_VERTS 20
class Vertex {
public:
Vertex(char lab) {
label = lab;
visited = false;
}
char label;
bool visited;//记录此节点是否访问
};
class Graph {
public:
Graph();
~Graph();
void addVertex(char lab);
void addEdge(int start, int end);
void printMatrix();
void showVertex(int v);//打印顶点
int getAdjUnvisitedVertex(int v);//找下一个没被访问的结点
void DFS();//深度优先搜索
void BFS();//广度优先搜索
private:
Vertex* vertexList[MAX_VERTS];
int nVertes;
int adjMat[MAX_VERTS][MAX_VERTS];
};
void Graph::showVertex(int v) {
cout<<vertexList[v]->label<<" ";
}
int Graph::getAdjUnvisitedVertex(int v) {
for (int i = 0; i < nVertes; i++) {
if (adjMat[v][i] == 1 && vertexList[i]->visited == false) {
return i;
}
}
return -1;
}
void Graph::DFS() {
stack<int> gStack;//保存是的顶点的下标
vertexList[0]->visited = true;
showVertex(0);
gStack.push(0);
int v;
while (!gStack.empty()) {
v = getAdjUnvisitedVertex(gStack.top());
//没有下一个没被访问的顶点，就返回上一个顶点
if (v == -1) {
gStack.pop();
}
else {
vertexList[v]->visited = true;
showVertex(v);
gStack.push(v);
}
}
cout << endl;
for (int i = 0; i < nVertes; i++) {
vertexList[i]->visited = false;
}
}
void Graph::BFS() {
queue<int> q;
vertexList[0]->visited = true;
q.push(0);
while (!q.empty()) {
int v = q.front();
cout << vertexList[v]->label << " ";
q.pop();
int res = getAdjUnvisitedVertex(v);
while (res != -1) {
vertexList[res]->visited = true;
q.push(res);
res = getAdjUnvisitedVertex(v);
}
}
cout << endl;
for (int i = 0; i < nVertes; i++) {
vertexList[i]->visited = false;
}
}
Graph::Graph() {
for (int i = 0; i < MAX_VERTS; i++) {
for (int j = 0; j < MAX_VERTS; j++) {
adjMat[i][j] = 0;
}
}
nVertes = 0;
}
void Graph::addVertex(char lab) {
vertexList[nVertes++] = new Vertex(lab);
}
void Graph::addEdge(int start, int end) {
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
void Graph::printMatrix() {
for (int i = 0; i < nVertes; i++) {
for (int j = 0; j < nVertes; j++) {
cout << adjMat[i][j] << " ";
}cout << endl;
}
}
Graph::~Graph() {
for (int j = 0; j < nVertes; j++) {
delete vertexList[j];
}
}
int main()
{
Graph g;
g.addVertex('A');//0
g.addVertex('B');//1
g.addVertex('C');//2
g.addVertex('D');//3
g.addVertex('E');//4
g.addEdge(0,1);
g.addEdge(0,3);
g.addEdge(1,4);
g.addEdge(3,4);
g.addEdge(2,4);
//g.printMatrix();
g.DFS();
g.BFS();
return 0;
}
邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。
邻接表长这样：（无向图）
所以，图的类属性要有一个用来保存顶点的数组（这里采用了指针（VertexTable）指向一个数组）、指向 保存多个链表的数组 的指针（HeadNodes）和保存顶点个数的变量（nVertex）。（代码中写了一个用来保存顶点总数的变量n，可忽略）
邻接表代码：
#include <iostream>
#include<list>
using namespace std;
class Vertex {
public:
char label;
Vertex(char lab) {
label = lab;
}
Vertex(){}
};
ostream& operator << (ostream& out, const Vertex& v) {
cout << v.label;
return out;
}
template<class T>
class Graph {
public:
Graph(const int num) :n(num) {
VertexTable = new T[num];//num个顶点
HeadNodes = new list<int>[num];//num个链表
nVertex = 0;//开始时，当前顶点个数为0
}
~Graph() {
delete []VertexTable;
delete []HeadNodes;
}
void addVertex(T v);//添加顶点
void addEdge(int start, int end);//添加边
void printVertice();//打印顶点
void printAdjList();//打印边
private:
T* VertexTable;//存放顶点的数组
list<int>* HeadNodes;//
int n;//顶点总数
int nVertex;//当前顶点个数
};
template<class T>
void Graph<T>::addVertex(T v) {
VertexTable[nVertex++] = v;
}
template<class T>
void Graph<T>::addEdge(int start, int end) {
HeadNodes[start].push_back(end);
}
template<class T>
void Graph<T>::printVertice() {
for (int i = 0; i < nVertex; i++) {
cout << VertexTable[i] << " ";
}
cout << endl;
}
template<class T>
void Graph<T>::printAdjList() {
for (int i = 0; i < nVertex; i++) {
cout << i << "->";
list<int>::iterator iter = HeadNodes[i].begin();
for (iter; iter != HeadNodes[i].end(); iter++) {
cout << *iter << "->";
}
cout << "end" << endl;
}
}
int main()
{
Graph<Vertex> g(10);
Vertex a('A'),b('B'),c('C'),d('D'),e('E');
g.addVertex(a);
g.addVertex(b);
g.addVertex(c);
g.addVertex(d);
g.addVertex(e);
g.printVertice();
g.addEdge(0,1);
g.addEdge(0,3);
g.addEdge(1,0);
g.addEdge(1,4);
g.addEdge(2,4);
g.addEdge(3,0);
g.addEdge(3,4);
g.addEdge(4,1);
g.addEdge(4,2);
g.addEdge(4,3);
g.printAdjList();
}
结果：
图具体介绍：（https://baijiahao.baidu.com/s?id=1629054934725051961&wfr=spider&for=pc）
