如图,
这是我写图结构的实现过程中定义的两个结构体,一个是结点Node
Node包含三个元素: chr inform 表示字符型信息
vector表示包含这个结点的边
int postion 是我为这条边编辑的顺序,其大小取决于生成顺序,但是几乎没什么用,考虑到删除结点或边会引起这个量的变化或者缺失,几乎没用
Edge包含四个元素: int tag,同样表示生成编号,几乎没用
int weight 表示这条边的权重
Node begin Node end 表示这条边的起点和终点
除此之外,还在class tgrape 定义了
从上到下分别表示 储存所有结点 储存所有边 点编号 边编号 检测该字符是否在图中存在 用于遍历的表示是否访问过
这三个函数用来寻找结点和边 都是从claas里边的所有点和所有边寻找的
还有增加结点、边和删除结点、边的操作,放到后面,也是引用的
问题来了,当我DFS遍历的时候
遍历只能进行到第一层,
求解决方法,下面是全部代码
#pragma once
#define _MY_GRAPE_H_
#include<vector>
#include<iostream>
#include<algorithm>
#include<utility>
using namespace std;
struct Edge;
struct Node
{
char inform;
vector<Edge> neibor_edge;
int postion;
Node()
{
}
Node(char data, int pos)
{
inform = data;
postion = pos;
}
void operator = (const Node& Anot)
{
this->inform = Anot.inform;
this->postion = Anot.postion;
this->neibor_edge = Anot.neibor_edge;
}
bool operator == (const Node& Anot)
{
return (this->inform == Anot.inform && this->postion == Anot.postion);
}
};
bool cmp_node(Node& A, Node& B)
{
return A.postion < B.postion;
}
struct Edge
{
Node begin;
Node end;
int weight;
int tag;
Edge()
{
}
Edge(Node A, Node B,int tag_,int _weight = 0)
{
if (A.postion < B.postion)
{
begin = A;
end = B;
}
else
{
begin = B;
end = A;
}
weight = _weight;
tag = tag_;
}
void operator = (const Edge& Anot)
{
this->begin = Anot.begin;
this->end = Anot.end;
this->weight = Anot.weight;
this->tag = Anot.tag;
}
bool operator == (const Edge& Anot)
{
return (this->begin == Anot.begin && this->end == Anot.end && this->weight == Anot.weight && this->tag == Anot.tag);
}
};
bool cmp_edge(Edge& S, Edge& L)
{
return S.tag < L.tag;
}
Node Another_node(Node& A, Edge& The_edge)
{
for (int i = 0; i < A.neibor_edge.size(); i++)
{
if (A.neibor_edge[i] == The_edge)
{
if (The_edge.begin == A)
{
return The_edge.end;
}
else
{
return The_edge.begin;
}
}
}
cout << "结点和边不匹配" << '\n';
}
Node& dAnother_node(Node& A, Edge& The_edge)
{
for (int i = 0; i < A.neibor_edge.size(); i++)
{
if (A.neibor_edge[i] == The_edge)
{
if (The_edge.begin == A)
{
return The_edge.end;
}
else
{
return The_edge.begin;
}
}
}
cout << "结点和边不匹配" << '\n';
}
void vAnother_node(Node& A, Edge& The_edge,Node& B)
{
for (int i = 0; i < A.neibor_edge.size(); i++)
{
if (A.neibor_edge[i] == The_edge)
{
if (The_edge.begin == A)
{
B = The_edge.end;
}
else
{
B = The_edge.begin;
}
}
}
}
class Tgrape
{
public:
Tgrape();
~Tgrape();
void inter_node(char x);
void define_node(char pos);
void crease_edge(int first, int second, int weight = 0);
void crease_edge(char first, char second, int weight = 0);
void delete_edge(int sort_);
void delete_edge(int first, int second);
void delete_edge(char first, char second);
Node& founde_point(char sta);
Node found_point(char sta);
bool founde_edge(Edge edg);
void DFS(char start);
void DFS(Node& Start);
void BFS(char start);
bool found(char x);
bool has_visited(Node Current);
void print(Node x);
void print(Edge y);
void print_edge();
void empty_p();
void dprint()
{
dprint(*(node_saver.begin()+4));
}
void dprint(Node Y)
{
print(Y);
for (int i = 0; i < Y.neibor_edge.size(); i++)
{
print(Y.neibor_edge[i]);
dprint(Another_node(Y, Y.neibor_edge[i]));
}
}
private:
vector<Node> node_saver;
vector<Edge> edge_saver;
int node_count;
int edge_count;
bool Type[256] = { false };
bool visited[256] = { false };
};
inline Tgrape::Tgrape()
{
node_count = 0;
edge_count = 0;
}
inline Tgrape::~Tgrape()
{
}
inline void Tgrape::inter_node(char x)
{
if (!found(x))
{
Node New(x, ++node_count);
node_saver.push_back(New);
Type[x] = true;
}
else
{
cout << "含有此信息的结点已经生成,不能再次生成" << '\n';
}
}
inline void Tgrape::define_node(char pos)
{
sort(node_saver.begin(), node_saver.end(), cmp_node);
Node& A = founde_point(pos);
while (!A.neibor_edge.empty())
{
delete_edge(A.inform, Another_node(A, A.neibor_edge[0]).inform);
}
vector<Node>::iterator nit;
nit = find(node_saver.begin(), node_saver.end(), A);
nit = node_saver.erase(nit);
Type[pos] = false;
}
inline void Tgrape::crease_edge(int first, int second, int weight)
{
sort(node_saver.begin(), node_saver.end(), cmp_node);
int th_fir = 0, th_sec = 0;
for (int i = 0; i < node_saver.size(); i++)
{
if (node_saver[i].postion == first)
{
th_fir = i;
}
if (node_saver[i].postion == second)
{
th_sec = i;
}
if (th_fir && th_sec)
{
break;
}
}
Node& A = node_saver[th_fir];
Node& B = node_saver[th_sec];
Edge edg(A, B,++edge_count);
A.neibor_edge.push_back(edg);
B.neibor_edge.push_back(edg);
edge_saver.push_back(edg);
}
inline void Tgrape::crease_edge(char first, char second, int weight)
{
if (found(first) && found(second))
{
Node& A = founde_point(first);
Node& B = founde_point(second);
Edge E(A, B, ++edge_count, weight);
if (!founde_edge(E))
{
A.neibor_edge.push_back(E);
B.neibor_edge.push_back(E);
edge_saver.push_back(E);
}
else
{
cout << "有相同起终点和权重边已经生成,不再重复生产" << '\n';
}
}
else
{
cout << "结点未生成,请先生成结点" << '\n';
}
}
inline void Tgrape::delete_edge(int sort_)
{
sort(edge_saver.begin(), edge_saver.end(), cmp_edge);
int dest = 0;
for (int j = 0; j < edge_saver.size(); j++)
{
if (edge_saver[j].tag == sort_)
{
dest = j;
break;
}
}
Edge& Noe = edge_saver[dest];
Node& A = Noe.begin;
Node& B = Noe.end;
vector<Edge>::iterator ait, bit, eit;
ait = find(A.neibor_edge.begin(), A.neibor_edge.end(), Noe);
bit = find(B.neibor_edge.begin(), B.neibor_edge.end(), Noe);
eit = find(edge_saver.begin(), edge_saver.end(), Noe);
ait = A.neibor_edge.erase(ait);
bit = B.neibor_edge.erase(bit);
eit = edge_saver.erase(eit);
}
inline void Tgrape::delete_edge(int first, int second)
{
}
inline void Tgrape::delete_edge(char first, char second)
{
if (found(first) && found(second))
{
Node& A = founde_point(first);
Node& B = founde_point(second);
for (int y = 0; y < A.neibor_edge.size(); y++)
{
if ((A.neibor_edge[y].begin == A && A.neibor_edge[y].end == B) || (A.neibor_edge[y].begin == B && A.neibor_edge[y].end == A))
{
Edge& The_one = A.neibor_edge[y];
vector<Edge>::iterator ait, bit, eit;
ait = find(A.neibor_edge.begin(), A.neibor_edge.end(), The_one);
bit = find(B.neibor_edge.begin(), B.neibor_edge.end(), The_one);
eit = find(edge_saver.begin(), edge_saver.end(), The_one);
ait = A.neibor_edge.erase(ait);
bit = B.neibor_edge.erase(bit);
eit = edge_saver.erase(eit);
y--;
}
}
sort(A.neibor_edge.begin(), A.neibor_edge.end(), cmp_edge);
sort(B.neibor_edge.begin(), B.neibor_edge.end(), cmp_edge);
sort(edge_saver.begin(), edge_saver.end(), cmp_edge);
}
else
{
cout << "结点还未生成或已经删除,请重新选择" << '\n';
}
}
inline Node& Tgrape::founde_point(char sta)
{
if (found(sta))
{
vector<Node>::iterator it;
for (it = node_saver.begin();it!=node_saver.end();it++)
{
if ((*it).inform == sta)
{
return (*it);
}
}
}
}
inline Node Tgrape::found_point(char sta)
{
if (found(sta))
{
vector<Node>::iterator it;
for (it = node_saver.begin(); it != node_saver.end(); it++)
{
if ((*it).inform == sta)
{
return (*it);
}
}
}
}
inline bool Tgrape::founde_edge(Edge edg)
{
vector<Edge>::iterator it;
for (it = edge_saver.begin(); it != edge_saver.end(); it++)
{
if (*it == edg)
{
return true;
}
}
return false;
}
inline void Tgrape::DFS(char start)
{
fill(visited, visited + 256, false);
vector<Node> Cnode = node_saver;
if (!found(start))
{
cout << "当前结点没有在图内,请先生成此结点" << '\n';
}
else
{
Node S = found_point(start);
DFS(S);
}
}
inline void Tgrape::DFS(Node& Start) //就这里出了问题,DFS('a')只能进行到 与a相连的b,c 再往下就不行了
{
if (!has_visited(Start))
{
visited[Start.inform] = true;
for (int i = 0; i < Start.neibor_edge.size(); i++)
{
Node& B = dAnother_node(Start, Start.neibor_edge[i]);
print(Start.neibor_edge[i]);
DFS(Start);
}
}
else
{
cout << "无向图不是树" << '\n';
return;
}
cout << "无向图是树" << '\n';
}
inline void Tgrape::BFS(char start)
{
}
inline bool Tgrape::found(char x)
{
return Type[x];
}
inline bool Tgrape::has_visited(Node Current)
{
return visited[Current.inform];
}
inline void Tgrape::print(Node x)
{
cout << "信息:" << x.inform << " 位置:" << x.postion << '\n';
}
inline void Tgrape::print(Edge y)
{
cout << "起点:";
print(y.begin);
cout << "终点:";
print(y.end);
cout << "权重" << y.weight << " 编号" << y.tag << '\n';
}
inline void Tgrape::print_edge()
{
for (int i = 0; i < edge_saver.size(); i++)
{
print(edge_saver[i]);
cout << '\n';
}
}
inline void Tgrape::empty_p()
{
Node Start = *node_saver.begin();
print(Start);
for (int i = 0; i < Start.neibor_edge.size(); i++)
{
print(Start.neibor_edge[i]);
print(Another_node(Start, Start.neibor_edge[i]));
for (int j = 0; j < Another_node(Start, Start.neibor_edge[i]).neibor_edge.size(); j++)
{
print(Another_node(Start, Start.neibor_edge[i]).neibor_edge[j]);
print(Another_node(dAnother_node(Start, Start.neibor_edge[i]), Another_node(Start, Start.neibor_edge[i]).neibor_edge[j]));
}
}
}