原创内容，转载请注明原文网址：http://homeqin.cn/a/wenzhangboke/jishutiandi/youxikaifa/2018/1226/273.html
图的表示方法主要有邻接矩阵和邻接表。其中常州手机App开发邻接表最为常用，因此这里便以邻接表为例介绍一下图的创建及遍历方法。
创建图用到的结构有两种：顶点及弧
struct ArcNode
{
int vertexIndex; //该弧指向的顶点位置
struct ArcNode* next; //指向下一个弧
InfoType info; //该弧的相关信息，如权重等
};
struct Vertex
{
VertexType data; //顶点信息
ArcNode* firstArc; //指向第一条依附该节点弧的指针
ColorType color; //访问情况
}
其中ColorType是一个枚举，遍历的时候才会用到。图的创建比较简单，直接看代码很容易理解，这里不再详细说了。 常州网站开发培训图的深度和广度遍历直接看算法导论中的两张图就明白了 ：
其中ColorType是一个枚举，遍历的时候才会用到。图的创建比较简单，直接看代码很容易理解，这里不再详细说了。 常州网站开发培训图的深度和广度遍历直接看算法导论中的两张图就明白了 ：
//结点颜色代表遍历情况
enum ColorType
{
WHITE, //未访问
GRAY, //正在访问，邻接点还没访问完
BLACK //访问完毕
};
#include <queue>
#include <stack>
#include <iostream>
using namespace std;
enum GraphType
{
UNDIR_UNWEIGHT_GRAPH, //无向无权图
UNDIR_WEIGHT_GRAPH, //无向带权图
DIR_UNWEIGHT_GRAPH, //有向无权图
DIR_WEIGHT_GRAPH //有向带权图
};
//结点颜色代表遍历情况
enum ColorType
{
WHITE, //未访问
GRAY, //正在访问，邻接点还没访问完
BLACK //访问完毕
};
template<typename VertexType,typename InfoType>
class Graph
{
public:
Graph(int vertexNum, GraphType type) :m_vertexNum(vertexNum), m_type(type), m_arcNum(0)
{
for (int i = 0; i < MAX_VERTEX_NUM; ++i)
{
m_vertices[i].firstArc = nullptr;
}
}
void Create()
{
switch (m_type)
{
case UNDIR_UNWEIGHT_GRAPH:
CreateUndirUnweightGraph();
break;
case UNDIR_WEIGHT_GRAPH:
CreateUndirWeightGraph();
break;
case DIR_UNWEIGHT_GRAPH:
CreateDirUnweightGraph();
break;
case DIR_WEIGHT_GRAPH:
CreateDirWeightGraph();
break;
default:
break;
}
}
//输出图的信息
void Display()
{
for (int i = 0; i < m_vertexNum; ++i)
{
cout << "第" << i + 1 << "个结点为" << m_vertices[i].data << " 邻接表为：";
ArcNode* node = m_vertices[i].firstArc;
while (node)
{
cout << "->" << m_vertices[node->vertexIndex].data << "(" << node->info << ")";
node = node->next;
}
cout << endl;
}
}
void BFS()
{
for (int i = 0; i < m_vertexNum; ++i)
{
m_vertices[i].color = WHITE;
}
cout << "图的广度优先遍历为：";
BFS(&m_vertices[0]);
cout << endl;
}
void DFS()
{
for (int i = 0; i < m_vertexNum; ++i)
{
m_vertices[i].color = WHITE;
}
cout << "图的深度优先遍历为：";
DFS(&m_vertices[0]);
cout << endl;
}
private:
struct ArcNode
{
int vertexIndex; //该弧指向的顶点位置
struct ArcNode* next; //指向下一个弧
InfoType info; //该弧的相关信息，如权重等
};
struct Vertex
{
VertexType data; //常州企业App培训顶点信息
ArcNode* firstArc; //指向第一条依附该节点弧的指针
ColorType color; //访问情况
};
//最大顶点数
static const int MAX_VERTEX_NUM = 20;
Vertex m_vertices[MAX_VERTEX_NUM]; //顶点列表
int m_vertexNum; //当前顶点数量
int m_arcNum; //当前弧数量
GraphType m_type; //图类型：有向无权图、有向带权图、无向无权图、无向无权图
private:
//初始化顶点列表
void InitVertices()
{
cout << "请输入每个顶点的关键字" << endl;
VertexType data;
for (int i = 0; i < m_vertexNum; ++i)
{
cin >> data;
m_vertices[i].data = data;
}
}
//插入一个表结点
void Insert(int headVertex, int tailVertex, InfoType info)
{
//构造一个邻接表结点，即创建一条弧
ArcNode* newNode = new ArcNode;
newNode->info = info;
newNode->next = nullptr;
newNode->vertexIndex = tailVertex;
//找到邻接表的最后一个节点
ArcNode* lastNode = m_vertices[headVertex].firstArc;
if (lastNode == nullptr)
m_vertices[headVertex].firstArc = newNode;
else
{
while (lastNode->next)
{
lastNode = lastNode->next;
}
lastNode->next = newNode;
}
++m_arcNum;
}
//创建无向无权图
void CreateUndirUnweightGraph()
{
InitVertices();
cout << "请分别输入每条边的起始结点:" << endl;
int head, tail;
while (cin >> head >> tail)
{
//无向图head->tail tail->head插入两次
Insert(head, tail, 0);
Insert(tail, head, 0);
}
}
//创建无向有权图
void CreateUndirWeightGraph()
{
InitVertices();
cout << "请分别输入每条边的起始结点和权值:" << endl;
int head, tail;
InfoType weight;
while (cin >> head >> tail >> weight)
{
Insert(head, tail, weight);
Insert(tail, head, weight);
}
}
//创建常州微信公众平台有向无权图
void CreateDirUnweightGraph()
{
InitVertices();
cout << "请分别输入每条边的起始结点值:" << endl;
int head, tail;
while (cin >> head >> tail)
{
Insert(head, tail,0);
}
}
//创建有向带权图
void CreateDirWeightGraph()
{
InitVertices();
cout << "请分别输入每条边的起始结点和权值:" << endl;
int head, tail;
InfoType weight;
while (cin >> head >> tail >> weight)
{
Insert(head, tail, weight);
}
}
void BFS(Vertex* vertex)
{
vertex->color = GRAY;
queue<Vertex*> vertices;
vertices.push(vertex);
while (!vertices.empty())
{
Vertex* curVertex = vertices.front();
vertices.pop();
cout << curVertex->data << "->";
ArcNode* node = curVertex->firstArc;
while (node)
{
Vertex* tmpVertex = &m_vertices[node->vertexIndex];
if (tmpVertex->color == WHITE)
{
tmpVertex->color = GRAY;
vertices.push(tmpVertex);
}
node = node->next;
}
curVertex->color = BLACK;
}
}
void DFS(Vertex* vertex)
{
vertex->color = GRAY;
stack<Vertex*> vertices;
vertices.push(vertex);
while (!vertices.empty())
{
Vertex* curVertex = vertices.top();
vertices.pop();
cout << curVertex->data << "->";
ArcNode* node = curVertex->firstArc;
while (node)
{
Vertex* tmp = &m_vertices[node->vertexIndex];
if (tmp->color == WHITE)
{
tmp->color = GRAY;
vertices.push(tmp);
}
node = node->next;
}
curVertex->color = BLACK;
}
}
};
int main()
{
int vertexNum;
cout << "请输入要创建的图的结点数：";
cin >> vertexNum;
Graph<char, int> g(vertexNum,GraphType::UNDIR_UNWEIGHT_GRAPH);
g.Create();
g.Display();
g.BFS();
g.DFS();
}
常州微信小程序开发运行结果：(创建的树为算法导论BFS说明图片中的树)
上篇：上一篇：常州微信小程序开发-各种字符串哈希函数比较
下篇：下一篇：常州微信小程序-Unity判断手势
