图的遍历（邻接矩阵，邻接链表）,c++描述
拿这张图作为实例
图数据使用csv文件保存
- 例 0,1 则存在一条0顶点指向1顶点的边
- 例 0,1,2,3 则存在3条分别从0顶点指向1,2,3顶点的边
- 当一个节点仅指向另外一节点时有向，所有节点都相互指向时无向
则此图的描述为
其它不多说直接上代码
#include<iostream>
#include<vector>
#include<fstream>
#include<string>
#include<algorithm>
using namespace std;
enum DataSuructType//数据结构类型
{
AdjMartix,//邻接矩阵
AdjLink//邻接链表
};
class Graph
{
public:
Graph()=default;
~Graph()=default;
//file_name保存图信息的 data_type保存图信息的数据结构类型
Graph(string file_name, DataSuructType _data_struct_type);
void PrintMatrix();
//vertex 深搜遍历的起点， 返回所有路程的向量
vector<vector<int>> DFS(int vertex);
//获取对应顶点的度数
int GetDegress(int vertex);
private:
//顶点数量
int vertex_num;
//边数量
int edge_num;
//当前使用的数据结构类型
DataSuructType data_struct_type;
//保存图信息的邻接矩阵
vector<vector<bool>> graph_info_martix;
//保存图信息的邻接链表 STL的stack过于简单不能满足需求，使用vector代替
vector<vector<int>> graph_info_link;
};
Graph::Graph(string file_name, DataSuructType _data_struct_type)
{
//读取保存图信息的文件，以csv的方式保存
//例 0,1 则存在一条0顶点指向1顶点的边
//例 0,1,2,3 则存在3条分别从0顶点指向1,2,3顶点的边
ifstream input(file_name);
this->data_struct_type = _data_struct_type;
if (this->data_struct_type==AdjLink)
{
while (input.good())
{
string line;
input >> line;
int pos = line.find(",");
if (pos==-1)
{
continue;
}
vector<int> new_link;
while (pos != -1)
{
int pos_next = line.find(",", pos);
if (new_link.empty())
{
new_link.push_back(line.substr(0, pos)[0] - 'A');
//-'A'是因为转成int不是从0开始，而索引从0开始
//图1.2使用的是A,B,C。。。先行转换成int再保存
//若是顶点用字符串表示，考虑时间复杂度可以采用红黑树保存
}
else
{
this->edge_num++;
if (pos_next==-1)
{
new_link.push_back(line.substr(pos, line.length())[0] - 'A');
break;
}
new_link.push_back(line.substr(pos, pos_next)[0] - 'A');
}
pos = pos_next + 1;
}
vertex_num++;
this->graph_info_link.push_back(new_link);
}
}
else
{
int line_num = 0;
while (input.good())//计算顶点数
{
string line;
input >> line;
line_num++;
}
input.close();
input.open(file_name);
this->vertex_num = line_num;
for (int i = 0; i < line_num; i++)
{
vector<bool> temp;
temp.resize(line_num);
this->graph_info_martix.push_back(temp);
}
while (input.good())
{
string line;
input >> line;
int pos = line.find(",");
if (pos == -1)
{
continue;
}
bool is_first = true;
int vertex_first;//0->1,0->2 中的0
while (pos != -1)
{
int pos_next = line.find(",", pos);
if (is_first)
{
vertex_first = line.substr(0, pos)[0];
is_first = 0;
}
else
{
this->edge_num++;
int vertex_second;//0->1,0->2 中的1,2
if (pos_next == -1)
{
vertex_second=line.substr(pos, line.length())[0];
this->graph_info_martix[vertex_first-'A'][vertex_second - 'A'] = 1;
break;
}
vertex_second = line.substr(pos, pos_next)[0];
this->graph_info_martix[vertex_first - 'A'][vertex_second - 'A'] = 1;
}
pos = pos_next + 1;
}
}
}
input.close();
}
void Graph::PrintMatrix()
{
for (auto x : this->graph_info_martix)
{
for (auto x_0 : x)
{
if (x_0 == 1)
{
cout << "* ";
}
else
{
cout << " ";
}
}
cout << endl;
}
}
vector<vector<int>> Graph::DFS(int vertex)
{
auto find_vec = [](int obj, vector<int> vec_obj)
{
int pos = 0;
for (auto x:vec_obj)
{
if (x==obj)
{
return pos;
}
pos++;
}
return -1;
};
vector<vector<int>> return_info;
if (this->data_struct_type==AdjLink)
{
vector<int> road = { vertex };
int pos_0 = 0;
while (true)//尽可能使用迭代避免栈溢出
{
if (pos_0>= this->graph_info_link[*--road.cend()].size())//如果在当前顶点没有找到路，往回退
{
int last = *--road.cend();//切记!左闭合右开 [begin,end)
road.pop_back();
pos_0 = find_vec(last, graph_info_link[*--road.cend()]) + 1;
if (road.size()==1)//如果退到了第一位，结束
{
break;
}
}
else
{
int next_ver = this->graph_info_link[*--road.cend()][pos_0];
if (find_vec(next_ver, road) == -1)//如果这个方向的顶点不在里面
{
road.push_back(next_ver);
if (road.size() == this->vertex_num)//得到一条路
{
int last = *--road.cend();
return_info.push_back(road);
road.pop_back();
pos_0 = find_vec(last, graph_info_link[*--road.cend()]) + 1;
}
else
{
pos_0 = 0;
}
}
else
{
pos_0++;
}
}
}
}
else
{
auto find_next = [](int pos, vector<bool> obj_vec)
{
int pos_next = pos + 1;
while (pos_next!=obj_vec.size())
{
if (obj_vec[pos_next]==1)
{
return pos_next;
}
pos_next++;
}
return int(obj_vec.size());
};
vector<int> road = { vertex };
int pos_0 = 0;
while (true)//尽可能使用迭代避免栈溢出
{
if (pos_0 >= this->vertex_num)//如果在当前顶点没有找到路，往回退
{
int last = *--road.cend();//切记!左闭合右开 [begin,end)
road.pop_back();
pos_0 = find_next(last, this->graph_info_martix[*--road.cend()]) ;
if (road.size() == 1)//如果退到了第一位，结束
{
break;
}
}
else
{
bool next_ver = this->graph_info_martix[*--road.cend()][pos_0];
if (find_vec(pos_0, road) == -1&&
next_ver==1)//如果这个方向的顶点不在里面
{
road.push_back(pos_0);
if (road.size() == this->vertex_num)//得到一条路
{
return_info.push_back(road);
int last = *--road.cend();
road.pop_back();
pos_0 = find_next(last, this->graph_info_martix[*--road.cend()]) ;
}
else
{
pos_0 = 0;
}
}
else
{
pos_0++;
}
}
}
}
return return_info;
}
int Graph::GetDegress(int vertex)
{
int degress=0;
for (auto x:this->graph_info_martix[vertex])
{
if (x==1)
{
degress++;
}
}
return degress;
}
int main()
{
Graph ga("graph.csv",AdjLink);
Graph gb("graph.csv", AdjMartix);
for (char i = 'A'; i < 'I'+1; i++)
{
cout << "以" << i << "起点" << endl;
auto info = ga.DFS(i - 'A');
for (auto x:info)
{
for (auto x_0:x)
{
if (char(x_0 + 'A') !=i)
{
cout << " -> ";
}
cout << char(x_0+'A');
}
cout << endl;
}
}
gb.PrintMatrix();
for (char i = 'A'; i < 'I' + 1; i++)
{
cout << "以" << i << "起点" << endl;
auto info = gb.DFS(i - 'A');
for (auto x : info)
{
for (auto x_0 : x)
{
if (char(x_0 + 'A') != i)
{
cout << " -> ";
}
cout << char(x_0 + 'A');
}
cout << endl;
}
}
system("pause");
return 0;
}
运行得到结果
即所有节点作为起点的所有遍历路线
如何实现加权图，最短路径
- 单独用一个csv文件保存各个路径的长度加载到字典，再对生成好的路径进行查询排序
如何搜索任意两个结点之间的而非遍历全图
- 遍历得到一条路的条件是当前搜索到的路径结点等于全图的节点数，只要条件改成得到的路的最后一个节点为目标结点就行