d_galgs.h

数据结构c++语言描述stl版 威廉兄弟的好书,值得看,这是配书代码

	return returnValue;
}

// find the minimum spanning tree for the strongly connected digraph g
friend int minSpanTree(graph<T>& g, graph<T>& MST)
{
   // priority queue that stores minInfo objects
   miniPQ<minInfo, less<minInfo> >  minTreePQ;

   // used when inserting minInfo entries
   // into the priority queue or erasing entries
   minInfo vertexData;

   // adj is adjacency set of vertex we are visiting. adjIter
	// is an iterator that scans the list
	set<neighbor> adj;
   set<neighbor>::iterator adjIter;

	// size of the minimum spanning tree
	int minSpanTreeSize = 0, i;

	// index of a starting vertex.
	int pos_sVertex = -1, currPos, destPos, parentPos;

	// current minimum total weight for spanning tree
   int minSpanTreeWeight = 0;

	// initialize all vertices unmarked and their dataValue fields
	// to infinity;  select the first vertex as the	starting vertex;
	for (i = 0;i < g.vInfo.size(); i++)
		if (g.vInfo[i].occupied)
		{
			if (pos_sVertex == -1)
				pos_sVertex = i;
			g.vInfo[i].color = vertexInfo<T>::WHITE;
			g.vInfo[i].dataValue = INFINITY;
		}

   // create minInfo object for starting vertex
   vertexData.endV = pos_sVertex;

   // total weight of spanning tree with only the
	// starting vertex is 0
   vertexData.pathWeight = 0;

	// update dataValue in vInfo and set rVertex as parent
	g.vInfo[pos_sVertex].dataValue = 0;
	g.vInfo[pos_sVertex].parent = pos_sVertex;

	// insert starting vertex into the priority queue
   minTreePQ.push(vertexData);

   // add vertices until we span the entire graph
	for (;;)
   {
      // delete a priority queue entry
      vertexData = minTreePQ.top();
      minTreePQ.pop();
		currPos = vertexData.endV;

		// if vertex is not part of the new graph (unvisited)
		// add the weight of the edge to the total tree we3ight
		// and increment the number of vertices in the tree
		if (g.vInfo[currPos].color == vertexInfo<T>::WHITE)
		{
			minSpanTreeWeight += vertexData.pathWeight;
			minSpanTreeSize++;

			// if we spanned all vertices, break
			if (minSpanTreeSize == g.numberOfVertices())
				break;

			// mark the vertex BLACK so we don't look at it again.
			// set dataValue in vInfo vector to current
			// minimum tree weight
			g.vInfo[currPos].color = vertexInfo<T>::BLACK;

			// find all unmarked neighbors of the vertex.
			// adjIter is a set iterator pointing at the edge corresponding to
			// vertices with index currPos and destPos
			adj = g.vInfo[currPos].edges;
			for(adjIter = adj.begin();adjIter != adj.end();	adjIter++)
			{
				destPos = (*adjIter).dest;

				// if neighbor is unmarked, check whether adding the new
				// edge to the tree is better than using the current edge
				if (g.vInfo[destPos].color == vertexInfo<T>::WHITE)
				{
					if ((*adjIter).weight < g.vInfo[destPos].dataValue)
					{
						// if new edge is a better connection, create minInfo object
						// for new vertex. update dataValue and parent variables
						// in vertexInfo
						vertexData.endV = destPos;
						vertexData.pathWeight = (*adjIter).weight;
						g.vInfo[destPos].dataValue = (*adjIter).weight;
						g.vInfo[destPos].parent = currPos;
						minTreePQ.push(vertexData);
					}
				}
			}
		}
	}

	// vertices for edges in MST
	T vA, vB;

	// clear tree and then add all of the vertices
   MST.clear();

	for(i = 0; i < g.vInfo.size(); i++)
		if (g.vInfo[i].occupied)
			MST.insertVertex((*(g.vInfo[i]).vtxMapLoc).first);

	// add the edges to the minimum spanning tree
	for (i = pos_sVertex+1; i < g.vInfo.size(); i++)
		if (g.vInfo[i].occupied)
		{
			parentPos = g.vInfo[i].parent;
			vA = (*(g.vInfo[parentPos]).vtxMapLoc).first;
			vB = (*(g.vInfo[i]).vtxMapLoc).first;
			MST.insertEdge(vA,vB, g.getWeight(vA,vB));
		}

   return minSpanTreeWeight;
}

// determine if the graph is acyclic
friend bool acyclic(graph<T>& g)
{
	int i;
	// use for calls to dfsVisit()
	list<T> dfsList;

	// initialize all vertices to WHITE
	for (i=0;i < g.vInfo.size(); i++)
		if (g.vInfo[i].occupied)
			g.vInfo[i].color = vertexInfo<T>::WHITE;

	// scan vInfo, calling dfsVisit() for each WHITE vertex.
	// catch a graphError exception in a call to dfsVisit()
	try
	{
		for (i=0;i < g.vInfo.size(); i++)
			if (g.vInfo[i].occupied && g.vInfo[i].color ==
												vertexInfo<T>::WHITE)
					dfsVisit(g,(*(g.vInfo[i].vtxMapLoc)).first,
									 dfsList, true);
	}

	catch (const graphError&)
	{
		return false;
	}

	return true;
}

// this algorithm is a private friend of the graph class
private:

// depth-first visit assuming a WHITE starting vertex. dfsList
// contains the visited vertices in reverse order of finishing time.
// when checkForCycle is true, the function throws an exception if
// it detects a cycle
friend void dfsVisit(graph<T>& g, const T& sVertex, list<T>& dfsList,
							bool checkForCycle)
{
	// indices for vertex positions in vInfo
	int pos_sVertex, pos_neighbor;

	// iterator to scan the adjacency set of a vertex
	set<neighbor>::iterator adj;

	// alias to simplify access to the vector vInfo
	vector<vertexInfo<T> >& vlist = g.vInfo;

	// fetch the index for sVertex in vInfo; throw an exception
	// if the starting vertex is not in the graph
	pos_sVertex = g.getvInfoIndex(sVertex);

	if (pos_sVertex == -1)
		throw graphError("graph dfsVisit(): vertex not in the graph");

	// color vertex GRAY to note its discovery
	vlist[pos_sVertex].color = vertexInfo<T>::GRAY;

	// create an alias for the adjacency set of sVertex
	set<neighbor>& edgeSet = vlist[pos_sVertex].edges;

	// sequence through the adjacency set and look for vertices
	// that are not yet discovered (colored WHITE). recursively call
	// dfsVisit() for each such vertex. if a vertex in the adjacency
	// set is GRAY, the vertex was discovered during a previous
	// call and there is a cycle that begins and ends at the
	// vertex; if checkForCycle is true, throw an exception
	for (adj = edgeSet.begin(); adj != edgeSet.end(); adj++)
	{
		pos_neighbor = (*adj).dest;
		if (vlist[pos_neighbor].color == vertexInfo<T>::WHITE)
			dfsVisit(g,(*(g.vInfo[pos_neighbor].vtxMapLoc)).first,
							 dfsList, checkForCycle);
		else if (vlist[pos_neighbor].color == vertexInfo<T>::GRAY
					&& checkForCycle)
			throw graphError("graph dfsVisit(): graph has a cycle");
	}

	// finished with vertex sVertex. make it BLACK and add it to
	// the front of dfsList
	vlist[pos_sVertex].color = vertexInfo<T>::BLACK;
	dfsList.push_front((*(g.vInfo[pos_sVertex].vtxMapLoc)).first);
}

// return to the public section for the remaining algorithms
public:

// depth-first search. dfsList contains all the graph vertices in the
// reverse order of their finishing times
friend void dfs(graph<T>& g, list<T>& dfsList)
{
	int i;

	// clear dfsList
	dfsList.erase(dfsList.begin(), dfsList.end());

	// initialize all vertices to WHITE
	for (i=0;i < g.vInfo.size(); i++)
		if (g.vInfo[i].occupied)
			g.vInfo[i].color = vertexInfo<T>::WHITE;

	// scan vInfo, calling () dfsVisit() for each WHITE vertex.
	for (i=0;i < g.vInfo.size(); i++)
		if (g.vInfo[i].occupied && g.vInfo[i].color ==
											vertexInfo<T>::WHITE)
			dfsVisit(g,(*(g.vInfo[i].vtxMapLoc)).first, dfsList, false);
}

// find a topological sort of an acyclic graph
friend void topologicalSort(graph<T>& g, list<T>& tlist)
{
	int i;

	// clear the list that will contain the sort
	tlist.erase(tlist.begin(), tlist.end());

	for (i=0;i < g.vInfo.size(); i++)
		if (g.vInfo[i].occupied)
			g.vInfo[i].color = vertexInfo<T>::WHITE;

	// cycle through the vertices, calling dfsVisit() for each
	// WHITE vertex. check for a cycle
	try
	{
		for (i=0;i < g.vInfo.size(); i++)
			if (g.vInfo[i].occupied && g.vInfo[i].color == vertexInfo<T>::WHITE)
				dfsVisit(g, (*(g.vInfo[i].vtxMapLoc)).first, tlist, true);
	}

	catch(graphError&)
	{
		throw graphError("graph topologicalSort(): graph has a cycle");
	}
}

// return the transpose of the graph
friend graph<T> transpose(graph<T>& g)
{
	int i, n = g.vInfo.size();
	set<neighbor>::iterator setIter;
	// initialize gt as a copy of g
	graph<T> gt = g;

	// clear the adjacency set of each vertex in gt and set the in-degree
	// of each vertex to 0
	for (i=0;i < n;i++)
	{
		gt.vInfo[i].edges.erase(gt.vInfo[i].edges.begin(),
										gt.vInfo[i].edges.end());
		gt.vInfo[i].inDegree = 0;
	}

	// assign the edges of gt as the reverse of those in g
	for (i=0; i < n; i++)
		if (g.vInfo[i].occupied)
		{
			set<neighbor>& s = g.vInfo[i].edges;

			// edge from index i to index dest in vInfo for g must be an edge
			// from dest to i with the same weight in gt. increment the in-degree
			// at index i
			for (setIter = s.begin(); setIter != s.end(); setIter++)
			{
				gt.vInfo[(*setIter).dest].edges.insert(neighbor(i,(*setIter).weight));
				gt.vInfo[i].inDegree++;
			}
		}

	return gt;
}

// find the strong components of the graph
friend void strongComponents(graph<T>& g, vector<set<T> >& component)
{
	// list of vertices visited by dfs() for graph g
	list<T> dfsGList;

	// list of vertices visited by dfsVisit() for g transpose
	list<T> dfsGTList;

	// used to scan dfsGList and dfsGTList objects
	list<T>::iterator gIter, gtIter;

	// transpose of the graph
	graph<T> gt;

	// set for an individual strong component
	set<T> scSet;

	int i;

	// clear the return vector
	component.resize(0);

	// execute depth-first tranversal of g
	dfs(g, dfsGList);

	// compute gt
	gt = transpose(g);

	// initialize all vertices in gt to WHITE (unvisited)
	for (i=0;i < gt.vInfo.size(); i++)
		if (gt.vInfo[i].occupied)
			gt.vInfo[i].color = vertexInfo<T>::WHITE;

	// call dfsVisit() for gt from vertices in dfsGList
	gIter = dfsGList.begin();
	while(gIter != dfsGList.end())
	{
		// call dfsVisit() only if vertex has not been visited
		if (gt.vInfo[gt.getvInfoIndex(*gIter)].color ==
						 vertexInfo<T>::WHITE)
		{
			// clear dfsGTList and scSet
			dfsGTList.erase(dfsGTList.begin(), dfsGTList.end());
			scSet.erase(scSet.begin(), scSet.end());

			// do dfsVisit() in gt for starting vertex *gIter
			dfsVisit(gt, *gIter, dfsGTList, false);

			// copy vertices from the list to set scSet
			for (gtIter = dfsGTList.begin(); gtIter != dfsGTList.end();
								gtIter++)
				scSet.insert(*gtIter);

			// add strong component set to the vector
			component.push_back(scSet);
		}
		gIter++;
	}
}