Algorithm Issues in Communication Networks Experiment 4-Depth-First Algorithm and Breadth-First Algorithm (Node Traversal)

Experiment 4 Algorithm issues in communication networks-depth-first algorithm and breadth-first algorithm (node traversal)

1. Introduction

In communication networks, node traversal is an important task that helps understand the topology of the network, identify potential problems, and perform various analyses. Depth-first search algorithm and breadth-first search algorithm are two commonly used graph traversal methods, which can help us understand the connection relationships between nodes in the network.

2. System design requirements

Experimental requirements:

1. Starting from any node, use the depth-first search algorithm to calculate the traversal order of the attached graph and print the output (can two different implementation methods be used);

2. Starting from any node, use the breadth-first search algorithm to calculate the traversal order of the attached graph and print the output (can two different implementation methods be used);

Notice:

1. Please convert the attached graphics to the input data format (attached to the experiment report);

2. When printing, please print the node number and node name in the order of traversal.

Specific display content:

1. Number of nodes**

2. Node number and name**

3. Number of sides**

4. Depth first search results: **** (for example: 1. Chongqing; 4. Shanghai…)

5. Breadth-first search results: ****

6. It is a connected graph, and all nodes are traversed;

It is not a connected graph, and the ** nodes cannot be traversed;

3. Design ideas and plans

1. Program flow chart design

2. Global variables and structures

#define CITY_NUM 10
#define connect 1
#define unconnect 0 // means no connection

int graph[CITY_NUM][CITY_NUM]; // distance between cities
int p[CITY_NUM]; // Array of predecessor nodes, which stores the predecessor nodes of the shortest path
int S[CITY_NUM]; // Mark visited vertices
char cities[CITY_NUM][20] =
{<!-- -->
    "Chongqing",
    "Beijing",
    "Chengdu",
    "Shanghai",
    "Shenzhen",
    "Hangzhou",
    "Guangzhou",
    "Wuhan",
    "Tianjin",
    "Nanjing",
};

3. Algorithm design

3.1 overall code

#include 

#define CITY_NUM 10
#define connect 1
#define unconnect 0 // means no connection

int graph[CITY_NUM][CITY_NUM]; // distance between cities
int p[CITY_NUM]; // Array of predecessor nodes, which stores the predecessor nodes of the shortest path
int S[CITY_NUM]; // Mark visited vertices
char cities[CITY_NUM][20] =
{<!-- -->
    "Chongqing",
    "Beijing",
    "Chengdu",
    "Shanghai",
    "Shenzhen",
    "Hangzhou",
    "Guangzhou",
    "Wuhan",
    "Tianjin",
    "Nanjing",
};

void fileop(void)
{<!-- -->
    FILE *fp;
    int i, j;
    int from, to;
    if ((fp = fopen("input1.txt", "r")) == NULL)
    {<!-- -->
        printf("File opening failed");
    }
    else
    {<!-- -->
        // Initialize the graph and set the weight between each node to 0 to indicate that it is not connected.
        for (i = 0; i < CITY_NUM; i + + )
        {<!-- -->
            for (j = 0; j < CITY_NUM; j + + )
            {<!-- -->
                graph[i][j] = unconnect;
            }
        }
        //Read the weights between file nodes and assign them
        while (fscanf(fp, "%d %d", & amp;from, & amp;to) == 2)
        {<!-- -->
            graph[from - 1][to - 1] = connect;
            graph[to - 1][from - 1] = connect;
        }
        fclose(fp);
    }
}

void printCities()
{<!-- -->
    printf("Node number and name:\
");
    for (int i = 0; i < CITY_NUM; i + + )
    {<!-- -->
        printf("Node %d: %s;\
", i + 1, cities[i]);
    }
    printf("\
");
}

void printEdges()
{<!-- -->
    int nodes = 0;
    printf("Information of all edges:\
");
    for (int i = 0; i < CITY_NUM; i + + )
    {<!-- -->
        for (int j = i + 1; j < CITY_NUM; j + + )
        {<!-- -->
            if (graph[i][j] != unconnect)
            {<!-- -->
                printf("Node %d to node %d \
", i + 1, j + 1);
                nodes + + ;
            }
        }
    }
    printf("Number of edges: %d", nodes);
    printf("\
");
}

void DFS(int node)//Recursive implementation of depth traversal
{<!-- -->
    S[node] = 1; // Mark node as visited
    printf("Node %d: %s\
", node + 1, cities[node]);

    for (int i = 0; i < CITY_NUM; i + + )
    {<!-- -->
        if (graph[node][i] == connect & amp; & amp; S[i] == 0)
        {<!-- -->
            DFS(i);
        }
    }
}

void BFS(int startNode)//Queue implementation breadth traversal
{<!-- -->
    //Reset S array
    for (int i = 0; i < CITY_NUM; i + + )
    {<!-- -->
        S[i] = 0;
    }
    int queue[CITY_NUM];
    int front = 0, rear = 0;

    queue[rear + + ] = startNode;
    S[startNode] = 1; // Mark node as visited

    while (front < rear)
    {<!-- -->
        int currentNode = queue[front + + ];
        printf("Node %d: %s\
", currentNode + 1, cities[currentNode]);

        for (int i = 0; i < CITY_NUM; i + + )
        {<!-- -->
            if (graph[currentNode][i] == connect & amp; & amp; S[i] == 0)
            {<!-- -->
                queue[rear + + ] = i;
                S[i] = 1; // Mark node as visited
            }
        }
    }
}

int isConnectedGraph()
{
    int temp=0;
    int flag=-1;//Return the corresponding disconnected node (returning -1 means fully connected)
    for (int i = 0; i < CITY_NUM; i + + )
    {
        for(int j = 0; j
            if (graph[i][j] == unconnect)
            {
                temp + + ;
            }
        }
        if(temp > CITY_NUM-1)//If the distance to each node is unconnect, it will not be connected.
        {
            flag = i;
        }
        temp=0;
    }
    return flag;
}

int main()
{<!-- -->
    int startNode; // Get the starting node entered by the user
    fileop();
    printCities();
    printEdges();

    printf("Please enter the starting node number (1-%d): ", CITY_NUM);
    scanf("%d", & amp;startNode);

    if (startNode < 1 || startNode > CITY_NUM)
    {<!-- -->
        printf("Invalid input.\
");
        return 1;
    }

    startNode=startNode-1; //The array number corresponds to the node number minus 1

    //Perform a depth-first search
    printf("Depth first search results:\
");
    DFS(startNode);

    //Perform breadth first search
    printf("Breadth-first search results:\
");
    BFS(startNode);

    if (isConnectedGraph()==-1)
    {<!-- -->
        printf("It is a connected graph, all nodes are traversed.\
");
    }
    else
    {<!-- -->
        printf("Not a connected graph, node %d cannot be traversed.\
",isConnectedGraph() + 1);
    }

    return 0;
}

3.2 File reading and graph construction

Convert the graphics to the input data format and save it in the input1.txt file. Complete reading the input1.txt file and constructing the graph structure

1 2
1 3
1 4
twenty three
2 5
3 4
3 5
3 6
4 6
4 7
4 9
5 6
5 8
6 3
6 7
6 8
7 8
7 10

void fileop(void)
{<!-- -->
    FILE *fp;
    int i, j;
    int from, to;
    if ((fp = fopen("input1.txt", "r")) == NULL)
    {<!-- -->
        printf("File opening failed");
    }
    else
    {<!-- -->
        // Initialize the graph and set the weight between each node to 0 to indicate that it is not connected.
        for (i = 0; i < CITY_NUM; i + + )
        {<!-- -->
            for (j = 0; j < CITY_NUM; j + + )
            {<!-- -->
                graph[i][j] = unconnect;
            }
        }
        //Read the weights between file nodes and assign them
        while (fscanf(fp, "%d %d", & amp;from, & amp;to) == 2)
        {<!-- -->
            graph[from - 1][to - 1] = connect;
            graph[to - 1][from - 1] = connect;
        }
        fclose(fp);
    }
}

3.3 Print and display information

void printCities()
{<!-- -->
    printf("Node number and name:\
");
    for (int i = 0; i < CITY_NUM; i + + )
    {<!-- -->
        printf("Node %d: %s;\
", i + 1, cities[i]);
    }
    printf("\
");
}

void printEdges()
{<!-- -->
    int nodes = 0;
    printf("Information of all edges:\
");
    for (int i = 0; i < CITY_NUM; i + + )
    {<!-- -->
        for (int j = i + 1; j < CITY_NUM; j + + )
        {<!-- -->
            if (graph[i][j] != unconnect)
            {<!-- -->
                printf("Node %d to node %d \
", i + 1, j + 1);
                nodes + + ;
            }
        }
    }
    printf("Number of edges: %d", nodes);
    printf("\
");
}

3.4 Depth traversal algorithm (DFS) and breadth traversal algorithm (BFS)

void DFS(int node)//Recursive implementation of depth traversal
{<!-- -->
    S[node] = 1; // Mark node as visited
    printf("Node %d: %s\
", node + 1, cities[node]);

    for (int i = 0; i < CITY_NUM; i + + )
    {<!-- -->
        if (graph[node][i] == connect & amp; & amp; S[i] == 0)
        {<!-- -->
            DFS(i);
        }
    }
}

void BFS(int startNode)//Queue implementation breadth traversal
{<!-- -->
    //Reset S array
    for (int i = 0; i < CITY_NUM; i + + )
    {<!-- -->
        S[i] = 0;
    }
    int queue[CITY_NUM];
    int front = 0, rear = 0;

    queue[rear + + ] = startNode;
    S[startNode] = 1; // Mark node as visited

    while (front < rear)
    {<!-- -->
        int currentNode = queue[front + + ];
        printf("Node %d: %s\
", currentNode + 1, cities[currentNode]);

        for (int i = 0; i < CITY_NUM; i + + )
        {<!-- -->
            if (graph[currentNode][i] == connect & amp; & amp; S[i] == 0)
            {<!-- -->
                queue[rear + + ] = i;
                S[i] = 1; // Mark node as visited
            }
        }
    }
}

3.5 Determine whether it is a connected graph

int isConnectedGraph()
{<!-- -->
    int temp=0;
    int flag=-1;//Return the corresponding disconnected node (returning -1 means fully connected)
    for (int i = 0; i < CITY_NUM; i + + )
    {<!-- -->
        for(int j = 0; j<CITY_NUM; j + + ){<!-- -->
            if (graph[i][j] == unconnect)
            {<!-- -->
                temp + + ;
            }
        }
        if(temp>CITY_NUM-1)//If the distance to each node is unconnect, it will not be connected.
        {<!-- -->
            flag = i;
        }
        temp=0;
    }
    return flag;
}

3.6 Main function

int main()
{<!-- -->
    int startNode; // Get the starting node entered by the user
    fileop();
    printCities();
    printEdges();

    printf("Please enter the starting node number (1-%d): ", CITY_NUM);
    scanf("%d", & amp;startNode);

    if (startNode < 1 || startNode > CITY_NUM)
    {<!-- -->
        printf("Invalid input.\
");
        return 1;
    }

    startNode=startNode-1; //The array number corresponds to the node number minus 1

    //Perform a depth-first search
    printf("Depth first search results:\
");
    DFS(startNode);

    //Perform breadth first search
    printf("Breadth-first search results:\
");
    BFS(startNode);

    if (isConnectedGraph()==-1)
    {<!-- -->
        printf("It is a connected graph, all nodes are traversed.\
");
    }
    else
    {<!-- -->
        printf("Not a connected graph, node %d cannot be traversed.\
",isConnectedGraph() + 1);
    }

    return 0;
}

4. Debugging

5. Experience

When writing the isconnectedGraph() function, the code is always unable to return non-connected corresponding nodes. Even if there is no problem with the logic, repeated modifications and debugging are frustrating and doubtful whether this will work. Pass. However, it is often some minor errors that lead to inconsistent running results. For example, the temp used to record whether each node is connected is not cleared in time. Therefore, debugging code not only requires confidence in yourself, but also requires care and a solid foundation.

6. Opinions

Seven. Appendix

Results display