Data-Structure/AdjList.h at master · KiAlexander/Data-Structure · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
struct VertexNode {
	char vertex;
	ArcNode*firstarc;
};
struct ArcNode {
	int Adjvex;
	ArcNode* nextarc;
};
const int MAXSIZE = 10;
template<class T>class AlGraph
{
public:
	AlGraph(T a[], int n, int e);
	~AlGraph();
	void DFS(int v);  //深度优先遍历
	void BPS(int v);  //广度优先遍历
private:
	VertexNode adjlist[MAXSIZE];
	int        vNum, arcNum;
};
//构造函数，建立无向图的算法
template<class T>AlGraph<T>::AlGraph(T a[], int n, int e)
{
	int i, j, k;
	vNum = n;
	arcNum = e;
	for (k = 0;k < n;k++)
	{
		adjlist[k].vertex = a[k];
		adjlist[k].firstarc = NULL;
	}
	for (k = 0;k < e;k++)
	{
		cin >> i >> j;
		ArcNode*s = new ArcNode;
		s->Adjvex = j;
		s->nextarc = adjlist[i].firstarc;
		adjlist[i].firstarc = s;
	}
}
//深度优先遍历
template<class T>
void AlGraph<T>::DFS(int v)
{
	cout << adjlist[v].vertex;
	visited[v] = true;
	ArcNode*p = adjlist[v].firstarc;
	while (p)
	{
		int j = p->adjvex;
		if (!visited[j])
		   DFS(j);
		p = p->nextarc;
	}
}
//广度优先遍历
template< class T>
void AlGraph<T>::BPS(int v)
{
	int queue[MAXSIZE];
	int f = 0, r = 0;
	cout << adjlist[v].vertex;
	visted[v] = true;
	queue[++r] = v;
	while (f!=r)
	{
		v = queue[++f];
		ArcNode*p = adjlist[v].firstarc;
		while (p)
		{
			int j = p->Adjvex;
			if (!visited[j])
			{
				cout << adjlist[j].vertex;
				visited[j] = true;
				queue[++r] = j;
			}
			p=p->nextarc
		}
	}
}
//普利姆算法
void Prim()