图算法入门1：基础表示方法和深度优先搜索实现

图结构深度优先搜索示例如下图所示：

从一个结点开始优先按照深度访问相邻节点，下面详细介绍代码实现。

如上图的图结构，通常以文件形式进行保存，每一行第一个字符是当前节点名字，后续字符是相连接节点名字，故其存储内容如下：

s a
a s b g
g a h i
i g
h g
b a c d e
e b f
f e
d b
c b

图的表示，每一个图的节点用一个结构体表示：

typedef struct Vertex{
	string name;
	int index;
	Vertex(string inputName, int inputIndex):name(inputName),index(inputIndex){}
	Vertex():name(""),index(0){}
} VertexNode;

index对应图节点的编号索引，name对应图节点的名字，整个图结构用邻接表表示法： 

vector > adjGraph;

第一个vector的索引对应某个图节点的索引，对应内容为该图节点所有连接的图节点信息。

深度优先搜索算法实现：

void graphDfs(vector >& graph,  const int& here, vector& visited, const vector& indexName){
	cout << "DFS visit " << indexName[here] << endl;
	visited[here] = true;
	// 遍历所有相邻的顶点
	for(int i = 0; i < graph[here].size(); ++i) {
		int there = graph[here][i].index;
		if(!visited[there]) {
			graphDfs(graph, there, visited, indexName);
		}
	}
}

可以看到基本原理就是从一个图节点开始深度优先访问所有节点，并且一直迭代下去，直到访问完所有节点，vector visit标记是否访问过某个图节点，indexName用于保存节点编号index和名字name的转换。完整实现代码如下：

#include
#include
#include
#include
#include
#include
using namespace std;
typedef struct Vertex{
	string name;
	int index;
	Vertex(string inputName, int inputIndex):name(inputName),index(inputIndex){}
	Vertex():name(""),index(0){}
} VertexNode;
void graphDfs(vector >& graph,  const int& here, vector& visited, const vector& indexName){
	cout << "DFS visit " << indexName[here] << endl;
	visited[here] = true;
	// 遍历所有相邻的顶点
	for(int i = 0; i < graph[here].size(); ++i) {
		int there = graph[here][i].index;
		if(!visited[there]) {
			graphDfs(graph, there, visited, indexName);
		}
	}
}
int main() {
	unordered_map graphMap; // 图节点名和编号的Map
	vector > adjGraph; // 图的连接表表示法
	ifstream graphRdFile("graph_struct.txt");
	if(!graphRdFile.good()) {
		cout << "open graph file failed!" << endl;
		return -1;
	}
	string line;
	int index = 0;
	string vertexName;
	// 首先对Vertex Name进行编码
	while(graphRdFile >> vertexName) {
		if (graphMap.find(vertexName) == graphMap.end()) {
			graphMap.insert(make_pair(vertexName, index++));
		}
	}
	// 编码与Vertex的反映射
	vector indexName = vector(graphMap.size(),"");
	for(auto itr=graphMap.begin();itr!=graphMap.end();itr++) {
		indexName[itr->second] = itr->first;
	}
	// 重新读
	graphRdFile.clear();
	graphRdFile.seekg(0,std::ios::beg);
	adjGraph.resize(graphMap.size());
	int currentIndex = 0; // 当前图节点的编号
	while (getline(graphRdFile, line)) { //按行读，每一行是一个图节点的连接情况
		istringstream ss(line);
		string tmp;
		bool firstFlag = true;
		while(ss >> tmp) {
			if (firstFlag) {
				if (graphMap.find(tmp) != graphMap.end()) {
					currentIndex = graphMap[tmp];
				} else {
					break;
				}
				firstFlag = false;
				continue;
			}
			if (graphMap.find(tmp) != graphMap.end()) {
				adjGraph[currentIndex].emplace_back(VertexNode(tmp,graphMap[tmp]));
			}
		}
	}
	// 深度优先搜索测试
	vector visited = vector(graphMap.size(), false);
	graphDfs(adjGraph, 0, visited, indexName);
	return 0;
}

执行结果如下：

DFS visit s
DFS visit a
DFS visit b
DFS visit c
DFS visit d
DFS visit e
DFS visit f
DFS visit g
DFS visit h
DFS visit i

注意，这里针对的是连通图的情况，若不连通，则无法保证遍历所有图节点，例如如下图的图结构

则需要从每个节点都遍历一次，才能保证遍历所有节点：

for (int i = 0; i < adjGraph.size(); ++i) {
    if(!visited[i])
	graphDfs(adjGraph, 0, visited, indexName);
}

graphDfs对于每个顶点调用1次，所以总共被调用次，而执行相邻边线检测的for循环，会对所有边线确认1次（有向图）或2次（无向图），故最终时间复杂度为。