再发邻接表实现的带权无向图的抽象数据类型,及其相关算法的实现,(oop)大家多探讨:
涉及到的成员函数实现的算法在类的声明中已经详细列出了,大家参考,这里基本涉及到了我们常见的无向图的所有算法:#ifndef GRAPHLINK_H
#define GRAPHLINK_H
#include"BaseGraph.h"
#include<iostream.h>
#include<stdlib.h>
#include"LinkedQueue.h"
#include"GenTree.h"
#include"Forest.h"
/////////////////////////////////////////////////
//Edge 边结点结构的定义
/////////////////////////////////////////////////
template<class T,class E>
struct Edge
{
int dest; //目的结点的结点号
E cost; //边对应的权值
Edge<T,E>* link; //下一条边结点的指针
Edge(){}; //默认构造函数
Edge(int num,E weight)//带参数的构造函数
:dest(num),cost(weight),link(NULL){};
bool operator!=(Edge<T,E>& R)const
{ //成员重载运算符
if(R.dest==dest) //判断两个边结点是否相等
return true;
else
return false;
};
};
///////////////////////////Edge边结点结构定义结束
/////////////////////////////////////////////////
//Vertex结构 图的顶点结点的定义
/////////////////////////////////////////////////
template<class T,class E>
struct Vertex
{
T data; //结点的数据域
Edge<T,E>* adj;//边链表的首指针
};
///////////////////////////Vertex顶点结构定义结束
/////////////////////////////////////////////////
//Graphlink<T,E>类模板的实现
//以邻接链表方式实现的图的类模板的声明和实现
//该类以Graph<T,E>为虚基类
//T是顶点数据域类型,E是边的权值类型
/////////////////////////////////////////////////
template<class T,class E>
class Graphlink:public Graph<T,E>
{
private:
Vertex<T,E>* NodeTable; //顶点表数组
int getVertexPos(const T vertex) //给出指定顶点Vertex的结点号
{
for(int i=0;i<numVertices;i++) //遍历所有的邻接顶点
if(NodeTable[i]==vertex)
return i;
return -1; //没有找到
};
bool* visited; //用于标记第i个结点是否被访问的数组
void DFS(int start); //递归:深度优先遍历本图,start是起始结点
int* Path; //用于存放最短路径的辅助数组
public:
Graphlink(int sz=DefaultVertices); //默认构造函数
~Graphlink(); //析构函数
T getValue(int i) //取结点号为i的结点里的数据
{
if(i>=0 && i<maxVertices)
return NodeTable[i].data;
else
return 0;
};
E getWeight(int v1,int v2); //取得边(v1,v2)上的权值
bool insertVertex(const T vertex); //在图中插入一个顶点vertex
bool removeVertex(int v); //在图中删除指定结点号v的结点
bool insertEdge(int v1,int v2,E cost); //插入一条边以及对应的权值
bool removeEdge(int v1,int v2); //删除边(v1,v2)
int getFirstNeighbor(int v); //取得结点v的第一个邻接结点
int getNextNeighbor(int v,int w); //取得v的邻接结点中w后的那个邻接结点
void DFSGraphic(int start); //深度优先遍历当前图所有结点
void BFSGraphic(); //广度优先遍历
void Find_Connected_Component(); //求图的所有的连通分量顶点集
TreeNode<T>* DFSTree(int v); //递归:得到以v为出发点的深度优先生成树TS
void DisplayDFSTree(int v); //调用上面的递归函数求图的深度优先生成树
TreeNode<T>* DFSForest(int v); //则求其所有连通分量的的深度优先生成森林
void Find_DFSForest(int v) //得到非连通图的深度优先生成森林
{
Forest<char> F;
F.setRoot(DFSForest(0));
cout<<"深度优先生成森林是:"<<endl;
F.Display();
};
int getFirstUnvisit(int p,bool* visited); //得到当前未访问的第一个邻接结点
int getNextUnvisit(int p,int v,bool* visited);//得到下个未访问的邻接结点
void DepthFirst(int start); //非递归深度优先遍历当前图
void Dijkstra(int v); //求v到其他顶点的最短路径
void DisplayPath(int v,E* d); //显示当前图中从顶点v到其他所有顶点的最短路径
int DFSArticul(int v0,int* dfn,int* low); //递归:从顶点v0出发DFS当前图,查找并输出关节点
void FindArticul(); //找出当前图中所有的关节点
//友元重载输出运算符
friend ostream& operator<<(ostream& os,Graphlink<T,E>& G);
//友元重载输入运算符
friend istream& operator>>(istream& is,Graphlink<T,E>& G);
};
/////////////////////Graphlink<T,E>类模板声明结束
