图的遍历，结点度，图的连通分量

川长思鸟来 2022-04-05 09:53 216阅读 0赞

#include"stdafx.h"
    #include<queue>
    #include<stack>
    #include<string>
    #include<iostream>
    using namespace std;
    enum GraphType
    {
    	UNDIR_UNWEIGHT_GRAPH,//无向无权图
    	UNDIR_WEIGHT_GRAPH,//无向带权图
    	DIR_UNWEIGHT_GRAPH,//有向无权图
    	DIR_WEIGHT_GRAPH//有向带权图
    };
    
    enum ColorType
    {
    	WHITE,
    	GRAY,
    	BLACK
    };
    template<typename VertexType,typename InfoType>
    class Graph
    {
    public:
    	Graph(int vertexNum, int arcNum,GraphType type) :m_vertexNum(vertexNum), m_type(type), m_arcNum(arcNum)
    	{
    		for (int i = 0; i < MAX_VERTEX_NUM; i++)
    		{
    			m_vertices[i].firstArc = nullptr;
    		}
    	}
    	void Create()
    	{
    		switch (m_type)
    		{
    		case UNDIR_UNWEIGHT_GRAPH:
    			CreateUndirUnweightGraph();
    			break;
    		case UNDIR_WEIGHT_GRAPH:
    			CreateUndirWeightGraph();
    			break;
    		case DIR_UNWEIGHT_GRAPH:
    			CreateDirUnWeightGraph();
    			break;
    		case DIR_WEIGHT_GRAPH:
    			CreateDirWeightGraph();
    			break;
    		default:
    			break;
    		}
    	}
    	void Display()
    	{
    		for (int i = 0; i < m_vertexNum; i++)
    		{
    			//cout << "第" << i + 1 << "个结点为" << m_vertices[i].data << " 邻接表为: ";
    			cout << m_vertices[i].data << ":";
    			ArcNode *node = m_vertices[i].firstArc;
    			while (node != nullptr)
    			{
    				if(m_type==GraphType::DIR_WEIGHT_GRAPH||m_type==GraphType::UNDIR_WEIGHT_GRAPH)cout << m_vertices[node->vertexIndex].data << "(" << node->info << ")"<< " " ;
    				else cout << m_vertices[node->vertexIndex].data << " ";
    				node = node->next;
    			}
    			cout << endl;
    		}
    	}
    	void CountNodesDegrees()
    	{
    		vector<NodeDegrees> TheirDegrees;
    		for (int i = 0; i < m_vertexNum; i++)
    		{
    			NodeDegrees bufDgr;
    			bufDgr.Degree = 0;
    			bufDgr.OutDegree = 0;
    			bufDgr.InDegree = 0;
    			
    			ArcNode*node = m_vertices[i].firstArc;
    			while (node != nullptr)
    			{
    				bufDgr.OutDegree += 1;
    				node = node->next;
    			}
    			TheirDegrees.push_back(bufDgr);
    		}//统计出度
    		char bufCh;
    		for (int i = 0; i < m_vertexNum; i++)
    		{
    			ArcNode* node = m_vertices[i].firstArc;
    			while (node != nullptr)
    			{
    				bufCh = m_vertices[node->vertexIndex].data;
    				for (int j = 0; j < VertexStr.size(); j++)
    				{
    					if (VertexStr[j] == bufCh)
    					{
    						TheirDegrees[j].InDegree += 1;
    						break;
    					}
    				}
    				node = node->next;
    			}
    		}
    		for (int i = 0; i < m_vertexNum; i++)
    		{
    			TheirDegrees[i].Degree = TheirDegrees[i].OutDegree + TheirDegrees[i].InDegree;
    			cout << VertexStr[i] << " " << TheirDegrees[i].OutDegree << " " << TheirDegrees[i].InDegree << " "<< TheirDegrees[i].Degree << endl;
    		}
    	}
    	void BFS()
    	{
    		for (int i = 0; i < m_vertexNum; ++i)
    		{
    			m_vertices[i].color = WHITE;
    		}
    		//cout << "图的广度优先遍历为:";
    		BFS(&m_vertices[0]);
    		cout << endl;
    	}
    	void DFS()
    	{
    		for (int i = 0; i < m_vertexNum; i++)
    		{
    			m_vertices[i].color = WHITE;
    		}
    		//cout << "图的深度优先遍历:";
    		DFS(&m_vertices[0],true);
    		cout << endl;
    	}
    	void CountConnectedComponent()
    	{
    		for (int i = 0; i < m_vertexNum; i++)
    		{
    			m_vertices[i].color = WHITE;
    		}
    		bool allvisited = false;
    		int result = 0;
    		while (allvisited==false)
    		{
    			for (int i = 0; i < m_vertexNum; i++)
    			{
    				if (m_vertices[i].color == WHITE)
    				{
    					DFS(&m_vertices[i], false);
    					result++;
    				}
    			}
    			allvisited = true;
    			for (int i = 0; i < m_vertexNum; i++)
    			{
    				if (m_vertices[i].color == WHITE)
    				{
    					allvisited = false; break;
    				}
    			}
    		}
    		cout << result << endl;
    	}
    	void Sort()
    	{
    		for (int i = 0; i < m_vertexNum; i++)
    		{
    			ArcNode* node;
    			ArcNode* mark, *buf;
    			for (node = m_vertices[i].firstArc; node->next != nullptr; node = node->next)
    			{
    				mark = node;
    				for (buf = node->next; buf != nullptr; buf = buf->next)
    				{
    					if (buf->vertexIndex < mark->vertexIndex)mark = buf;
    				}
    				if (mark != node)
    				{
    					swap((*mark).vertexIndex, (*node).vertexIndex);
    					swap((*mark).info, (*node).info);
    				}
    			}
    
    		}
    	}
    	//~Graph();
    
    private:
    	struct ArcNode
    	{
    		int vertexIndex;
    		struct ArcNode* next;
    		InfoType info;
    	};
    	struct Vertex
    	{
    		VertexType data;
    		ArcNode* firstArc;
    		ColorType color;
    	};
    	struct NodeDegrees {
    		int Degree;
    		int OutDegree;
    		int InDegree;
    	};
    	static const int MAX_VERTEX_NUM = 50;
    	Vertex m_vertices[MAX_VERTEX_NUM];
    	int m_vertexNum;
    	int m_arcNum;
    	string VertexStr;
    	GraphType m_type;
    	
    	void InitVertices()
    	{
    		//cout << "请输入每个顶点的关键字" << endl;
    		cin >> VertexStr;
    		/*for (int i = 0; i < VertexStr.size() - 1; i++)
    		{
    			int mark = i;
    			for (int j = i; j < VertexStr.size(); j++)
    			{
    				if (VertexStr[j] < VertexStr[mark])mark = j;
    			}
    			if (mark != i)
    			{
    				swap(VertexStr[i], VertexStr[mark]);
    			}
    		}*/
    		for (int i = 0; i < m_vertexNum; i++)
    		{
    			m_vertices[i].data = VertexStr[i];
    		}
    	}
    
    	void Insert(int headVertex, int tailVertex, InfoType info)
    	{
    		ArcNode* newNode = new ArcNode;
    		newNode->info = info;
    		newNode->next = nullptr;
    		newNode->vertexIndex = tailVertex;
    
    		ArcNode* LastNode = m_vertices[headVertex].firstArc;
    		if (LastNode == nullptr)
    			m_vertices[headVertex].firstArc = newNode;
    		else
    		{
    			while (LastNode->next)
    			{
    				LastNode = LastNode->next;
    			}
    			LastNode->next = newNode;
    		}
    		
    	}
    
    	void CreateUndirUnweightGraph()
    	{
    		InitVertices();
    		//cout << "请分别输入每条边的起始结点:" << endl;
    		string bufferArc;
    		
    		int head, tail;
    		for (int i = 0; i<m_arcNum; i++)
    		{
    			cin >> bufferArc;
    			for (int i = 0; i < VertexStr.size(); i++)
    			{
    				if (VertexStr[i] == bufferArc[0])head = i;
    				else if (VertexStr[i] == bufferArc[1])tail = i;
    			}
    			//无向图插入两次
    			
    			Insert(head, tail, 0);
    			Insert(tail, head, 0);
    		}
    	}
    
    	void CreateUndirWeightGraph()
    	{
    		InitVertices();
    		//cout << "请分别输入每条边的起始结点和权值:" << endl;
    		string bufferArc;
    
    		int head, tail;
    		InfoType weight;
    		for (int i = 0; i<m_arcNum; i++)
    		{
    			cin >> bufferArc;
    			cin >> weight;
    			for (int i = 0; i < VertexStr.size(); i++)
    			{
    				if (VertexStr[i] == bufferArc[0])head = i;
    				else if (VertexStr[i] == bufferArc[1])tail = i;
    			}
    			Insert(head, tail, weight);
    			Insert(tail, head, weight);
    		}
    	}
    	void CreateDirUnWeightGraph()
    	{
    		InitVertices();
    		//cout << "请分别输入每条边的起始结点:" << endl;
    		string bufferArc;
    		int head, tail;
    		for (int i = 0; i < m_arcNum; i++)
    		{
    			cin >> bufferArc;
    			for (int i = 0; i < VertexStr.size(); i++)
    			{
    				if (VertexStr[i] == bufferArc[0])head = i;
    				else if (VertexStr[i] == bufferArc[1])tail = i;
    			}
    			//cout << head << "  " << tail << endl;
    			Insert(head, tail, 0);
    		}
    	}
    	void CreateDirWeightGraph()
    	{
    		InitVertices();
    		//cout << "请输入每条边的起始结点和权值:" << endl;
    		string bufferArc;
    		int head, tail;
    		InfoType weight;
    		for (int i = 0; i<m_arcNum; i++)
    		{
    			cin >> bufferArc;
    			cin  >> weight;
    			for (int i = 0; i < VertexStr.size(); i++)
    			{
    				if (VertexStr[i] == bufferArc[0])head = i;
    				else if (VertexStr[i] == bufferArc[1])tail = i;
    			}
    			
    			Insert(head, tail, weight);
    		}
    	}
    	
    	void BFS(Vertex* vertex)
    	{
    		vertex->color = GRAY;
    		queue<Vertex*> vertices;
    		vertices.push(vertex);
    		while (!vertices.empty())
    		{
    			Vertex* curVertex = vertices.front();
    			vertices.pop();
    			cout << curVertex->data;
    			ArcNode* node = curVertex->firstArc;
    			while (node != nullptr)
    			{
    				Vertex* tmpVertex = &m_vertices[node->vertexIndex];
    				if (tmpVertex->color == WHITE)
    				{
    					tmpVertex->color = GRAY;
    					vertices.push(tmpVertex);
    				}
    				node = node->next;
    			}
    			curVertex->color = BLACK;
    		}
    	}
    	void DFS(Vertex* vertex,bool print)
    	 {
    		 vertex->color = GRAY;
    		stack<Vertex*> vertices;
    		vertices.push(vertex);
    		Vertex* curVertex;
    		while (!vertices.empty())
    		{
    			curVertex = vertices.top();
    			if(curVertex->color==GRAY&&print)cout << curVertex->data;
    			ArcNode* node = curVertex->firstArc;
    			bool flag = false;
    			while (node != nullptr)
    			{
    				Vertex* temp = &m_vertices[node->vertexIndex];
    				if (temp->color == WHITE)
    				{
    					temp->color = GRAY;
    					flag = true;
    					vertices.push(temp);
    					break;
    				}
    				node = node->next;
    			}
    			if (flag == false)vertices.pop();
    			curVertex->color = BLACK;
    		}
    	}
    	 
    };
    int main()
    {
    	int VertexAmount,ArcAmount;
    	cin >> VertexAmount >> ArcAmount;
    	Graph<char,int> G1(VertexAmount,ArcAmount,GraphType::DIR_UNWEIGHT_GRAPH);
    	G1.Create();
    	//G1.Display();
    	//G1.Sort();
    	//G1.Display();
    	//G1.CountNodesDegrees();
    	//G1.DFS();
    	//G1.BFS();
    	G1.CountConnectedComponent();
    	
    	return 0;
    }