图的存储
在leetcode中图的存储形式如下，这种形式的图只能适合用来存储是连通图的情况，且根据leetcode提供的_{0,1,2#1,2#2,2}_格式的字符串通过程序来自动构造图比较麻烦，预知字符串的含义请移步到leetcode的解释。
1
2
3
4
5
6
7
| /**
* Definition for undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector<UndirectedGraphNode *> neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
|
本文为了能够用字符串表示所有图，并且便于程序的构造，使用了邻接表的形式来对图进行存储，即可以用来存储有向图，有可以存储无向图。图一个节点的结构如下：
1
2
3
4
5
6
7
8
9
| /**
* 图节点的邻接表表示形式
*/
struct GraphNode {
std::string label;
std::vector<GraphNode *> neighbors;
bool visited; // 深度优先搜索和广度优先搜索的遍历都需要visited数组，为了简化程序，直接在节点的存储结构中设置visited变量
GraphNode(std::string x) : label(x), visited(false) {};
};
|
图的创建方面为了简化算法实现，对程序的效率没做太多关注，算法复杂度稍高。本算法的难点在于对字符串的拆解，并根据字符串找到对应的节点指针。
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
| /**
* 图节点的邻接表表示形式
*/
struct GraphNode {
std::string label;
std::vector<GraphNode *> neighbors;
bool visited;
GraphNode(std::string x) : label(x), visited(false) {};
};
/**
* 通过字符串的值，找到该字符串对应的图节点
*/
GraphNode *get_one_node(const std::vector<GraphNode *> &node_vector, std::string str)
{
for (std::vector<GraphNode *>::const_iterator iter = node_vector.begin(); iter != node_vector.end(); iter++)
{
if ((*iter)->label == str)
{
return *iter;
}
}
return NULL;
}
/**
* 时间复杂度高,对图的构建一般效率要求较低
* 对于查找某个节点的邻接点的指针操作可以使用map来提高查询效率
* 或者可以通过不需要初始化所有节点的方式来构造图，而是采用需要哪个节点构造哪个节点的方式
*/
std::vector<GraphNode *> create_graph(std::string str)
{
std::vector<GraphNode *> node_vector;
// init all nodes
for (size_t pos = 0; pos < str.length() - 1;)
{
size_t end = str.find(',', pos);
if (end != std::string::npos)
{
GraphNode *node = new GraphNode(str.substr(pos, end - pos));
node_vector.push_back(node);
}
else
{
break;
}
pos = str.find('#', pos);
if (pos == std::string::npos)
{
break;
}
else
{
pos++;
}
}
// add neighbors in every node
for (size_t pos = 0; pos < str.length() - 1; )
{
GraphNode *current_node = NULL;
size_t current_end = str.find(',', pos);
if (current_end != std::string::npos)
{
current_node = get_one_node(node_vector, str.substr(pos, current_end - pos));
pos = current_end + 1;
}
else
{
break;
}
size_t node_end = str.find('#', pos); // 当前节点的字符串的结束位置
if (node_end == std::string::npos)
{
node_end = str.length();
}
else
{
node_end--;
}
for ( ; ; )
{
current_end = str.find(',', pos);
if (current_end > node_end || current_end == std::string::npos)
{
// 一个节点的最后一个邻接点
current_end = node_end;
}
else
{
current_end--;
}
GraphNode *node = get_one_node(node_vector, str.substr(pos, current_end - pos + 1));
if (node != NULL)
{
current_node->neighbors.push_back(node);
std::cout << current_node->label << " add " << node->label << std::endl;
}
if (current_end == node_end)
{
// 一个节点的最后一个邻接点
break;
}
else
{
pos = current_end + 2; // 该节点之后还有其他邻接点
}
}
pos = node_end + 2;
}
return node_vector;
}
|
深度优先搜索
深度优先搜索遵循贪心算法的原理，如果孩子节点不为空，则一直遍历下去。
递归算法
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
| void DFS_traverse_recursion(GraphNode *node)
{
if (!node->visited)
{
std::cout << node->label << '\t';
node->visited = true;
}
for (std::vector<GraphNode *>::iterator iter = node->neighbors.begin(); iter != node->neighbors.end(); iter++)
{
if (!(*iter)->visited)
{
DFS_traverse_recursion(*iter);
}
}
}
/**
* 图的深度优先搜索的递归形式
*/
void DFS_traverse_recursion(std::vector<GraphNode *> &graph)
{
for (std::vector<GraphNode *>::iterator iter = graph.begin(); iter != graph.end(); iter++)
{
(*iter)->visited = false;
}
for (std::vector<GraphNode *>::iterator iter = graph.begin(); iter != graph.end(); iter++)
{
if (!(*iter)->visited)
DFS_traverse_recursion(*iter);
}
}
|
非递归算法
使用栈来实现非递归。
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
| /**
* 图的深度优先搜索的非递归形式
*/
void DFS_traverse_not_recursion(std::vector<GraphNode *> &graph)
{
for (std::vector<GraphNode *>::iterator iter = graph.begin(); iter != graph.end(); iter++)
{
(*iter)->visited = false;
}
for (std::vector<GraphNode *>::iterator iter = graph.begin(); iter != graph.end(); iter++)
{
std::stack<GraphNode *> node_stack;
if ((*iter)->visited)
{
continue;
}
node_stack.push(*iter);
while (!node_stack.empty())
{
GraphNode *node = node_stack.top();
node_stack.pop();
if (node->visited)
continue;
std::cout << node->label << '\t';
node->visited = true;
/* 使用反向迭代器遍历后将节点加入到栈中 */
for (std::vector<GraphNode *>::reverse_iterator iter2 = node->neighbors.rbegin(); iter2 != node->neighbors.rend(); iter2++)
{
if (!(*iter2)->visited)
{
node_stack.push(*iter2);
}
}
}
}
}
|
广度优先搜索
该算法不存在递归算法，仅有非递归版本。需要利用队列来保存需要遍历的节点，占用的存储空间稍多。
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
| /**
* 图的广度优先搜索的非递归形式
*/
void BFS_traverse_not_recursion(std::vector<GraphNode *> &graph)
{
for (std::vector<GraphNode *>::iterator iter = graph.begin(); iter != graph.end(); iter++)
{
(*iter)->visited = false;
}
for (std::vector<GraphNode *>::iterator iter = graph.begin(); iter != graph.end(); iter++)
{
std::queue<GraphNode *> node_queue;
if ((*iter)->visited)
{
continue;
}
node_queue.push(*iter);
while (!node_queue.empty())
{
GraphNode *node = node_queue.front();
node_queue.pop();
if (node->visited)
continue;
std::cout << node->label << '\t';
node->visited = true;
for (std::vector<GraphNode *>::iterator iter2 = node->neighbors.begin(); iter2 != node->neighbors.end(); iter2++)
{
if (!(*iter2)->visited)
{
node_queue.push(*iter2);
}
}
}
}
}
|
相关下载
本文相关源码