目录
DirectedGraph类的构成
构造函数
析构函数
深度优先遍历
广度优先遍历
前文回顾:
[邻接矩阵形式]无向图的建立与深度,广度遍历_☆迷茫狗子的秘密基地☆-CSDN博客目录MGraph类构造函数深度优先遍历广度优先遍历MGraph类const int N = 10;int visit[N]; // 顶点是否被访问template<typename DataType>class MGraph//无向图{public: MGraph(DataType a[], int n, int e); ~MGraph(){} void DF(int x); //深度优先遍历 void BF(int x);https://blog.csdn.net/qq_39391544/article/details/120943744?spm=1001.2014.3001.5501
DirectedGraph类的构成
const int N = 10;
int visit[N];
struct ConnectNode{ //邻接节点的坐标
int site;
ConnectNode* next;
};
template<typename DataType>
struct VertexNode //顶点表
{
DataType value;
ConnectNode* firstEdge;
};
template<typename DataType>
class DirectedGraph{ //有向图
public:
DirectedGraph(DataType a[], int n, int e);
~DirectedGraph();
void DF(int x);
void BF(int x);
private:
VertexNode<DataType> v[N];
int vNum,edgeNum;
};
构造函数
template<typename DataType>
DirectedGraph<DataType>::DirectedGraph(DataType a[], int n, int e):vNum(n),edgeNum(e)
{
for(int i = 0; i < vNum; i++){
v[i].value = a[i];
v[i].firstedge = NULL;
}
int j,k;
ConnectNode* s = NULL;
for(int i = 0; i < edgeNum; i++){
cin >> j >> k;
s = new ConnectNode;
s->site = k;
s->next = v[j].firstEdge;
v[j].firstEdge = s;
}
}
析构函数
template<typename DataType>
DirectedGraph<DataType>::~DirectedGraph()
{
ConnectNode *p = NULL, *q = NULL;
for(int i = 0; i < vNum; i++){
p = q = v[i].firstEdge;
while(p){
p = p->next;
delete q;
q = p;
}
}
}
深度优先遍历
template<typename DataType>
void DirectedGraph<DataType>::DF(int x)
{
cout << v[x].value << endl;
visit[x] = 1;
ConnectNode *p = v[x].firstEdge;
while(p)
{
if(visit[p->site]) DF(p->site);
p = p->next;
}
}
广度优先遍历
template<typename DataType>
void DirectedGraph<DataType>::BF(int x)
{
int Q[N];
int front = -1, rear = -1;
ConnectNode* p = NULL;
cout << v[x].value << endl;
visit[x] = 1;
Q[++rear] = x;
while(front != rear)
{
int t = Q[++front];
p = v[t].firstEdge;
while (p)
{
if(!visit[p->site]){
cout << v[p->site].value << endl;
visit[p->site] = 1;
Q[++rear] = p->site;
}
p = p->next;
}
}
}