图论之欧拉路

欧拉路

给定无孤立节点图G，若存在一条路，经过图中的每一条边一次且仅一次，那么该条路称为欧拉路，如果这条路的起点和终点相同，则该路称为欧拉回路，否则称为欧拉通路。

无向图

无向图中具有一条欧拉图，当且仅当该图是连通图且有零个或者两个奇数度的节点，所有点的度都是偶数的时候，该图有欧拉回路，有两个奇数度的节点时，有欧拉通路。

有向图

有向图具有欧拉路当且仅当该图是连通的，若每个节点的入度等于出度，则存在欧拉回路，若图中除了两个节点之外，每个点的入度等于出度，而这两个点中一个点的入度比出度大1，另外一个点的出度比入读大1，则存在欧拉通路。

求解欧拉路

当判断图中具有欧拉路后，可以根据深度优先搜索，对每一条边设置访问标记，当找到一条欧拉路后直接结束搜索，否则根据回溯思想不断进行搜索。