[Data algorithm and structure] The unweighted directed graph G is stored in an adjacency list, find the in-degree and out-degree of each vertex in the graph G, find the vertex with the largest out-degree in the graph G and output the vertex number, calculate the number of vertices with an out-degree of 0 in the graph G, and judge whether there is an edge <i,j> in the graph G

Title

Question:?Try to write an algorithm assuming that the unweighted directed graph G is stored in an adjacency list, and design and implement algorithms to solve the following problems.

1. Find the in-degree of each vertex in graph G.
2. Find the out-degree of each vertex in graph G.
3. Find the vertex with the largest out-degree in graph G, and output the vertex number.
4. Compute the number of vertices in graph G with out-degree 0.
5. Determine whether there is an edge in graph G

Data structure and definition

#include <stdio.h>
#include <iostream>

using namespace std;

#define MaxSize 20 // Maximum number of vertices
struct Node
{<!-- -->
    int weight;
    int index;
    struct Node *next;
};
struct HNode
{<!-- -->
    char nodeData;
    struct Node *next;
};
struct Graph
{<!-- -->
    int vertexNum;
    int arcNum;
    bool is Direted;
    HNode verList[MaxSize];
};

The graph structure used in this question

Adjacency list of the graph

Find the in-degree of each vertex in graph G

void HNodeIndegree(Graph G)
{<!-- -->
    int IndegreeCnt[G.vertexNum] = {<!-- -->0};
    for (int i = 0; i < G.vertexNum; i ++ )
    {<!-- -->
        Node *tmp = G.verList[i].next;
        while (tmp != nullptr)
        {<!-- -->
            IndegreeCnt[tmp->index] + + ;
            tmp = tmp->next;
        }
    }
    cout << "all node's indegree" << endl;
    for (int j = 0; j < G.vertexNum; j++ )
    {<!-- -->
        cout << G.verList[j].nodeData << ':' << IndegreeCnt[j] << endl;
    }
}

Find the out-degree of each vertex in graph G

void HNodeOutdegree(Graph G)
{<!-- -->
    int OutdegreeCnt[G.vertexNum] = {<!-- -->0};
    for (int i = 0; i < G.vertexNum; i ++ )
    {<!-- -->
        Node *tmp = G.verList[i].next;
        while (tmp != nullptr)
        {<!-- -->
            OutdegreeCnt[i] + + ;
            tmp = tmp->next;
        }
    }
    cout << "all node's outdegree" << endl;
    for (int j = 0; j < G.vertexNum; j++ )
    {<!-- -->
        cout << G.verList[j].nodeData << ':' << OutdegreeCnt[j] << endl;
    }
}

Find the vertex with the largest out-degree in graph G, and output the vertex number

void MaxOutDegreeNode(Graph G)
{<!-- -->
    int index = -1; // the array subscript with the largest out degree
    int res = 0; // out degree
    // Same as HNodeOutdegree
    // same code
    int OutdegreeCnt[G.vertexNum] = {<!-- -->0};
    for (int i = 0; i < G.vertexNum; i ++ )
    {<!-- -->
        Node *tmp = G.verList[i].next;
        while (tmp != nullptr)
        {<!-- -->
            OutdegreeCnt[i] + + ;
            tmp = tmp->next;
        }
    }
    // same code

    for (int j = 0; j < G.vertexNum; j++ )
    {<!-- -->
        if (OutdegreeCnt[j] > res)
        {<!-- -->
            res = OutdegreeCnt[j];
            index = j;
        }
    }
    cout << "the max out degree is" << ':' << G.verList[index].nodeData << endl;
}

Calculate the number of vertices whose out-degree is 0 in graph G

void Zero Outdegree(Graph G)
{<!-- -->
    int cnt = 0;
    // same code
    int OutdegreeCnt[G.vertexNum] = {<!-- -->0};
    for (int i = 0; i < G.vertexNum; i ++ )
    {<!-- -->
        Node *tmp = G.verList[i].next;
        while (tmp != nullptr)
        {<!-- -->
            OutdegreeCnt[i] + + ;
            tmp = tmp->next;
        }
    }
    // same code
    for (int j = 0; j < G.vertexNum; j++ )
    {<!-- -->
        if (OutdegreeCnt[j] == 0)
        {<!-- -->
            cnt + + ;
        }
    }
    cout << "the number of zero outdegree is" << ' ' << cnt;
}

Judge whether there is an edge

in graph G

bool IsArcExist(char a, char b, Graph G)
{<!-- -->
    int AIndex, BIndex; // Find the array index of arc head and arc tail
    for (int i = 0; i < G.vertexNum; i ++ )
    {<!-- -->
        if (G.verList[i].nodeData == a)
        {<!-- -->
            AIndex = i;
            continue;
        }
        if (G.verList[i].nodeData == b)
        {<!-- -->
            BIndex = i;
            continue;
        }
    }
    Node *tmp = G.verList[AIndex].next;
    while (tmp != nullptr)
    {<!-- -->
        if (tmp->index == BIndex)
        {<!-- -->
            return true;
        }
        tmp = tmp->next;
    }
    return false;
}

Complete code

#include <stdio.h>
#include <iostream>

using namespace std;

#define MaxSize 20 // Maximum number of vertices
struct Node
{<!-- -->
    int weight;
    int index;
    struct Node *next;
};
struct HNode
{<!-- -->
    char nodeData;
    struct Node *next;
};
struct Graph
{<!-- -->
    int vertexNum;
    int arcNum;
    bool is Direted;
    HNode verList[MaxSize];
};

int Locate(char c, Graph G)
{
    int index = -1;
    for (int i = 0; i < G.vertexNum; i ++ )
    {
        if (G.verList[i].nodeData == c)
        {
            index = i;
        }
    }
    return index;
}

void InsertVex(Graph & G, char v)
{
    G.verList[G.vertexNum].nodeData = v;
    G.verList[G.vertexNum].next = nullptr;
    G.vertexNum++;
}

void InsertArc(Graph & G, char tail, char head)
{
    int TailIndex, HeadIndex;
    TailIndex = Locate(tail, G);
    HeadIndex = Locate(head, G);
    if (HeadIndex == -1 || TailIndex == -1) // The input arc head or arc tail does not exist
    {
        return;
    }
    // Regardless of whether G is a directed graph or an undirected graph
    Node *newNode = new Node;
    newNode->next = G.verList[TailIndex].next; // head insertion into the adjacency list
    newNode->index = HeadIndex;
    G.verList[TailIndex].next = newNode;
    if (!G.isDireted) // G is an undirected graph
    {
        Node *newNode = new Node;
        newNode->next = G.verList[HeadIndex].next; // Head insertion into the adjacency list
        newNode->index = TailIndex;
        G.verList[HeadIndex].next = newNode;
    }
}

void DeleteVex(Graph & G, char v)
{
    int index = Locate(v, G); // the index of the vertex
    // Release all edges related to this vertex
    Node *p = G.verList[index].next; // Temporary pointer p points to the first node of the vertex adjacency list
    while (p != nullptr)
    {
        if (!G.isDireted) // G is an undirected graph
        {
            Node *q = G.verList[p->index].next; // Temporary pointer q points to the first node in the adjacency list where the node to be deleted is located
            while (q->next->index != index) // keep searching until the index value of the next node of q is found to be the index of the deleted vertex
            {
                q = q->next;
            }
            Node *needDel = q->next; // Create a temporary pointer pointing to the node to be deleted
            q->next = needDel->next; // Ensure the adjacency list is continuous
            free(needDel); // release space
        }
        G.verList[index].next = p->next;
        G.arcNum--;
        free(p);
    }
    // release vertices
    G.verList[index].nodeData = NULL;
    G.verList[index].next = nullptr;
    G.vertexNum--;
    return;
}

void DeleteArc(Graph & G, char tail, char head)
{
    int TailIndex = Locate(tail, G);
    int HeadIndex = Locate(head, G);
    Node *p = G.verList[TailIndex].next; // The temporary pointer p points to the first node of the arc tail vertex adjacency list
    while (p->next->index != HeadIndex)
    {
        p = p->next;
    }
    Node *needDel = p->next;
    p->next = needDel->next;
    free(needDel);
    G.arcNum--;
    if (!G.isDireted) // G is an undirected graph
    {
        Node *q = G.verList[HeadIndex].next;
        while (q->next->index != TailIndex)
        {
            q = q->next;
        }
        needDel = q->next;
        q->next = needDel->next;
        free(needDel);
    }
}
void CreateGraph(Graph & G)
{
    cin >> G.vertexNum >> G.arcNum; // Enter the number of vertices and edges
    cin >> G.isDireted; // Whether the input is a directed graph
    if (G.vertexNum > MaxSize)
    {
        return;
    }
    // Initialize the vertex list
    for (int i = 0; i < G.vertexNum; i ++ )
    {
        cin >> G.verList[i].nodeData;
        G.verList[i].next = nullptr;
    }
    // Enter the information of each side in turn
    for (int j = 0; j < G.arcNum; j++ )
    {
        char ArcHead, ArcTail;
        cin >> ArcTail >> ArcHead;
        InsertArc(G, ArcTail, ArcHead);
    }
}

void HNodeIndegree(Graph G)
{<!-- -->
    int IndegreeCnt[G.vertexNum] = {<!-- -->0};
    for (int i = 0; i < G.vertexNum; i ++ )
    {<!-- -->
        Node *tmp = G.verList[i].next;
        while (tmp != nullptr)
        {<!-- -->
            IndegreeCnt[tmp->index] + + ;
            tmp = tmp->next;
        }
    }
    cout << "all node's indegree" << endl;
    for (int j = 0; j < G.vertexNum; j++ )
    {<!-- -->
        cout << G.verList[j].nodeData << ':' << IndegreeCnt[j] << endl;
    }
}

void HNodeOutdegree(Graph G)
{<!-- -->
    int OutdegreeCnt[G.vertexNum] = {<!-- -->0};
    for (int i = 0; i < G.vertexNum; i ++ )
    {<!-- -->
        Node *tmp = G.verList[i].next;
        while (tmp != nullptr)
        {<!-- -->
            OutdegreeCnt[i] + + ;
            tmp = tmp->next;
        }
    }
    cout << "all node's outdegree" << endl;
    for (int j = 0; j < G.vertexNum; j++ )
    {<!-- -->
        cout << G.verList[j].nodeData << ':' << OutdegreeCnt[j] << endl;
    }
}

void MaxOutDegreeNode(Graph G)
{<!-- -->
    int index = -1; // the array subscript with the largest out degree
    int res = 0; // out degree
    // Same as HNodeOutdegree
    // same code
    int OutdegreeCnt[G.vertexNum] = {<!-- -->0};
    for (int i = 0; i < G.vertexNum; i ++ )
    {<!-- -->
        Node *tmp = G.verList[i].next;
        while (tmp != nullptr)
        {<!-- -->
            OutdegreeCnt[i] + + ;
            tmp = tmp->next;
        }
    }
    // same code

    for (int j = 0; j < G.vertexNum; j++ )
    {<!-- -->
        if (OutdegreeCnt[j] > res)
        {<!-- -->
            res = OutdegreeCnt[j];
            index = j;
        }
    }
    cout << "the max out degree is" << ':' << G.verList[index].nodeData << endl;
}

void ZeroOutdegree(Graph G)
{
    int cnt = 0;
    // same code
    int OutdegreeCnt[G.vertexNum] = {0};
    for (int i = 0; i < G.vertexNum; i ++ )
    {
        Node *tmp = G.verList[i].next;
        while (tmp != nullptr)
        {
            OutdegreeCnt[i] + + ;
            tmp = tmp->next;
        }
    }
    // same code
    for (int j = 0; j < G.vertexNum; j++ )
    {
        if (OutdegreeCnt[j] == 0)
        {
            cnt + + ;
        }
    }
    cout << "the number of zero outdegree is" << ' ' << cnt;
}

bool IsArcExist(char a, char b, Graph G)
{<!-- -->
    int AIndex, BIndex; // Find the array index of arc head and arc tail
    for (int i = 0; i < G.vertexNum; i ++ )
    {<!-- -->
        if (G.verList[i].nodeData == a)
        {<!-- -->
            AIndex = i;
            continue;
        }
        if (G.verList[i].nodeData == b)
        {<!-- -->
            BIndex = i;
            continue;
        }
    }
    Node *tmp = G.verList[AIndex].next;
    while (tmp != nullptr)
    {<!-- -->
        if (tmp->index == BIndex)
        {<!-- -->
            return true;
        }
        tmp = tmp->next;
    }
    return false;
}

int main()
{
    Graph G;
    CreateGraph(G);
    // HNodeIndegree(G);
    // HNodeOutdegree(G);
    // MaxOutDegreeNode(G);
    // ZeroOutdegree(G);
    // char head, tail;
    // cin >> head >> tail;
    // bool isit = IsArcExist(head, tail, G);
    // cout << isit << endl;
    return 0;
}

Conclusion

Because it is an algorithmic side dish, the methods and ideas provided may not be very good. Please bear with me~ If you have any questions, please leave a message to discuss. If you think this article is helpful to you, can you give me a free like? The communication between us is my biggest motivation!