Position: Document Download > All Categories > Foreign Language Learning > Korean Learning > 2014 Heilongjiang Province Important Data Introduction
Infringement complaint

Introduction to important data of Heilongjiang Province in 2014

Introduction to important data of Heilongjiang Province in 2014

1. Assuming that the adjacency matrix is used as the storage structure of the graph, write an algorithm to determine whether there is a simple directed loop in a given directed graph. If it exists, output the loop as a sequence of vertices (you can find one). (Note: there is no arc from vertex to own in the figure)

Directed graph judgment loops are more complicated than undirected graphs. Using depth-first traversal, the vertices are divided into three categories: unvisited; visited but their neighboring points have not been visited; visited and their neighboring points have been visited. The following three states are represented by 0, 1, and 2. As mentioned earlier, if the back edges of vertices u to v appear before the end of dfs (v), there must be a circuit containing vertices v and u in the graph. In the corresponding program, the state of v is 1, and u is the vertex being accessed. If we find that the state of the next adjacent point of u is 1, we can output the circuit.

void Print (int v, int start) // Output the circuit starting from vertex start.

(for (i = 1; i <= n; i ++)

if (g [v] [i]! = 0 && visited [i] == 1) // If there is an edge (v, i) and the state of vertex i is 1. {printf ("% d", v);

if (i == start) printf (“\ n”); else Print (i, start); break;} // if

} // Print

void dfs (int v)

{visited [v] = 1;

for (j = 1; j <= n; j ++)

if (g [v] (j]! = 0) // existing edge (v, j)

if (visited [j]! = 1) {if (! visited [j]) dfs (j);} // if

else {cycle = 1; Print (j, j);}

visited [v] = 2;

} // dfs

void find_cycle () // Determine if there is a loop, and if so, output the adjacency matrix. The visited array is a global variable. {for (i = 1; i <= n; i ++) visited [i] = 0;

for (i = 1; i <= n; i ++) if (! visited [i]) dfs (i);

} // find_cycle

2. In the title, the average value of the elements in the two rows of the matrix should be sorted in ascending order. Since the number of elements in each row is equal, the average value and the sum of the elements in each line are the same. So you should first find the sum of the elements in each row, put them into a one-dimensional array, and then choose a sorting method to sort the array. Note that if there is an element movement during sorting, each element in the corresponding row must also be Make changes accordingly.

void Translation (float * matrix, int n)

// This algorithm transforms the n × n matrix matrix by the average value of the elements of each row in ascending order. {int i, j, k, l;

float sum, min; // sum temporarily stores the sum of the elements in each row

float * p, * pi, * pk;

for (i = 0; i <n; i ++)

(sum = 0.0; pk = matrix + i * n; // pk points to the first element of each row of the matrix.

for (j = 0; j <n; j ++) (sum + = * (pk); pk ++;) // Find the sum of a row of elements.

* (p + i) = sum; // Save the sum of a row of elements into a one-dimensional array.

} // for i

for (i = 0; i <n-1; i ++) // sort the array p by selection

(min = * (p + i); k = i; // Initially set the sum of the elements in the i-th row to be the smallest.

for (j = i + 1; j <n; j ++) if (p [j] <min) {k = j; min = p [j];} // Remember the new minimum value and line number.

Page 1Next

free download Word Documents Free Download: An Introduction to Important Data in Heilongjiang Province in 2014

(Download 1-3 pages, total 3 pages)

you may also like

Back to top