【432】COMP9024,Exercise9
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
最新文章
- webapi版本升级管理
- [lintcode 14] First Position of Target
- Java 利用初学知识 写出自己的名字
- 编写高质量代码改善C#程序的157个建议读书笔记【11-20】
- centos6.5 64位系统安装 tengine
- linux apache 自动监护脚本
- hdu3294(manacher)
- 大数据系列之Hadoop分布式集群部署
- Python 自动化 第一周
- IDEA常用操作
- IntelliJ IDEA 注册码——亲测有效
- 【Java每日一题】20170309
- composer 自动加载 通过classmap自动架子啊
- 服务器&;linux
- 20155237 2016-2017-2 《Java程序设计》第8周学习总结
- bzoj 3450 期望分数
- /*使用PHP创建一个数组,保存5個员工的信息(ename/sex/salary/birthday/pic)*/
- 测试开发之Django——No3.Django中的试图(views)
- 013 - 关于GC root: Native Stack | MAT分析
- 润乾报表在proxool应用下的数据源配置
热门文章
- C++创建对象的3种方式(转载)
- 修改Windows10 命令终端cmd的编码为UTF-8
- car二手车购买原理
- 【爬虫】大杀器——phantomJS+selenium
- 为什么 MySQL 索引要使用 B+树而不是其它树形结构?比如 B 树?
- regedit系统注册表,msconfig系统配置
- printf的使用和test的使用
- noi.ac #44 链表+树状数组+思维
- webstorm 和 vscode 的纠结
- FLUENT求解传热系数surfaceheattransfercoef.的参考值的设置【转载】