[for beginners] PTA 06 - Figure 3 six dimensional space (30 points) DFS passes test point 4

Non subject class Xiaobai, record the learning process

The first reaction to this question is dfs, which is easy to record the number of layers, but dfs has defects. See details for details

"Why not use DFS" https://blog.csdn.net/sharemon/article/details/102857989 .

Such as data (1)

8 8			
1 3			
1 2			
2 3			
3 4
4 5
5 6
6 7
7 8

2. Data obtained by exchanging 3 rows (2)

8 8
1 2
1 3
2 3
3 4
4 5
5 6
6 7
7 8

Using the following code will get different results

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MaxVertex 1002
typedef int Vertex;
typedef struct ENode{
    Vertex V1, V2;
} *Edge;
typedef struct VNode *PTVNode;
struct VNode{
    Vertex Adj;
    PTVNode Next;
};
typedef struct AdjVNode *PTAdjVNode;
typedef struct AdjVNode{
    PTVNode FistEdge;
} AdjList[MaxVertex];
typedef struct GNode{
    int Ne, Nv;
    AdjList Graph;
} *LGNode;
void dfs(LGNode s,PTVNode w,bool*visited,int Level){
    while(w&&Level<=6){
        if(!visited[w->Adj]){
            visited[w->Adj] = true;
            dfs(s, s->Graph[w->Adj].FistEdge, visited, Level + 1);
        }
        w = w->Next;
    }
}
float Degree(LGNode s,int n){
    bool visited[MaxVertex] = {false};
    visited[n] = true;int i;float count;
    PTVNode w = s->Graph[n].FistEdge;
    dfs(s, w, visited, 1);
    for (i=1,count=0; i <= s->Nv;i++)
        if(visited[i])count++;
    count /= s->Nv;
    return count;
}
void Insert(LGNode S, Edge E, bool flag){
    PTVNode w;
    w = (PTVNode)malloc(sizeof(struct VNode));
    w->Adj = E->V2;
    w->Next = S->Graph[E->V1].FistEdge;
    S->Graph[E->V1].FistEdge = w;
    if(flag){
        Vertex temp;
        temp = E->V1;E->V1 = E->V2;E->V2 = temp;
        Insert(S, E, false);
    }
}
LGNode BulidLGraph(int N,int M){
    LGNode S;Edge E;int i;
    S = (LGNode)malloc(sizeof(struct GNode));
    S->Nv = N;
    S->Ne = M;
    for (i = 1; i<=N;i++)
        S->Graph[i].FistEdge = NULL;
    for (i = 1; i <= M;i++){
        E = (Edge)malloc(sizeof(struct ENode));
        scanf("%d%d", &E->V1, &E->V2);
        Insert(S, E, true);
    }
    return S;
}
int main()
{
    int N, M;float m;
    LGNode Sosial;
    scanf("%d%d", &N, &M);
    Sosial = BulidLGraph(N, M);
    for (int i=1; i <= N;i++){
        m = Degree(Sosial, i) * 100;
        printf("%d: %.2f%%\n",i, m);
    }
    return 0;
}

Data 1 Data 2
8 8 8 8
1 3 1 2
1 2 1 3
2 3 2 3
3 4 3 4
4 5 4 5
5 6 5 6
7 8 7 8
1: 87.50% 1: 100.00%
2: 100.00% 2: 100.00%
3: 100.00% 3: 100.00%
4: 100.00% 4: 100.00%
5: 100.00% 5: 100.00%
6: 100.00% 6: 100.00%
7: 100.00% 7: 100.00%
8: 100.00% 8: 100.00%

The reason is that the head interpolation method is used when establishing the adjacency table, and the path 1 - > 2 - > 3 - > 4 - > 5 - > 6 - > 7 - > 8 is traversed first in data 1. However, when traversing to No. 7, because the maximum number of stack layers is 6, traversing to No. 7 has stopped. For the second path, 1 - > 3 - > 4 - > 5 - > 6 - > 7 - > 8. Since No. 3 has been marked in the long path, the path cannot be traversed because No. 3 is skipped, so No. 8 cannot be accessed.
For data 2, the short path is traversed first, so No. 8 of layer 6 can be accessed. Then traverse the long path and visit No. 2. All the data in the code 1 is accessed.
This is because the access order of dfs is related to the order of input edges and the method of establishing adjacency table. dfs cannot selectively access the shortest path first. If you happen to access the long path first, the end vertices of the short path will not be accessed because the common vertices of the precursor are marked.
A scheme that this rookie came up with is to change the original bool type visited array into an integer array that records the number of access layers

bool visited[MaxVertex] = {false};

Change to

int visited[MaxVertex] = {0};

Here 0 still means that it has not been visited.
Put the original dfs function

void dfs(LGNode s,PTVNode w,bool*visited,int Level){
    while(w&&Level<=6){
        if(!visited[w->Adj]){
            visited[w->Adj] = true;
            dfs(s, s->Graph[w->Adj].FistEdge, visited, Level + 1);
        }
        w = w->Next;
    }
}

Change to

void dfs(LGNode s,PTVNode w,int*visited,int Level){
    while(w&&Level<=6){
        if(!visited[w->Adj]||Level<visited[w->Adj]){
            visited[w->Adj] = Level;
            dfs(s, s->Graph[w->Adj].FistEdge, visited, Level + 1);
        }
        w = w->Next;
    }
}

Consider the case of accessing the long path first and then the short path. For example, when the long path accesses No. 3 visited[3]= =2 in the second layer, and then accesses the short path, the number of stack layers is Level==1; This means that there may be inaccessible vertices (7 layers in the long path and 6 layers in the short path).

However, this method will also cause a lot of repeated traversal, and the time complexity will increase greatly. Attached drawings;

Test point diagram rewritten by bsf is attached

Tags: Algorithm data structure dfs pta

Posted by aaronlzw_21 on Tue, 24 May 2022 01:28:07 +0300