DFS的实现（邻接链表的图）

梦里梦外; 2022-02-02 13:27 168阅读 0赞

直接上代码：

void linkedDgraph1::DFS_VISIT(linkedDgraph1 &G1,int u)
    {
    	time += 1;
    	dTime[u] = G1.dTime[u]=time;
    	color[u] = GRAY;
    	graphNode<int> *p = Adj[u].first();
    	while (p != NULL)
    	{
    		int v = p->element;
    		if (color[v] == WHITE)//如果点是白色的
    		{
    			precursor[v] = u;
    			DFS_VISIT(G1, v);
    			G1.insertEdge(u, v,1);
    			//cout << u << "-->" << v << endl;
    		}
    		p = p->next;
    	}
    	color[u] = BLACK;
    	time += 1;
    	fTime[u] = G1.fTime[u]=time;
    }
    
    void linkedDgraph1::DFS(linkedDgraph1 &G1)
    {
    	 time = 0;//计时器
    	for (int i = 0; i < verticeNumber; i++)
    	{
    		if (color[point[i]] == WHITE)
    		{
    			DFS_VISIT(G1,point[i]);
    		}
    		
    	}
    }

再附上这个图的类的定义及构造函数：

class linkedDgraph1
    {
    public:
    	linkedDgraph1(int num);//构造函数 
    	//~linkedDgraph1();//析构函数 
    	int numberOfVertices();// 顶点个数 
    	int numberOfEdges();//边的个数 
    	bool existsEdge(int, int);//存在顶点 
    	void insertEdge(int, int, int);//插入边 
    	void insertVertice(int);
    	void eraseEdge(int, int);//删除边 
    	void erasePoint(int);//删除顶点 
    	int getWeight(int, int);//获取权重 
    	int degree(int);//顶点的总度数 
    	int inDegree(int);//顶点的入度 
    	int outDegree(int);//顶点的出度 
    	bool topologicalOrder(int *);//拓扑排序 
    	int course(int **);//课程安排 
    	void shortPaths(int, int *, int *);//最短路径 
    	void output();//输出点和边
    	void DFS(linkedDgraph1 &G1);//深度优先搜索
    	void DFS_VISIT(linkedDgraph1 &G1,int u);
    	void DFS_Articulution(vector<int> &articulution);//寻找一个图的衔接点
    	void DFS_Articulution_visit(int u,vector<int> &articulution);
    	int DFS_subVerticeNumber(int);//dfs遍历后的子节点数
    private:
    	int *point;// 顶点集 
    	int verticeNumber;//顶点的数量 
    	int edgeNumber;	//边的数量 
    	int num1;//初始顶点数 
    	graphChain<int> *Adj;//邻接链表 
    	int time;//计时器
    	Color *color;//顶点颜色集
    	int *dTime;//开始时间集
    	int *fTime;//结束时间集
    	int *precursor;//前驱点
    	int *low;//
    };
    linkedDgraph1::linkedDgraph1(int num)
    {
    	verticeNumber = 0;
    	num1 = num;
    	edgeNumber = 0;
    	point = new int[10000];
    	color = new Color[1000];
    	dTime = new int[10000];
    	fTime = new int[10000];
    	precursor = new int[10000];
    	low = new int[10000];
    	for (int i = 0; i < 10000; i++)
    	{
    		point[i] = 0;
    		color[i] = WHITE;
    		dTime[i] = 0;
    		fTime[i] = 0;
    		precursor[i] = 0;
    		low[i] = 0;
    	}
    	Adj = new graphChain<int>[10000];
    }