2019独角兽企业重金招聘Python工程师标准>>> 
图的表示
对于图G=(V,E),可以用两种标准方法表示。第一种是将图作为邻接链表的组合，另外一种表示方法是则是将图邻接矩阵来看待。两种表示方法既可以用来表示无向图也可以用来表示有向图，邻接链表的方法在表示稀疏图（边的条数E，远远小于V结点的个数）比较好。比较稠密的图则适合
邻接矩阵的方法.
#include <iostream>
#include <type_traits>
#include <queue>namespace{
enum Color{ white=0, gray=1, black=3 };
}class Edge{//这里的edge指的是一条边,类似这样 start-------end; start和end都为结点. public:int start;int end;int value;Edge* next;Edge(const int& s, const int& e, const int& v);
};Edge::Edge(const int& s, const int& e, const int& v):start(s),end(e),value(v)
{//
}class Vertex{ //结点的顶点. public:Color color;int distance; //两个结点之间的距离，相邻的两个结点距离为1.int pie; //储存父结点. Edge* head; //这其实是个顶点被封装在Vertex中. Vertex():color(white),distance(0),pie(0){} //初始化顶点的颜色为白色 标明还没有找到该顶点，初始化顶点
};class Graph{private:int nodeNumber; //无向图中结点的个数.Vertex* v; //顶点.std::queue<int> que; void detroyEdge(Edge* edge);void addSingleEdge(const int& start, const int& end, const int& value);void deleteSingleEdge(const int& start, const int& end);public:Graph(const int& numberOfNode);~Graph(); void addDoubleEdge(const int& start, const int& end, const int& value=1);void BFSearch(const int& s); void PrintPath(const int& a, const int& b);
};Graph::Graph(const int& numberOfNode):nodeNumber(numberOfNode),v(nullptr)
{this->v = new Vertex[numberOfNode+1]; //之所以+1因为树的个数是从1开始数的. std::cout<<"success"<<std::endl;
}void Graph::addSingleEdge(const int& start, const int& end, const int& value) //存储无向图.
{Edge* newEdge = new Edge(start, end, value); //创建一个边 边的左右节点分别为start和end，且start和end之间的距离为value;也就是说他们之间只有一条线连接. if(this->v[start].head == nullptr || (this->v[start].head)->end > end){ //这里判断给定的边的顶结点(start)是否存在顶点，且给定结点（start）如果存在顶点那么他的最小节点是否大于newEdge的end(节点) //如果符合上述条件那么令新给的边的顶点(start)成为自身顶点.newEdge->next = this->v[start].head; //令v[start]中的顶点 this->v[start].head = newEdge;}else{Edge* tempEdge = this->v[start].head; //令tempEdge和pre都等于当前顶点. Edge* pre = tempEdge;while(newEdge != nullptr && newEdge->end < end){ //树可能很深 因此要用while. pre = newEdge; //注意跳出循环的时候pre总是等于e的head. newEdge = newEdge->next;}if(newEdge != nullptr && newEdge->end == end){delete newEdge;return;}newEdge->next = newEdge;//把新节点插入到合适的位置. pre->next = newEdge;}
}void Graph::addDoubleEdge(const int& start, const int& end, const int& value)
{this->addSingleEdge(start, end, value); //以start为新建边的顶点. this->addSingleEdge(end, start, value); //以end为新建边的顶点。
}void Graph::deleteSingleEdge(const int& start, const int& end)
{Edge* e = this->v[start].head;Edge* pre = e; //此时pre和e都指向顶点.while(e != nullptr && e->end < end){ //注意此处这里寻找小于边(start------end)中end的那个结点. pre = e;e = e->next;} if(e == nullptr || e->end > end){ //此时说明给定的结点end是不存在无向图中的. return;}if(e == this->v[start].head){this->v[start].head = e->next;}else{pre->next = e->next;}delete e; //销毁e.
}void Graph::BFSearch(const int& s) //广度最优搜索.
{int i;for(i=1; i<this->nodeNumber; ++i){ //把每个结点的颜色都设置为white; this->v[i].color = ::white;this->v[i].distance = 0x7fffffff; //注意这里的 0xffffff为long int的最大值.this->v[i].pie = 0; // pie表示的是当前结点的父节点. }this->v[s].color = ::gray; //设置源结点的颜色为gray; this->v[s].distance = 0x7fffffff; //设置源结点的distance为一个无穷大的数. this->v[s].pie = 0; //设置源结点的父节点为空(0)。 while(!que.empty()){this->que.pop(); //栈内元素清空. }this->que.push(s); //把源结点s。放到栈内. while( !this->que.empty() ){int u;int tempV;u = this->que.front(); //读取栈内的源结点. this->que.pop();Edge* e = this->v[u].head; while( e != nullptr ){ tempV = e->end; //令tempV = 源结点的一个子结点. if(this->v[tempV].color == ::white){ //如果该子节点的颜色为white this->v[tempV].color = ::gray;this->v[tempV].distance = this->v[u].distance + 1;this->v[tempV].pie = u;this->que.push(tempV);}e = e->next;}this->v[u].color = ::black;}}void Graph::PrintPath(const int& a, const int& b) //输出结点a到结点b之间的所有结点.
{this->BFSearch(a); //设置源节点为a. if(a == b){ //当结点a与结点b相同的时候那么就没有再继续寻找的意义了所以路过的结点就只有a. std::cout<<a<<" ";}else{if(this->v[b].pie == 0){ //判断节点b是否含有父结点. 如果没有父结点那么b点就不存在无向图中. std::cout<<"no path from "<<a<<" to "<<b;}else{ //存在父结点那么寻找a,到b的父节点之间经过的所有结点. this->PrintPath(a, this->v[b].pie);std::cout<<b<<" ";}}
}void Graph::detroyEdge(Edge* edge)
{Edge* e = edge->next;delete edge;edge = nullptr;if(e != nullptr){this->detroyEdge(e);}return;
}Graph::~Graph()
{while(!this->que.empty()){this->que.pop();}if(this->v != nullptr){for(int i=1; i<=this->nodeNumber; ++i){if(this->v[i].head != nullptr){Edge* tempEdge = this->v[i].head;this->detroyEdge(tempEdge);}}}
}int main()
{
/*
1 2
1 5
2 6
6 7
6 3
3 7
3 4
7 8
7 4
4 8
*/Graph* myGraph = new Graph(int(8)); //这里的8指的是结点的个数.
int a;
int b;for(int i=0; i<=8; ++i){std::cin>>a>>b;myGraph->addDoubleEdge(a, b);}myGraph->BFSearch(2); //当给定源结点为2的时候所有节点的父节点.int s=2;
int e=4;
myGraph->PrintPath(s, e);
return 0;
}