有向图中的欧拉电路

  • Z时代
  • 2024-01-10
  • 分类：综合

欧拉路径是一条路径，通过它我们可以一次访问每个边缘。我们可以多次使用相同的顶点。欧拉电路是欧拉路径的一种特殊类型。当欧拉路径的起始顶点也与该路径的终止顶点相连时，则称为欧拉电路。

要检查图是否为欧拉图，我们必须检查两个条件-

  • 图形必须是连通的。

  • 每个顶点的入度和出度必须相同。

输入输出

Input:
图的邻接矩阵
0 1 0 0 0
0 0 1 0 0
0 0 0 1 1
1 0 0 0 0
0 0 1 0 0
Output:
发现欧拉电路。

算法

traverse(u, visited)

输入： 起始节点u和访问节点，以标记访问了哪个节点。

输出：遍历所有连接的顶点。

Begin
   mark u as visited
   for all vertex v, if it is adjacent with u, do
      if v is not visited, then
         traverse(v, visited)
   done
End

isConnected（图）

输入- 图形。

输出-如果已连接图形，则为True。

Begin
   define visited array
   for all vertices u in the graph, do
      make all nodes unvisited
      traverse(u, visited)
      if any unvisited node is still remaining, then
         return false
   done
   return true
End

isEulerCircuit（图）

输入：给定的图形。

输出： 找到一个欧拉电路时为真。

Begin
   if isConnected() is false, then
      return false
   define list for inward and outward edge count for each node
   for all vertex i in the graph, do
      sum := 0
      for all vertex j which are connected with i, do
         inward edges for vertex i increased
         increase sum
      done
      number of outward of vertex i is sum
   done
   if inward list and outward list are same, then
      return true
   otherwise return false
End

示例

#include<iostream>
#include<vector>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
   {0, 1, 0, 0, 0},
   {0, 0, 1, 0, 0},
   {0, 0, 0, 1, 1},
   {1, 0, 0, 0, 0},
   {0, 0, 1, 0, 0}
};
               
void traverse(int u, bool visited[]) {
   visited[u] = true;    //将v标记为已访问
   for(int v = 0; v<NODE; v++) {
      if(graph[u][v]) {
         if(!visited[v])
            traverse(v, visited);
      }
   }
}
bool isConnected() {
   bool *vis = new bool[NODE];
   //以所有顶点u为起点，检查所有节点是否可见
   for(int u; u < NODE; u++) {
      for(int i = 0; i<NODE; i++)
         vis[i] = false;    //initialize as no node is visited
               
      traverse(u, vis);
         
      for(int i = 0; i<NODE; i++) {
         if(!vis[i])    //如果有一个节点，不被遍历访问，则图是不连通的
            return false;
      }
   }
   return true;
}
bool isEulerCircuit() {
   if(isConnected() == false) {    //当图不连通时
      return false;
   }
   vector<int> inward(NODE, 0), outward(NODE, 0);
         
   for(int i = 0; i<NODE; i++) {
      int sum = 0;
      for(int j = 0; j<NODE; j++) {
         if(graph[i][j]) {
            inward[j]++;    //增加目标顶点的内边
            sum++;    //多少条外边
         }
      }
      outward[i] = sum;
   }
   if(inward == outward)    //当每个节点的向内边和向外边的数目相同时
      return true;
   return false;
}
int main() {
   if(isEulerCircuit())
      cout << "Euler Circuit Found.";
   else
      cout << "There is no Euler Circuit.";
}

输出结果

Euler Circuit Found.

以上是 有向图中的欧拉电路 的全部内容， 来源链接： utcz.com/z/354229.html

回到顶部