eulerianCycle.c
- What determines whether a graph is Eulerian or not?
- Write a C program that reads a graph, prints the graph, and determines whether an input graph is Eulerian or not.
- if the graph is Eulerian, the program prints an Eulerian path
- you should start with vertex 0
note that you may use the function findEulerianCycle() from the lecture on Graph Search Applications
if it is not Eulerian, the program prints the message Not Eulerian
- if the graph is Eulerian, the program prints an Eulerian path
For example,
- The graph:
#4
0 1 0 2 0 3 1 2 2 3is not Eulerian (can you see why?). Using this as input, your program should output:
V=4, E=5
<0 1> <0 2> <0 3>
<1 0> <1 2>
<2 0> <2 1> <2 3>
<3 0> <3 2>
Not Eulerian -
In the above-named lecture I showed a 'concentric squares' graph (called concsquares):
#8
0 7 7 5 5 1 1 0
6 0 6 7
2 5 2 7
4 1 4 5
3 0 3 1which is Eulerian, although I've labelled the vertices differently here. For this input your program should produce the output:
V=8, E=12
<0 1> <0 3> <0 6> <0 7>
<1 0> <1 3> <1 4> <1 5>
<2 5> <2 7>
<3 0> <3 1>
<4 1> <4 5>
<5 1> <5 2> <5 4> <5 7>
<6 0> <6 7>
<7 0> <7 2> <7 5> <7 6>
Eulerian cycle: 0 1 4 5 2 7 5 1 3 0 6 7 0Draw concsquares, label it as given in the input file above, and check the cycle is indeed Eulerian.
-
The function findEulerCycle() in the lecture notes does not handle disconnected graphs. In a disconnected Eulerian graph, each subgraph has an Eulerian cycle.
- Modify this function to handle disconnected graphs.
- With this change, your program should now work for the graph consisting of 2 disconnected triangles:
#6
0 1 0 2 1 2 3 4 3 5 4 5It should now find 2 Eulerian paths:
V=6, E=6
<0 1> <0 2>
<1 0> <1 2>
<2 0> <2 1>
<3 4> <3 5>
<4 3> <4 5>
<5 3> <5 4>
Eulerian cycle: 0 1 2 0
Eulerian cycle: 3 4 5 3
思路：经过一条边就删掉一个，通过遍历查找是否遍历完（针对不连通的graph）
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "Graph.h"
#include "Quack.h" #define UNVISITED -1
#define WHITESPACE 100 void dfsR(Graph g, Vertex v, int numV, int *order, int *visited);
Vertex getAdjacent(Graph g, int numV, Vertex v); int readNumV(void) { // returns the number of vertices numV or -1
int numV;
char w[WHITESPACE];
scanf("%[ \t\n]s", w); // skip leading whitespace
if ((getchar() != '#') ||
(scanf("%d", &numV) != 1)) {
fprintf(stderr, "missing number (of vertices)\n");
return -1;
}
return numV;
} int readGraph(int numV, Graph g) { // reads number-number pairs until EOF
int success = true; // returns true if no error
int v1, v2;
while (scanf("%d %d", &v1, &v2) != EOF && success) {
if (v1 < 0 || v1 >= numV || v2 < 0 || v2 >= numV) {
fprintf(stderr, "unable to read edge\n");
success = false;
}
else {
insertE(g, newE(v1, v2));
}
}
return success;
} void findEulerCycle(Graph g, int numV, Vertex startv) {
Quack s = createQuack();
push(startv, s); int allVis = 0;
while (!allVis) {
printf("Eulerian cycle: ");
while (!isEmptyQuack(s)) {
Vertex v = pop(s); // v is the top of stack vertex and ...
push(v, s); // ... the stack has not changed
Vertex w;
if ((w = getAdjacent(g, numV, v)) >= 0) {
push(w, s); // push a neighbour of v onto stack
removeE(g, newE(v, w)); // remove edge to neighbour
}
else {
w = pop(s);
printf("%d ", w);
}
}
printf("\n");
allVis = 1; for (Vertex v = 0; v < numV && allVis; v++) {
for (Vertex w = 0; w < numV && allVis; w++) {
if (isEdge(g, newE(v, w))) {
allVis = 0;
push(v, s);
}
}
}
}
} Vertex getAdjacent(Graph g, int numV, Vertex v) {
// returns the Largest Adjacent Vertex if it exists, else -1
Vertex w;
Vertex lav = -1; // the adjacent vertex
for (w=numV-1; w>=0 && lav==-1; w--) {
Edge e = newE(v, w);
if (isEdge(g, e)) {
lav = w;
}
}
return lav;
} int isEulerian(Graph g, int numV) {
int count = 0;
for (Vertex w = 0; w < numV; w++) {
count = 0;
for (Vertex v = 0; v < numV; v++) {
if (isEdge(g, newE(w, v))) {
count++;
}
}
if (count % 2 != 0) {
return 0;
}
}
return 1;
} int main (void) {
int numV;
if ((numV = readNumV()) >= 0) {
Graph g = newGraph(numV);
if (readGraph(numV, g)) {
showGraph(g); if(isEulerian(g, numV)) {
findEulerCycle(g, numV, 0);
}
else {
printf("Not Eulerian\n");
}
}
}
else {
return EXIT_FAILURE;
}
return EXIT_SUCCESS;
} // clear && gcc dfs_EulerCycle.c GraphAM.c Quack.c && ./a.out < input_1.txt // clear && gcc dfs_EulerCycle.c GraphAM.c Quack.c && ./a.out < input_2.txt // clear && gcc dfs_EulerCycle.c GraphAM.c Quack.c && ./a.out < input_3.txt
unreachable.c
Write a program that uses a fixed-point computation to find all the vertices in a graph that are unreachable from the start vertex (assume it to be 0). Note the following:
- the fixed-point computation should be iterative
you should not use recursion, or stacks or queues
If a graph is disconnected:
- then those vertices not reachable (say vertices 8 and 9) should be output as follows:
Unreachable vertices = 8 9
If a graph is connected then all vertices are reachable and the output is :
Unreachable vertices = none
For example:
- Here is a graph that consists of 2 disconnected triangles:
#6
0 1 0 2 1 2 3 4 3 5 4 5If the start vertex is 0, then the output should be:
V=6, E=6
<0 1> <0 2>
<1 0> <1 2>
<2 0> <2 1>
<3 4> <3 5>
<4 3> <4 5>
<5 3> <5 4>
Unreachable vertices = 3 4 5because obviously the vertices in the second triangle are not reachable from the first.
- here is a connected graph:
#5
0 1 1 2 2 3 3 4 4 0
1 3 1 4
2 4Starting at any vertex, the result should be:
V=5, E=8
<0 1> <0 4>
<1 0> <1 2> <1 3> <1 4>
<2 1> <2 3> <2 4>
<3 1> <3 2> <3 4>
<4 0> <4 1> <4 2> <4 3>
Unreachable vertices = none
思路：
- 首先就是设置 outside数组，默认是都为 -1，一旦被访问了就赋值为 0，变为 inside
- 设置一个 changing 字符串，用来监测 outside 数组是否有变化
- 如果变化的话，就遍历所有inside的点的相连接的点，如果发现 outside，则将此点赋值为 inside，changing 赋值为1
- while 循环，继续遍历，知道所有 inside 点的邻接点都是 inside，遍历结束
- 因此会将所有一个连通图中的点放入在 inside 内部
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "Graph.h" #define UNVISITED -1
#define WHITESPACE 100 int readNumV(void) { // returns the number of vertices numV or -1
int numV;
char w[WHITESPACE];
scanf("%[ \t\n]s", w); // skip leading whitespace
if ((getchar() != '#') ||
(scanf("%d", &numV) != 1)) {
fprintf(stderr, "missing number (of vertices)\n");
return -1;
}
return numV;
} int readGraph(int numV, Graph g) { // reads number-number pairs until EOF
int success = true; // returns true if no error
int v1, v2;
while (scanf("%d %d", &v1, &v2) != EOF && success) {
if (v1 < 0 || v1 >= numV || v2 < 0 || v2 >= numV) {
fprintf(stderr, "unable to read edge\n");
success = false;
}
else {
insertE(g, newE(v1, v2));
}
}
return success;
} int *mallocArray(int numV) {
int *array = malloc(numV * sizeof(int));// l
if (array == NULL) { // o
fprintf(stderr, "Out of memory\n"); // c
exit(1); // a
} // l
int i; // f
for (i=0; i<numV; i++) { // u
array[i] = UNVISITED; // n
} // c
return array; // t
} void showUnreach(Graph g, int numV, Vertex startv) {
int *outside = mallocArray(numV);
outside[startv] = 0;
int changing = 1;
while (changing) {
changing = 0;
for (Vertex v = 0; v < numV; v++) {
if (!outside[v]) {
for (Vertex w = 0; w < numV; w++) {
if (isEdge(g, newE(v, w)) && outside[w] == UNVISITED) {
outside[w] = 0;
changing = 1;
}
}
}
}
}
printf("Unreachable vertices = ");
int any = 0;
for (Vertex v = 0; v < numV; v++) {
if (outside[v] == UNVISITED) {
printf("%d ", v);
any = 1;
}
}
if (!any) {
printf("none");
}
putchar('\n');
return;
} int main (void) {
int numV;
if ((numV = readNumV()) >= 0) {
Graph g = newGraph(numV);
if (readGraph(numV, g)) {
showGraph(g);
showUnreach(g, numV, 0);
}
}
else {
return EXIT_FAILURE;
}
return EXIT_SUCCESS;
} // clear && gcc unreachable.c GraphAM.c && ./a.out < input_1.txt // clear && gcc unreachable.c GraphAM.c && ./a.out < input_2.txt // clear && gcc unreachable.c GraphAM.c && ./a.out < input_3.txt