头文件和定义

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <assert.h>
#include <string>
//#include "SeqQueue.h"
//#include "LinkStack.h"
using namespace std;
#define INFINITY 1000000
struct Graph{
	int vCount,eCount;
	string *vers;
	int **matrix;
	bool isDirect,isHaveWeight;
};

搜索顶点

1
2
3
4
5
6
7
8
//search vertex
int GraphLocate(Graph g,string v)
{
	for(int i=0;i<g.vCount;i++)
		if(g.vers[i]==v)
			return i;
	return -1;
}

创建图

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
//create
void GraphCreate(Graph &g)
{
	cout<<"input Graph type:";
	cin>>g.isDirect;
	cin>>g.isHaveWeight;
	cout<<"input vCount:";
	cin>>g.vCount;
	//create vers
	cout<<"input vers:";
	g.vers=new string[g.vCount];
	for(int i=0;i<g.vCount;i++)
		cin>>g.vers[i];
	//init matrix
	g.matrix=new int*[g.vCount];
	for(int j=0;j<g.vCount;j++)
		g.matrix[j]=new int[g.vCount];
	for(int a=0;a<g.vCount;a++)
		for(int b=0;b<g.vCount;b++)
		if(g.isHaveWeight==1)
			g.matrix[a][b]=INFINITY;
		else
			g.matrix[a][b]=0;
	//add edge
	cout<<"input eCount:";	cin>>g.eCount;
	string v1,v2;	int weight;
	for(int q=0;q<g.eCount;q++)	{
		cout<<"input the edges of "<<q+1<<":";
		cin>>v1>>v2;
		if(g.isHaveWeight==1)
			cin>>weight;
		else
			weight=1;
		g.matrix[GraphLocate(g,v1)][GraphLocate(g,v2)]=weight;
		if(g.isDirect==0)
			g.matrix[GraphLocate(g,v2)][GraphLocate(g,v1)]=weight;
	}
}

打印函数1

1
2
3
4
5
6
7
8
9
void GraphPrint(Graph &g)
{
    for(int i = 0; i < g.vCount; i++) {
        for(int j = 0; j < g.vCount; j++) {
            cout << g.matrix[i][j] << " ";
        }
    }
}

虽然我们成功得到了结果，但是不是很美观。

打印函数2

1
2
3
4
5
6
7
8
9
10
void GraphPrint(Graph &g)
{
	cout << endl; //这个是头部换行
    for(int i = 0; i < g.vCount; i++) {
        for(int j = 0; j < g.vCount; j++) {
            cout << g.matrix[i][j] << " ";
        }
        cout << endl; //这个是在每一段结束后换行
    }
}

在头部加入一个换行，并且在每一段结束的时候也加上换行，这样是不是已经很美观了。

测试函数和主函数

1
2
3
4
5
6
7
8
9
10
11
void GraphCreateTest()
{
	Graph g;
	GraphCreate(g);
	GraphPrint(g);
}

int main(){
	 GraphCreateTest();
	 system("pause");
}

图的创建完整代码

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
#include <iostream>
#include <assert.h>
#include <string>
//#include "SeqQueue.h"
//#include "LinkStack.h"
using namespace std;
#define INFINITY 1000000
struct Graph{
	int vCount,eCount;
	string *vers;
	int **matrix;
	bool isDirect,isHaveWeight;
};

//search vertex
int GraphLocate(Graph g,string v)
{
	for(int i=0;i<g.vCount;i++)
		if(g.vers[i]==v)
			return i;
	return -1;
}
//create
void GraphCreate(Graph &g)
{
	cout<<"input Graph type:";
	cin>>g.isDirect;
	cin>>g.isHaveWeight;
	cout<<"input vCount:";
	cin>>g.vCount;
	//create vers
	cout<<"input vers:";
	g.vers=new string[g.vCount];
	for(int i=0;i<g.vCount;i++)
		cin>>g.vers[i];
	//init matrix
	g.matrix=new int*[g.vCount];
	for(int j=0;j<g.vCount;j++)
		g.matrix[j]=new int[g.vCount];
	for(int a=0;a<g.vCount;a++)
		for(int b=0;b<g.vCount;b++)
		if(g.isHaveWeight==1)
			g.matrix[a][b]=INFINITY;
		else
			g.matrix[a][b]=0;
	//add edge
	cout<<"input eCount:";	cin>>g.eCount;
	string v1,v2;	int weight;
	for(int q=0;q<g.eCount;q++)	{
		cout<<"input the edges of "<<q+1<<":";
		cin>>v1>>v2;
		if(g.isHaveWeight==1)
			cin>>weight;
		else
			weight=1;
		g.matrix[GraphLocate(g,v1)][GraphLocate(g,v2)]=weight;
		if(g.isDirect==0)
			g.matrix[GraphLocate(g,v2)][GraphLocate(g,v1)]=weight;
	}
}

void GraphPrint(Graph &g)
{
	cout << endl; 
    for(int i = 0; i < g.vCount; i++) {
        for(int j = 0; j < g.vCount; j++) {
            cout << g.matrix[i][j] << " ";
        }
        cout << endl; 
    }
}

void GraphCreateTest()
{
	Graph g;
	GraphCreate(g);
	GraphPrint(g);
}

int main(){
	 GraphCreateTest();
	 system("pause");
}

如何输入

  • input Graph type（类型）
    • 第一次输入
      • 0 无向图
      • 1 有向图
    • 第二次输入
      • 0 无权图
      • 1 有权图
  • input vCount（顶点数）
    • 输入顶点数（任意整数）
  • input vers（顶点的参数）
    • v1,v2,v3,v4,v5,v6……
  • input eCount（边数）
    • 输入边数（任意整数）
  • input the edges of（输入每一条从哪里到哪里）
    • 输入示范
      • v1（换行）
      • v3 （换行后进入下一次输入）

注意：如果是带权的需要输入三个数值，第三次输入的内容是边数的权值，不带权的只需要输入两次。

Tips：可以一次性全部输入，不需要一条条慢慢输，但是这也带来了一个问题，输出会粘在一行，我头部的换行就是为了这个准备的。

示例

DFS（深度优先搜索）

代码 1

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
//DFS init
void GraphDFSbyRec(Graph &g,string v,bool *&isVisited)
{
    cout<< "" <<v;
    isVisited[GraphLocate(g,v)] = true;
    for (int i = 0; i <g.vCount; i++)
    {
        if (g.matrix[GraphLocate(g,v)][i]!=0 && isVisited[i]==false)
        {
			cout << " -> ";
            GraphDFSbyRec(g,g.vers[i],isVisited);
        }
        
    }
    
}

//DFS
void GraphDFS(Graph &g,string v)
{
    bool *isVisited = new bool [g.vCount];
    for (int i = 0; i < g.vCount; i++)
    {
        isVisited[i]=false;
    }
    cout<< "DFS: ";
    GraphDFSbyRec(g,v,isVisited);
    cout << endl;
}

代码 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void GraphDFSbyRec(Graph &g, string v,bool *&isVisited)
{
	cout<<" "<<v;
	isVisited[GraphLocate(g,v)]=true;
	for(int i=0;i<g.vCount;i++)
		if(g.matrix[GraphLocate(g,v)][i]!=0 && isVisited[i]==false)
			GraphDFSbyRec(g,g.vers[i],isVisited);
}

void GraphDFS(Graph &g,string v)
{
	bool *isVisited=new bool[g.vCount];
	for(int i=0;i<g.vCount;i++)
		isVisited[i]=false;
	cout<<"DFS:";
	GraphDFSbyRec(g,v,isVisited);
	cout<<endl;
}

BFS（广度优先搜索）

注意：使用BFS算法时你需要导入SeqQueue.h这个头文件使用里面结构体以及声明和定义，在我的GitHub中有一份。如果编译报错请删除或者注释掉SeqQueue的main方法，因为g++在编译时不支持两个main方法同时存在，引入的文件只可以当作定义或者结构体使用。

SeqQueue.cpp

代码 1

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
//BFS init
void GraphBFS_init(Graph &g, string v, bool *&isVisited, SeqQueue &q) {
    isVisited = new bool[g.vCount];
	cout << "BFS: ";
    for (int i = 0; i < g.vCount; i++) {
        isVisited[i] = false;
    }
    cout << "" << v;
    isVisited[GraphLocate(g, v)] = true;
    SeqQueueIn(q, GraphLocate(g, v));
}

//BFS
void GraphBFS(Graph &g, string v, bool *&isVisited, SeqQueue &q) {
    while (!SeqQueueEmpty(q)) {
        int cur = SeqQueueFront(q);
        SeqQueueOut(q);
        for (int i = 0; i < g.vCount; i++) {
            if (g.matrix[cur][i] != 0 && !isVisited[i]) {
                cout << " -> " << g.vers[i];
                isVisited[i] = true;
                SeqQueueIn(q, i);
            }
        }
    }
	cout << endl;
}

代码2

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
void GraphBFSinit(Graph &g, string v) {
    bool *isVisited = new bool[g.vCount];
    for (int i = 0; i < g.vCount; i++) {
        isVisited[i] = false;
    }
    SeqQueue q;
    SeqQueueInit(q, 10);
    cout << " " << v;
    isVisited[GraphLocate(g, v)] = true;
    SeqQueueIn(q, GraphLocate(g, v));
    GraphBFS(g, isVisited, q);
    delete[] isVisited;
}

void GraphBFS(Graph &g, bool *&isVisited, SeqQueue &q) {
    while (!SeqQueueEmpty(q)) {
        int cur = SeqQueueFront(q);
        SeqQueueOut(q);
        for (int i = 0; i < g.vCount; i++) {
            if (g.matrix[cur][i] != 0 && !isVisited[i]) {
                cout << " " << g.vers[i];
                isVisited[i] = true;
                SeqQueueIn(q, i);
            }
        }
    }
    cout << endl;
}

结尾

完整代码 1

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>
#include <assert.h>
#include <string>
#include "SeqQueue.h"
//#include "LinkStack.h"
using namespace std;
#define INFINITY 1000000
struct Graph{
	int vCount,eCount;
	string *vers;
	int **matrix;
	bool isDirect,isHaveWeight;
};

//search vertex
int GraphLocate(Graph g,string v)
{
	for(int i=0;i<g.vCount;i++)
		if(g.vers[i]==v)
			return i;
	return -1;
}
//create
void GraphCreate(Graph &g)
{
	cout<<"input Graph type:";
	cin>>g.isDirect;
	cin>>g.isHaveWeight;
	cout<<"input vCount:";
	cin>>g.vCount;
	//create vers
	cout<<"input vers:";
	g.vers=new string[g.vCount];
	for(int i=0;i<g.vCount;i++)
		cin>>g.vers[i];
	//init matrix
	g.matrix=new int*[g.vCount];
	for(int j=0;j<g.vCount;j++)
		g.matrix[j]=new int[g.vCount];
	for(int a=0;a<g.vCount;a++)
		for(int b=0;b<g.vCount;b++)
		if(g.isHaveWeight==1)
			g.matrix[a][b]=INFINITY;
		else
			g.matrix[a][b]=0;
	//add edge
	cout<<"input eCount:";	cin>>g.eCount;
	string v1,v2;	int weight;
	for(int q=0;q<g.eCount;q++)	{
		cout<<"input the edges of "<<q+1<<":";
		cin>>v1>>v2;
		if(g.isHaveWeight==1)
			cin>>weight;
		else
			weight=1;
		g.matrix[GraphLocate(g,v1)][GraphLocate(g,v2)]=weight;
		if(g.isDirect==0)
			g.matrix[GraphLocate(g,v2)][GraphLocate(g,v1)]=weight;
	}
}

void GraphPrint(Graph &g)
{
	cout << endl; 
    for(int i = 0; i < g.vCount; i++) {
        for(int j = 0; j < g.vCount; j++) {
            cout << g.matrix[i][j] << " ";
        }
        cout << endl; 
    }
}

//DFS init
void GraphDFSbyRec(Graph &g,string v,bool *&isVisited)
{
    cout<< "" <<v;
    isVisited[GraphLocate(g,v)] = true;
    for (int i = 0; i <g.vCount; i++)
    {
        if (g.matrix[GraphLocate(g,v)][i]!=0 && isVisited[i]==false)
        {
			cout << " -> ";
            GraphDFSbyRec(g,g.vers[i],isVisited);
        }
        
    }
    
}


//DFS
void GraphDFS(Graph &g,string v)
{
    bool *isVisited = new bool [g.vCount];
    for (int i = 0; i < g.vCount; i++)
    {
        isVisited[i]=false;
    }
    cout<< "DFS: ";
    GraphDFSbyRec(g,v,isVisited);
    cout << endl;
}

//BFS init
void GraphBFS_init(Graph &g, string v, bool *&isVisited, SeqQueue &q) {
    isVisited = new bool[g.vCount];
	cout << "BFS: ";
    for (int i = 0; i < g.vCount; i++) {
        isVisited[i] = false;
    }
    cout << "" << v;
    isVisited[GraphLocate(g, v)] = true;
    SeqQueueIn(q, GraphLocate(g, v));
}

//BFS
void GraphBFS(Graph &g, string v, bool *&isVisited, SeqQueue &q) {
    while (!SeqQueueEmpty(q)) {
        int cur = SeqQueueFront(q);
        SeqQueueOut(q);
        for (int i = 0; i < g.vCount; i++) {
            if (g.matrix[cur][i] != 0 && !isVisited[i]) {
                cout << " -> " << g.vers[i];
                isVisited[i] = true;
                SeqQueueIn(q, i);
            }
        }
    }
	cout << endl;
}

void GraphCreateTest()
{
    Graph g;
    GraphCreate(g);
    GraphPrint(g);
    string starting_vertex = g.vers[0];
    bool *isVisited;
	GraphDFS(g, starting_vertex);
    SeqQueue q;
    SeqQueueInit(q, g.vCount);
    GraphBFS_init(g, starting_vertex, isVisited, q);
    GraphBFS(g, starting_vertex, isVisited, q);
    delete[] isVisited;
}

int main(){
	 GraphCreateTest();
	 system("pause");
}

完整代码 2

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <iostream>
#include <assert.h>
#include <string>
#include "SeqQueue.h"
//#include "LinkStack.h"
using namespace std;
#define INFINITY 1000000
struct Graph{
	int vCount,eCount;
	string *vers;
	int **matrix;
	bool isDirect,isHaveWeight;
};

void GraphBFS(Graph &g, bool *&isVisited, SeqQueue &q);

//search vertex
int GraphLocate(Graph g,string v)
{
	for(int i=0;i<g.vCount;i++)
		if(g.vers[i]==v)
			return i;
	return -1;
}
//create
void GraphCreate(Graph &g)
{
	cout<<"input Graph type:";
	cin>>g.isDirect;
	cin>>g.isHaveWeight;
	cout<<"input vCount:";
	cin>>g.vCount;
	//create vers
	cout<<"input vers:";
	g.vers=new string[g.vCount];
	for(int i=0;i<g.vCount;i++)
		cin>>g.vers[i];
	//init matrix
	g.matrix=new int*[g.vCount];
	for(int x=0;x<g.vCount;x++)
		g.matrix[x]=new int[g.vCount];
	for(int t=0;t<g.vCount;t++)
		for(int j=0;j<g.vCount;j++)
			if(g.isHaveWeight==1)
				g.matrix[t][j]=INFINITY;
			else
				g.matrix[t][j]=0;
	//add edge
	cout<<"input eCount:";	cin>>g.eCount;
	string v1,v2;	int weight;
	for(int o=0;o<g.eCount;o++)	{
		cout<<"input the edges of "<<o+1<<":";
		cin>>v1>>v2;
		if(g.isHaveWeight==1)cin>>weight;
		else weight=1;
		g.matrix[GraphLocate(g,v1)][GraphLocate(g,v2)]=weight;
		if(g.isDirect==0)
			g.matrix[GraphLocate(g,v2)][GraphLocate(g,v1)]=weight;
	}
}

void GraphPrint(Graph &g)
{
	cout << endl; 
    for(int i = 0; i < g.vCount; i++) {
        for(int j = 0; j < g.vCount; j++) {
            cout << g.matrix[i][j] << " ";
        }
        cout << endl; 
    }
}


void GraphDFSbyRec(Graph &g, string v,bool *&isVisited)
{
	cout<<" "<<v;
	isVisited[GraphLocate(g,v)]=true;
	for(int i=0;i<g.vCount;i++)
		if(g.matrix[GraphLocate(g,v)][i]!=0 && isVisited[i]==false)
			GraphDFSbyRec(g,g.vers[i],isVisited);
}

void GraphDFS(Graph &g,string v)
{
	bool *isVisited=new bool[g.vCount];
	for(int i=0;i<g.vCount;i++)
		isVisited[i]=false;
	cout<<"DFS:";
	GraphDFSbyRec(g,v,isVisited);
	cout<<endl;
}

void GraphBFSinit(Graph &g, string v) {
    bool *isVisited = new bool[g.vCount];
    for (int i = 0; i < g.vCount; i++) {
        isVisited[i] = false;
    }
    SeqQueue q;
    SeqQueueInit(q, 10);
    cout << " " << v;
    isVisited[GraphLocate(g, v)] = true;
    SeqQueueIn(q, GraphLocate(g, v));
    GraphBFS(g, isVisited, q);
    delete[] isVisited;
}

void GraphBFS(Graph &g, bool *&isVisited, SeqQueue &q) {
    while (!SeqQueueEmpty(q)) {
        int cur = SeqQueueFront(q);
        SeqQueueOut(q);
        for (int i = 0; i < g.vCount; i++) {
            if (g.matrix[cur][i] != 0 && !isVisited[i]) {
                cout << " " << g.vers[i];
                isVisited[i] = true;
                SeqQueueIn(q, i);
            }
        }
    }
    cout << endl;
}

void GraphCreateTest()
{
    Graph g;
    GraphCreate(g);
    GraphPrint(g);
    string starting_vertex = g.vers[0];
    GraphDFS(g, starting_vertex);
    cout << "BFS:";
    GraphBFSinit(g, starting_vertex);
}

int main(){
	system("chcp 65001");
	GraphCreateTest();
	system("pause");
}

中文版

代码

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <iostream>
#include <assert.h>
#include <string>
#include "SeqQueue.h"
using namespace std;
#define INFINITY 1000000
struct Graph{
	int vCount,eCount;
	string *vers;
	int **matrix;
	bool isDirect,isHaveWeight;
};

//search vertex
int GraphLocate(Graph g,string v)
{
	for(int i=0;i<g.vCount;i++)
		if(g.vers[i]==v)
			return i;
	return -1;
}
//create
void GraphCreate(Graph &g)
{
	cout<<"是否为有向图，0.无向图 1.有向图，" << endl;
	cin>>g.isDirect;
	cout<<"是否为带权图，0.不带权 1.带权，" << endl;
	cin>>g.isHaveWeight;
	cout<<"请输入图的顶点数:" << endl;
	cin>>g.vCount;
	//create vers
	cout<<"请输入图的顶点，例：v1，v2:" << endl;
	g.vers=new string[g.vCount];
	for(int i=0;i<g.vCount;i++)
		cin>>g.vers[i];
	//init matrix
	g.matrix=new int*[g.vCount];
	for(int j=0;j<g.vCount;j++)
		g.matrix[j]=new int[g.vCount];
	for(int a=0;a<g.vCount;a++)
		for(int b=0;b<g.vCount;b++)
		if(g.isHaveWeight==1)
			g.matrix[a][b]=INFINITY;
		else
			g.matrix[a][b]=0;
	//add edge
	cout<<"请输入图的边数:" << endl;	
	cin>>g.eCount;
	string v1,v2;	int weight;
	for(int q=0;q<g.eCount;q++)	{
		cout<<"请输入边的方向，例v1，换行v2 "<<q+1<<":" << endl;
		cin>>v1>>v2;
		if(g.isHaveWeight==1)
			cin>>weight;
		else
			weight=1;
		g.matrix[GraphLocate(g,v1)][GraphLocate(g,v2)]=weight;
		if(g.isDirect==0)
			g.matrix[GraphLocate(g,v2)][GraphLocate(g,v1)]=weight;
	}
}

void GraphPrint(Graph &g)
{
	cout << endl;
	if (g.isDirect==1)
	{
		cout <<"有向图" << endl ; 
	}else{
		cout <<"无向图" << endl;
	}
	if (g.isHaveWeight==1)
	{
		cout <<"带权图" << endl;
	}else{
		cout<< "不带权" << endl;
	}
	cout << "图的顶点数为：" << g.vCount << endl;
	cout << "图的边数为：" << g.eCount << endl;
    for(int i = 0; i < g.vCount; i++) {
        for(int j = 0; j < g.vCount; j++) {
            cout << g.matrix[i][j] << " ";
        }
        cout << endl;
    }
}

//DFS init
void GraphDFSbyRec(Graph &g,string v,bool *&is_visited)
{
    cout<< "" <<v;
    is_visited[GraphLocate(g,v)] = true;
    for (int i = 0; i <g.vCount; i++)
    {
        if (g.matrix[GraphLocate(g,v)][i]!=0 && is_visited[i]==false)
        {
			cout << " -> ";
            GraphDFSbyRec(g,g.vers[i],is_visited);
        }
        
    }
    
}


//DFS
void GraphDFS(Graph &g,string v)
{
    bool *is_visited = new bool [g.vCount];
    for (int i = 0; i < g.vCount; i++)
    {
        is_visited[i]=false;
    }
    cout<< "深度优先搜索: ";
    GraphDFSbyRec(g,v,is_visited);
    cout << endl;
}

//BFS init
void GraphBFS_init(Graph &g, string v, bool *&is_Visited, SeqQueue &q) {
    is_Visited = new bool[g.vCount];
	cout << "广度优先搜索: ";
    for (int i = 0; i < g.vCount; i++) {
        is_Visited[i] = false;
    }
    cout << "" << v;
    is_Visited[GraphLocate(g, v)] = true;
    SeqQueueIn(q, GraphLocate(g, v));
}

//BFS
void GraphBFS(Graph &g, string v, bool *&is_Visited, SeqQueue &q) {
    while (!SeqQueueEmpty(q)) {
        int cur = SeqQueueFront(q);
        SeqQueueOut(q);
        for (int i = 0; i < g.vCount; i++) {
            if (g.matrix[cur][i] != 0 && !is_Visited[i]) {
                cout << " -> " << g.vers[i];
                is_Visited[i] = true;
                SeqQueueIn(q, i);
            }
        }
    }
	cout << endl;
}

void GraphCreateTest()
{
    Graph g;
    GraphCreate(g);
    GraphPrint(g);
    string starting_vertex = g.vers[0];
    bool *is_visited;
	GraphDFS(g, starting_vertex);
    SeqQueue q;
    SeqQueueInit(q, g.vCount);
    GraphBFS_init(g, starting_vertex, is_visited, q);
    GraphBFS(g, starting_vertex, is_visited, q);
    delete[] is_visited;
}

int main(){
	 system("chcp 65001");
	 GraphCreateTest();
	 system("pause");
}