有向图的创建以及遍历

有向图的创建有很多种方法，这里简要介绍邻接表的创建，以及通过邻接表创建的有向图进行深度优先算法以及广度优先算法

可以先看看，具体文件的格式，大家想要实现的话，需要在桌面上创建一个txt格式的文件，然后将其命名为linjiebiao

5 7
v1 v2 v3 v4 v5
0 1 0 3
1 4
2 3 2 4
3 2
4 0

文件里面的内容是这样的，第一行，写入节点个数和边数，第二行是各个节点的名称，第三行到最后一行，写下从第几个节点到底几个节点的边

例如0 3 表示的是从第“0”到第“3”。对应的就是节点v1到节点v2，那么0 1 0 3综合起来表示的就是v1这个节点有向的连接到了v2和v3。

先给出代码 ，需要注意的是这个代码，只适用于有向图，而且在txt文件当中，必须每个节点可以指向这个节点的边，才可以 遍历所有的节点。那么对应于这个文件当中，就是第二个元素必须得包含所有节点，也就是0、1、2、3、4必须得都有

#include<iostream>
#include<fstream>
#include<string>

using namespace std;

const int MAXSIZE = 10;//定义图节点的最多个数


struct ArcNode
{
	int adjvex;
	ArcNode* nextare;
};

struct VertexNode
{
	string vertex;
	ArcNode* firststare;
};



template<class T>class ALGraph
{
public:
	ALGraph(ifstream& fin);
	~ALGraph();
	void DFS(int v);
	void BFS(int v);
private:
	VertexNode adjlist[MAXSIZE];
	int vNUM, arcNUM;
	bool visited[MAXSIZE];
};

int main()
{
	ifstream fin;
	fin.open("C:/Users/WuFRi/Desktop/linjiebiao.txt");
	if (!fin)
	{
		cerr << "error opening file." << endl;
		return 1;
	}
	ALGraph<string> a(fin);
	//a.DFS(0);
	a.BFS(0);
	system("pause");
	return 0;
}

template<class T>
ALGraph<T>::ALGraph(ifstream& fin)
{
	for (int i = 0; i < MAXSIZE; i++)
	{
		visited[i] = 0;
	}
	fin >> vNUM >> arcNUM;
	if (vNUM > MAXSIZE)
	{
		cerr << "there is no enough place for the node." << endl;
	}
	for (int i = 0; i < vNUM; i++)
	{
		fin >> adjlist[i].vertex;//输入每一个adjlist的名称
		adjlist[i].firststare = NULL;
	}
	for (int k = 0; k < arcNUM; k++)
	{
		int i, j;
		fin >> i >> j;
		ArcNode* newNode = new ArcNode;
		newNode->adjvex = j;//输入每一个节点相连的节点数字标记
		newNode->nextare = NULL;
		if (adjlist[i].firststare == NULL)
		{
			adjlist[i].firststare = newNode;
		}
		else
		{
			ArcNode* last = adjlist[i].firststare;
			while (last->nextare != NULL)
			{
				last = last->nextare;
			}
			last->nextare = newNode;
		}
	}
}

template<class T>
ALGraph<T>::~ALGraph()
{
	for (int i = 0; i < vNUM; i++) {
		ArcNode* p = adjlist[i].firststare;
		while (p) {
			ArcNode* temp = p;
			p = p->nextare;
			delete temp;
		}
	}
}

template<class T>
void ALGraph<T>::DFS(int v)
{
	cout << adjlist[v].vertex;
	visited[v] = 1;
	ArcNode* p = adjlist[v].firststare;
	while (p)
	{
		int j = p -> adjvex;
		if (visited[j] == 0)
		DFS(j);
		p = p->nextare;
	}
}

template<class T>
void ALGraph<T>::BFS(int v)//广度优先算法
{
	int queue[MAXSIZE];//创建一个储存节点的队列
	int f = 0, r = 0;
	cout << adjlist[v].vertex;
	visited[v] = 1;
	queue[++r] = v;
	while (f != r)
	{
		v = queue[++f];
		ArcNode* p = adjlist[v].firststare;
		while (p)
		{
			int j = p->adjvex;
			if (visited[j] == 0)
			{
				cout << adjlist[j].vertex;
				visited[j] = 1;
				queue[++r] = j;
			}
			p = p->nextare;
		}
	}
}