Table of Contents
Question A: The graph stored in the adjacency list is converted into the graph stored in the adjacency matrix – additional code pattern
Problem B: DFS-non-recursive algorithm for adjacency matrix storage graph (additional code pattern)
Problem C: Case 6-1.2: Breadth-first traversal of adjacency list storage graph
Problem D: DFS completion order solution of adjacency matrix storage graph (additional code pattern)
Issue E: Basic Experiment 6-2.3: Rescue 007
Problem A: The graph stored in the adjacency list is converted into a graph stored in the adjacency matrix – additional code mode
Title description
Adjacency lists and adjacency matrices are the two most important and basic graph storage methods. Students need to be proficient in programming in these two ways.
Taking the above figure as an example, the corresponding adjacency list and adjacency matrix storage methods can be expressed as:
(1) Adjacency list method
Number of nodes: 7
Node information: a b c d e f g
a-g-f
b-c
c-e
d
e-d
f-g-e
g-d
(2) Adjacency matrix method
Number of nodes: 7
Node information: a b c d e f g
0 0 0 0 0 1 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 1
0 1 0 1 0 0 0
Please write a program to convert the graph stored by the adjacency list method into the graph stored by the adjacency matrix method, and output
This question is in the additional code mode. The above code is automatically appended to the code submitted by the students. There is a code framework in the prompt for this question. Please copy it, modify it, comment out part of the code, and finally submit it.
Input format
The first line of input is a positive integer n (n<100), which represents the number of nodes in the graph.
The next n lines represent the information of each node, as well as the edge information of other points that can be reached from this node as the starting point.
Convention: Each node information is n consecutive letters starting from the lowercase letter a
Output format
First output the adjacency list
Then output an adjacency matrix composed of 0,1
Input sample
7 a-g-f b-c c-e d e-d f-g-e g-d
Example output
a --> g --> f b --> c c --> e d e --> d f --> g --> e g --> d 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0
AC code:
#include <bits/stdc + + .h>
using namespace std;
#defineMAX_SIZE 100
//Graph stored in adjacency matrix
struct graph
{
int vexNumber;
string vexInfo[MAX_SIZE];
int adjMatrix[MAX_SIZE][MAX_SIZE];
};
//Arc node definition
struct ArcNode
{
char weight; //The information part on the arc
int adj; // Serial number of adjacent point
ArcNode *nextarc; // next edge
};
//Vertex node definition
struct VexNode
{
string Info; // Information part on the vertex
ArcNode *firstarc; // Arc chain head pointer
};
// Definition of graph with adjacency list structure
struct linkGraph
{
VexNode *vexes; //adjacency list of each node
int vexnumber; // number of nodes
};
// Initialization of the graph stored in the adjacency list
int InitGraph(linkGraph & amp;G, int vexnumber)
{
G.vexes = new VexNode[vexnumber];
G.vexnumber = vexnumber;
for (int i = 0; i < vexnumber; i + + )
G.vexes[i].firstarc = NULL;
return 0;
}
//Construct edge node pointer
ArcNode* getArcNode(int adj){
ArcNode* node = new ArcNode();
node->adj = adj;
node->nextarc = nullptr;
return node;
}
//Construct the graph stored in the adjacency list based on the input
void InputlinkGraph(linkGraph & LG){
int n;
cin>>n;
InitGraph(LG,n);
for(int i=0;i<n;i + + ){
string s;
cin>>s;
LG.vexes[i].Info=s[0];
for(int j=1;j<s.size();j + + ){
if(s[j]=='-')continue;
ArcNode* p= new ArcNode();
ArcNode* a= LG.vexes[i].firstarc;
p->nextarc=NULL;
p->weight=s[j];
p->adj=s[j]-'a';
if(a==NULL)LG.vexes[i].firstarc=p;
else{
while(a->nextarc!=NULL)
a=a->nextarc;
a->nextarc=p;
}
}
}
}
//Convert the graph stored in the adjacency list into the graph stored in the adjacency matrix
void linkGraph2Graph(const linkGraph & LG, Graph & G){
G.vexNumber=LG.vexnumber;
memset(G.adjMatrix,0,sizeof(G.adjMatrix));
for(int i=0;i<LG.vexnumber;i + + ){
ArcNode* p=LG.vexes[i].firstarc;
while(p!=NULL){
G.adjMatrix[i][p->adj]=1;
p=p->nextarc;
}
}
}
// Output adjacency matrix
void printGraph(const Graph & amp; G){
for(int i=0;i<G.vexNumber;i + + ){
for(int j=0;j<G.vexNumber;j + + ){
cout<<G.adjMatrix[i][j]<<" ";
}
cout<<endl;
}
}
// Output adjacency list
void PrintlinkGraph(const linkGraph & amp; G){
for(int i=0;i<G.vexnumber;i + + ){
cout<<G.vexes[i].Info;
ArcNode* p=G.vexes[i].firstarc;
while(p!=NULL){
cout<<" --> "<<p->weight;
p=p->nextarc;
}
cout<<endl;
}
}
// Destruction of the graph stored in the adjacency list
int DestroylinkGraph(linkGraph & amp;G)
{
for (int i = 0; i < G.vexnumber; i + + )
{
while (G.vexes[i].firstarc != NULL)
{
ArcNode *p = G.vexes[i].firstarc;
G.vexes[i].firstarc = p->nextarc;
delete p;
}
}
delete[] G.vexes;
G.vexes = NULL;
G.vexnumber = 0;
return 0;
}
// please comment the following code when you submit to OJ
int main(){
// freopen("/config/workspace/answer/test.in","r",stdin);
linkGraph LG;
Graph G;
InputlinkGraph(LG);
PrintlinkGraph(LG);
linkGraph2Graph(LG,G);
printGraph(G);
DestroylinkGraph(LG);
return 0;
}
Problem B: DFS-non-recursive algorithm for adjacency matrix storage graph (additional code mode)
Title description
Depth-first search traversal is similar to pre-order traversal of trees and is a generalization of the pre-order traversal algorithm of trees.
The process is: assuming that the initial state is that all vertices in the graph have not been visited, the depth-first search can start from a certain vertex v in the graph, visit this vertex, and then start the depth-first traversal from the unvisited adjacent points of v. graph until all vertices in the graph that have paths connected to v are visited;
If there are still unvisited vertices in the graph at this time, select another unvisited vertex in the graph as the starting point, and repeat the above process until all vertices in the graph have been visited.
In this question, read in the adjacency matrix (i.e. array representation) of a graph, build the graph and traverse all vertices according to the algorithm described above, and output the order of traversing the vertices.
The non-recursive algorithm implementation of DFS is also similar to the non-recursive implementation of the tree’s pre-order traversal algorithm. A stack is used to store nodes. If the node is “completed”, that is, all adjacent points have been visited, then the node will be removed from the stack. quit.
This question is in additional code mode. The following code will be automatically appended to the code submitted by students. There is a code framework in the prompt for this question. Please copy it, modify it, comment out part of the code, and finally submit it.
Input format
The first line of input contains a positive integer n, indicating that there are n vertices in the graph. where n does not exceed 50. Each of the following n lines has n integers 0 or 1 separated by spaces. For the j-th 0 or 1 in the i-th line, 1 indicates that the i-th vertex and the j-th vertex are directly connected, and 0 indicates that there is no direct connection. direct connection. When i and j are equal, the corresponding integer is guaranteed to be 0.
Output format
There is only one line, containing n integers, indicating the order of accessing vertices to traverse the entire graph according to the depth-first traversal algorithm in the problem description. Output a space after each integer, and please note the line break at the end of the line.
Input sample
4 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 0
Example output
0 1 3 2
AC code:
#include <iostream>
#include <string>
#include <cstdio>
#include <stack>
#include <queue>
using namespace std;
#defineMAX_SIZE 100
//Graph stored in adjacency matrix
struct graph
{
int vexNumber;
string vexInfo[MAX_SIZE];
int adjMatrix[MAX_SIZE][MAX_SIZE];
};
// Find unvisited adjacent points of v0
// int findAdjVex(const Graph & amp; G, int v0, int visited[]){
// for(int i=0;i<G.vexNumber;i + + )
// if(G.adjMatrix[v0][i]==1 & amp; & amp;visited[i]==0)return i;
// return 0;
// }
// Taking vertex v0 as the starting point, perform a DFS trip
string DFS(const Graph & amp; G, int v0, int visited[]){
string result = "";
result=result + G.vexInfo[v0] + " ";
visited[v0]=1;
for(int i=0;i<G.vexNumber;i + + ){
if(G.adjMatrix[v0][i]==1 & amp; & amp;!visited[i])
result=result + DFS(G,i,visited);
}
return result;
}
// Perform DFS on the entire graph
string DFS(const Graph & amp; G){
string result = "";
// Step 1: Initialize the visited array
int visited[MAX_SIZE]={0};
// Step 2: Use each untraversed vertex as the starting point to perform DFS
for(int i=0;i<G.vexNumber;i + + ){
if(visited[i]==0){
result + =DFS(G,i,visited);
}
}
return result;
}
// please comment the following code when you submit to OJ
int main(){
// freopen("/config/workspace/answer/test.in","r",stdin);
// freopen("/config/workspace/answer/test.out","w",stdout);
GraphG;
cin >> G.vexNumber;
for(int i=0;i<G.vexNumber;i + + ){
G.vexInfo[i] = to_string(i);
for(int j=0;j<G.vexNumber;j + + ){
cin >> G.adjMatrix[i][j];
}
}
string str = DFS(G);
cout << str << endl;
return 0;
}
Issue C: Case 6-1.2: Breadth-first traversal of adjacency list storage graph
Title description
A graph has n nodes numbered from 0 to n-1 and m edges numbered from 0 to m-1. Output the breadth-first traversal order starting from point x.
Input format
The first line is n, m, x.
The next m lines each have a set of u, v. Indicates that point u can reach point v, and point v can also reach point u.
Output format
Output the order of passing points. (Output the lexicographically smallest answer)
Input sample
7 9 5 0 3 0 2 0 4 3 1 3 2 4 5 1 5 2 5 5 6
Example output
5 1 2 4 6 3 0
AC code:
#include <bits/stdc + + .h>
using namespace std;
struct node {
int in, out;
};
int cmp(struct node a, struct node b) {
if (a.in == b.in)
return a.out < b.out;
return a.in < b.in;
}
int main() {
int m, n, x;
cin >> n >> m >> x;
struct node a[m + 5];
for (int i = 0; i < m; i + + ) {
int j, o;
cin >> j >> o;
if (j < o) {
a[i].in = j;
a[i].out = o;
} else {
a[i].in = o;
a[i].out = j;
}
}
sort(a, a + m, cmp);
queue<int> q;
q.push(x);
int visited[n + 5] = {0};
visited[x] = 1;
while (!q.empty()) {
int p = q.front();
cout << p << " ";
q.pop();
for (int i = 0; i < m; i + + ) {
if (a[i].in == p & amp; & amp; !visited[a[i].out]) {
q.push(a[i].out);
visited[a[i].out] = 1;
} else if (a[i].out == p & amp; & amp; !visited[a[i].in]) {
q.push(a[i].in);
visited[a[i].in] = 1;
}
}
}
return 0;
}
Problem D: DFS completion order solution of adjacency matrix storage graph (additional code mode)
Title description
During the depth-first traversal of the graph, if a node p has no unvisited adjacent points, the node p is marked as “complete”.
Please write a program to solve the depth-first traversal completion order of a graph.
This question is in additional code mode. The following code will be automatically appended to the code submitted by students. There is a code framework in the prompt for this question. Please copy it, modify it, comment out part of the code, and finally submit it.
Input format
The first line of input contains a positive integer n, indicating that there are n vertices in the graph. where n does not exceed 26.
By default, the information corresponding to each vertex is lowercase letters from a to z.
Each of the following n lines has n integers 0 or 1 separated by spaces. For the j-th 0 or 1 in the i-th line, 1 indicates that the i-th vertex and the j-th vertex are directly connected, and 0 indicates that there is no direct connection. direct connection. When i and j are equal, the corresponding integer is guaranteed to be 0.
By default, dfs starts from a and continues in sequence.
Output format
There is only one line, containing n letters, indicating the order of visiting vertices to traverse the entire graph according to the depth-first traversal algorithm in the title description.
Input sample
7 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0
Example output
decbgaf
AC code:
#include <iostream>
#include <string>
#include <cstdio>
#include <stack>
#include <queue>
using namespace std;
#defineMAX_SIZE 100
//Graph stored in adjacency matrix
struct graph
{
int vexNumber;
string vexInfo[MAX_SIZE];
int adjMatrix[MAX_SIZE][MAX_SIZE];
};
// Find unvisited adjacent points of v0
int findAdjVex(const Graph & amp; G, int v0, int visited[]){
for(int i=0;i<G.vexNumber;i + + )
if(G.adjMatrix[v0][i]==1 & amp; & amp;!visited[i])return i;
return 0;
}
// Algorithm 7-1: Algorithm for solving DFS completion order starting from a certain node (adjacency matrix)
string DFS_finished(const Graph & amp;G, int v0, int visited[]){
string result="";
visited[v0]=1;
for(int i=0;i<G.vexNumber;i + + ){
if(G.adjMatrix[v0][i]==1 & amp; & amp;!visited[i])
result + =DFS_finished(G,i,visited);
}
result=result + G.vexInfo[v0];
return result;
}
// Algorithm 7: DFS completion order solution algorithm - adjacency matrix
string DFS_finished(const Graph & amp;G){
string result="";
int visited[MAX_SIZE]={0};
for(int i=0;i<G.vexNumber;i + + ){
if(visited[i]==0)result + =DFS_finished(G,i,visited);
}
return result;
}
// please comment the following code when you submit to OJ
int main(){
// freopen("/config/workspace/answer/test.in","r",stdin);
// freopen("/config/workspace/answer/test.out","w",stdout);
Graph G;
cin >> G.vexNumber;
for(int i=0;i<G.vexNumber;i + + ){
G.vexInfo[i] = (char)('a' + i);
for(int j=0;j<G.vexNumber;j + + ){
cin >> G.adjMatrix[i][j];
}
}
string str = DFS_finished(G);
cout << str << endl;
return 0;
}
Question E: Basic Experiment 6-2.3: Save 007
Title description
There is a plot in the old movie “Live and Let Die” where 007 was captured by a drug dealer on a small island in the center of a crocodile pool. He used an extremely bold method to escape – stepping directly into the pool. A series of crocodile’s big heads jumped onto the shore! (It is said that the stuntman was bitten on the foot by the last crocodile. Fortunately, he was wearing specially thickened boots and escaped.)
Assume that the crocodile pool is a square with a length and width of 100 meters, the center coordinate is (0, 0), and the northeast corner coordinate is (50, 50). Chixin Island is a circle with (0, 0) as the center and a diameter of 15 meters. Given the coordinates of the crocodiles distributed in the pool and the maximum distance that 007 can jump at one time, you need to tell him whether it is possible to escape.
Input format
First, the first line gives two positive integers: the number of crocodiles N (≤100) and the maximum distance D that 007 can jump at one time. N lines follow, each giving two integers representing the (x,y) coordinates of a crocodile.
Note: No two crocodiles will stay at the same spot.
Output format
If it is possible for 007 to escape, output “Yes” in one line, otherwise output “No”.
Input sample
14 20 25-15 -25 28 8 49 29 15 -35 -2 5 28 27-29 -8 -28 -20 -35 -25 -20 -13 29 -30 15 -35 40 12 12
Example output
Yes
AC code:
#include <bits/stdc + + .h>
using namespace std;
struct Point{
int x,y;
};
typedef Point Point;
int CanSafe(Point c[],int v,int D){
if(c[v].x + D>=50||c[v].x-D>=50||c[v].y-D>=50||c[v].y + D>=50)return 1;
return 0;
}
int CanJump(Point c[],int v,int u,int D){
if((c[v].x-c[u].x)*(c[v].x-c[u].x) + (c[v].y-c[u].y)*(c[v]. y-c[u].y)<=D*D)return 1;
return 0;
}
int CanFirst(Point c[],int v,int D){
if(c[v].x*c[v].x + c[v].y*c[v].y<=(D + 7.5)*(D + 7.5))return 1;
return 0;
}
int DFS(int N,int D,Point c[],int v,int visited[]){
visited[v]=1;
if(CanSafe(c,v,D))return 1;
for(int i=0;i<N;i + + ){
if(visited[i]==0 & amp; & amp;CanJump(c,v,i,D)){
if(DFS(N,D,c,i,visited)==1)return 1;
}
}
return 0;
}
int DFS(int N,int D,Point c[]){
int visited[N]={0};
for(int i=0;i<N;i + + ){
if(CanFirst(c,i,D) & amp; & amp;visited[i]==0){
visited[i]=1;
if(1==DFS(N,D,c,i,visited))return 1;
}
}
return 0;
}
int main(){
int N,D;
cin>>N>>D;
Point c[N];
for(int i=0;i<N;i + + )cin>>c[i].x>>c[i].y;
int result=DFS(N,D,c);
if(result==1)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
Thanks to Mr. ly for giving a lot of codes in class. Although there are small bugs, can be copied directly, which makes the idea of writing questions clearer
Thank you Jiang for the precious business trip opportunity