一、图的基本知识
对于图这个数据结构，我们通常有两种普遍的存储方式。分别时邻接表法和矩阵法参考博客。虽然图的结构会比二叉树复杂一些，但是整个图的算法会比二叉树简单，主要原因我觉得，至少图没有那么多难理解的递归算法。一般来说，我们解决图的问题的时候也总是需要，面对问题来创建图的结构。但是这样的话，当我们需要在及短的时间重新为这个问题定制一套算法，对于我这种普通人，就会很难受。所以，我们换一个思路去解决问题。我们可以把题目中给的图的信息，转化为我们最常用的图的结构存储起来，这样我们只需要临时写一个转换的接口函数。这样难道不香吗？故，我的图的结构是一个比较完善，尽管，也会对于某些问题稍显复杂，对某些问题又略显简单。但是一般思路都差不了多少，还是那句话学计算机，有手就行。
1.1 图的一般存结构
#define MYDATA char //节点本身信息
#define INT int
#define P_NODE NODE* //节点指针对象
#define P_EDGE EDGE*
using namespace std;
class NODE; //图节点
class EDGE;//边信息
class Graph;//图结构
class NODE
{
public:
MYDATA val;
INT in, out;
list<P_NODE> *nexts; //都定义指针是为了在堆上面开辟信息
list<P_EDGE> *edges; //该节点有的边信息
NODE()
{
val = 0;
in = out = 0;
nexts = new list<P_NODE>();
edges = new list<P_EDGE>();
}
};
class EDGE //边信息
{
public:
P_NODE from;
P_NODE to;
INT weight;
EDGE()
{
from = NULL;
to = NULL;
weight = 0;
}
};
class Graph
{
public:
map<MYDATA, P_NODE> *pGra;
list<P_EDGE> *pEge;
Graph()
{
pGra = new map<MYDATA,P_NODE>();
pEge = new list<P_EDGE>();
}
void createGra(MYDATA[][3],int); //接口是二维数组转化为图。第一列代表权重，第二列代表起始点，第三列代表结束点。
void BFS(MYDATA); // 广度遍历
void DFS(MYDATA); //深度遍历
};
二、图的基本算法
#include "graph.h"
//赋值函数
void eva(P_NODE &f,P_NODE &n,P_EDGE &e,MYDATA *a)
{
f->val = a[1];
f->out++;
n->val = a[2];
n->in++;
e->from = f;
e->to = n;
e->weight = a[0];
}
void Graph::createGra(MYDATA arr[][3],int C)
{
P_NODE pf = NULL;//源节点
P_NODE pn = NULL;//目地节点
P_EDGE pe = NULL;//边节点
int i = 0;//图节点的个数
while (i<C) //直到所有图节点录入完毕
{
try {
pe = new EDGE();
}
catch (exception e) //申请空间异常
{
cout << e.what() << endl;
}
if (pGra->find(arr[i][1]) == pGra->end())//判断是已经在map中有值
{
pf = new NODE();
pGra->insert(pair<MYDATA, P_NODE>(arr[i][1], pf));//将前值点插入地图中
}
if (pGra->find(arr[i][2]) == pGra->end())//判断是已经在map中有值
{
pn = new NODE();
pGra->insert(pair<MYDATA, P_NODE>(arr[i][2], pn));//将前值点插入地图中
}
eva(pGra->at(arr[i][1]), pGra->at(arr[i][2]), pe, arr[i]); //赋值操作
pGra->at(arr[i][1])->nexts->push_back(pn);
pGra->at(arr[i][2])->edges->push_back(pe);
pEge->push_back(pe);
i++;
}
}
void Graph::BFS(MYDATA d) //宽度遍历
{
queue<P_NODE> q;
set<P_NODE> s;//这个验证是否有节点已经进入队列
q.push(pGra->at(d));
s.insert(pGra->at(d));
while (!q.empty())
{
P_NODE term = q.front();
q.pop();//出队列
cout << term->val << " ";
for (list<P_NODE>::iterator it = term->nexts->begin(); it!= term->nexts->end(); ++it)
{
if (s.find(*it) == s.end())
{
s.insert(*it);
q.push(*it);
}
}
}
}
void Graph::DFS(MYDATA d) //深度遍历——随便哪一个点先进入都可以
{
if (pGra->at(d) == NULL)
{
return;
}
stack<P_NODE> st;
set<P_NODE> se;
st.push(pGra->at(d));//先把头节点放入栈中
se.insert(pGra->at(d));//在放入set当中
cout << (pGra->at(d))->val << " ";
while (!st.empty())
{
P_NODE term = st.top();//出栈
st.pop();
for (list<P_NODE>::iterator it = term->nexts->begin(); it != term->nexts->end(); ++it)
{
if (se.find(*it) == se.end())
{
st.push(term);
st.push(*it);
se.insert(*it);
cout << (*it)->val << " ";
break;
}
}
}
}