Занятие 5. Справочник

Занятие 5. Справочник

Поиск цикла в графе c выводом, заданном матрицей смежности G ????????????????????? 
…
static int[] path = new int[1000]; // 1000 – количество вершин в графе
static int n = 0; // количество уже открытых вершин
static boolean foundCycle = false;

static void DFS(int v, int p)
{
     color[v] = GREY; 
     path[n] = v;
n++;
	for (int i = 0; i < N; i++)
	{
           if (p != i && G[v][i] == 1 && 
               color[i] == GREY && !foundCycle)//обнаружен первый цикл
           {
			foundCycle = true;
			printCycle();
	}  
		if (G[v][i] == 1 && color[i] == WHITE) DFS(i, v);
	}
	color[v] = BLACK;
}

static void printCycle()
{
     int start = path[n-1];
     int i = n – 2;
	while(path[i] != start)
	{
           if (color[i] == GREY)
           {
			out.println (path[i]);
	}
	}
}
Вывод эйлерова цикла в графе. Перед использованием необходимо убедиться, что степени всех вершин четны. 
static euler (int v)
{
       for (int i = 0; j < n; j++)
       {  
           if (G[v][i] == 1)
           {
             G[v][i]=0;
             G[i][v]=0;
             euler(i);
	    }
        }
        out.print(i + " ");
}