Graph of data structure and algorithm

What is a graph

In the previous article, we learned the concept of tree, focusing on binary tree. Graph is a little similar to tree in topology, but graph is not a tree

Intuitively, let's first look at the topology of a graph:

Undirected graph

The above shows an undirected graph. An undirected graph is a graph without direction. As long as two nodes are connected, they can go from one node to another

We can understand it as a simplified map. A-G represents location

Generally, we have the following general concepts for graphs:

  • The nodes of a graph are called vertices;
  • The connection between vertices (nodes) is called edge;
  • How many edges a vertex (node) has is called the degree of the vertex (node);

Correspondingly, there is also a directed graph. A directed graph is a directed graph. The edges of two linked vertices have directions and can go from one vertex to another. If the two vertices are interconnected, there must be at least two edges in different directions

A directed graph is similar to a one-way traffic lane

Directed graph

The edges of a directed graph may point from a vertex or point to a vertex. We call the number of edges pointed from the vertex the degree of the vertex, and the number of edges pointing to a vertex the degree of the vertex

Compared with a map, the edge between two vertices can not only represent the connection relationship, but also the distance. Each edge is given a "distance" parameter (weight). Such a graph is called a weighted graph:

Weighted graph

Analogical object of graph

This data structure can represent some common objects in daily life. Here are some examples:

  • The map can be represented by a graph. The vertex is the place, the edge is the path between two places, and the weight on the edge can represent the distance;
  • Friends can also be represented by a graph. The vertex is each individual, the edge indicates whether there is a connection between the two individuals, and the weight on the edge can indicate the degree of favor;
  • The compiler also uses graphs. The header file include during C/C + + compilation can be represented by graph vertices, and the directed edges can represent dependencies;

Adjacency table storage method

How are diagrams stored?

It is a very intuitive storage method similar to a tree, and uses a linked list to represent the topology of the graph But the problem with this method is that we don't know how many edges each vertex of the graph will have, so it's not easy to define the structure

The adjacency list storage method also uses the linked list storage method. It represents each vertex as the head of the linked list, and the subsequent node is other vertices connected with the vertex. The following figure shows the adjacency list storage method of undirected graph:

[external chain picture transfer failed. The source station may have anti-theft chain mechanism. It is recommended to save the picture and upload it directly (IMG rsuydpxu-1629955069492)( https://s3.ax1x.com/2021/03/09/61qo2q.png )]

Adjacency table storage method

1
2
3
4
5

template <typename T>
struct Graph{
    T val;
    vector<Graph<T>*> link;
};

Above, val represents the value of the vertex, and link stores other vertices connected with this vertex

The link here looks like sequential storage. If the time complexity is O(n) when searching for another vertex connected to the vertex, we can use the search binary tree or red black tree to replace the sequential structure and improve the search efficiency. The specific data structure needs to be analyzed according to the specific scene

Breadth first search (BFS)

The search / traversal of graphs is similar to that of trees. It should be noted that graphs can have loops and do not fall into dead loops

Breadth first search is to access all the child nodes of the starting node first, and then all the child nodes of the asking child node. From the structure of the tree, it is a layer by layer access

Let's use the tree structure to show how BFS Searches:

[the external chain picture transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-xio9leza-1629955069495)( https://s3.ax1x.com/2021/03/10/6GVxfA.png )]

BFS

Define the structure of the diagram first:

1
2
3
4
5
6
7
8

template <typename T>
struct Graph{
    T val;
    vector<Graph<T>*> link;

Graph(const T&amp; v) : val(v) {}

};
using Map = Graph<char>;

Our main function uses the undirected graph above:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

int main()
{
    vector<vector<char>> link_map{
        {'A', 'B'},
        {'B', 'A', 'C', 'E'},
        {'C', 'B', 'D'},
        {'D', 'C', 'E', 'G'},
        {'E', 'B', 'D', 'F'},
        {'F', 'E', 'G'},
        {'G', 'D', 'F'},
    };

auto graph = initGraph(link_map);

return 1;

}

link_ The first element of the bar element of map represents a vertex, and the subsequent elements represent other vertices connected to the vertex;

Write a graph printing function to output graphs using adjacency table storage method:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void printGraph(const vector<Map> &graph)
{
    using std::begin;
    using std::end;
    for_each(begin(graph), end(graph), [](auto& g){
        cout << g.val << "(" << &g << ")";
        auto &link = g.link;
        for_each(begin(link), end(link), [](auto& l){
            cout << "->" << l->val << "(" << l << ")";
        });
        cout << endl;
    });
}

Convert the initialization data of the graph into adjacency table storage:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

vector<Map> initGraph(const vector<vector<char>> &link_map)
{
    using std::next;
    using std::begin;
    using std::end;

vector&lt;Map&gt; graph;
unordered_map&lt;char, int&gt; map_map;
int pos = 0;
for (auto &amp;link : link_map)
{
    const char&amp; c = link[0];
    Map g(c);
    graph.emplace_back(g);
    map_map.emplace(c, pos++);
}

auto g = begin(graph);
for (auto &amp;link : link_map)
{
    for_each(next(begin(link)), end(link), [&amp;](auto&amp; c){
        pos = map_map[c];
        auto pg = &amp;graph[pos];
        g-&gt;link.emplace_back(pg);
    });
    g = next(g);
}

printGraph(graph);

return graph;

}

After initializing the graph, we get the output:

1
2
3
4
5
6
7

A(0x11852a0)->B(0x11852c0)
B(0x11852c0)->A(0x11852a0)->C(0x11852e0)->E(0x1185320)
C(0x11852e0)->B(0x11852c0)->D(0x1185300)
D(0x1185300)->C(0x11852e0)->E(0x1185320)->G(0x1185360)
E(0x1185320)->B(0x11852c0)->D(0x1185300)->F(0x1185340)
F(0x1185340)->E(0x1185320)->G(0x1185360)
G(0x1185360)->D(0x1185300)->F(0x1185340)

For the breadth first search algorithm, we use the open-close table

  • The open table stores the nodes to be accessed next. Generally, a double ended queue can be used;
  • The close d table stores the accessed nodes. Generally, any container can be used;

Next, determine the operation for each node:

  • Judge whether the node has been accessed (whether it is in the close table):
1
2
3
4
5
6
7
8

using std::begin;
using std::end;
auto isInClose = [&vclose](auto& node){
    auto node_pos = find_if(begin(vclose), end(vclose), [&](auto& cnode){
        return cnode == node;
    });
    return node_pos != end(vclose);
};
  • Put the nodes to be accessed next into the open table:
1
2
3

auto openPush = [&vopen](auto& node){
    vopen.emplace_back(node);
};
  • Take the node from the open table and access:
1
2
3
4
5

auto openGet = [&vopen](){
    auto node = vopen.front();
    vopen.pop_front();
    return node;
};

Attention should be paid to the operation of the open table. When pushing, the node is pushed to the end, and when taking elements, it is taken from the beginning

  • For node processing, cout is used here for simplicity
1
2
3

auto processNode = [](auto& node){
    cout << node->val << " ";
};

With the above basic operations, breadth first traversal is implemented as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

void algoBFS(vector<Map>& graph)
{
    deque<Map*> vopen;
    vector<Map*> vclose;

auto isInClose = [&amp;vclose](auto&amp; node){
    auto node_pos = find_if(begin(vclose), end(vclose), [&amp;](auto&amp; cnode){
        return cnode == node;
    });
    return node_pos != end(vclose);
};

auto openPush = [&amp;vopen](auto&amp; node){
    vopen.emplace_back(node);
};

auto openGet = [&amp;vopen](){
    auto node = vopen.front();
    vopen.pop_front();
    return node;
};

auto processNode = [](auto&amp; node){
    cout &lt;&lt; node-&gt;val &lt;&lt; " ";
};

auto node = &amp;graph[0];
openPush(node);
do{
    node = openGet();
    if(!isInClose(node))
    {
        processNode(node);
        vclose.emplace_back(node);
        for(auto&amp; l : node-&gt;link)
        {
            if (!isInClose(l))
            {
                openPush(l);
            }
        }
    }
}while(!vopen.empty());

}

Output:

Depth first search (DFS)

From the tree structure, depth first search is accessed from the root node to the leaf node

Let's use the tree structure to show how DFS Searches:

DFS

The logic of depth first search is basically the same as that of breadth first search. The difference lies in the different ways of obtaining values from the open table

In breadth first search, we push the node to be accessed to the end of the open table, and then take the next accessed node from the header of the open table. As a result, we first access all the child nodes of the node, and then access all the child nodes of the child node

Depth first search is to push the node to be accessed to the end of the open table, and then take the next accessed node from the end of the open table. This is equivalent to tracing the child nodes from a few points to the end

The following is the openGet operation in depth first search:

1
2
3
4
5

auto openGet = [&vopen](){
    auto node = vopen.back();
    vopen.pop_back();
    return node;
};

The complete implementation is as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

void algoDFS(vector<Map>& graph)
{
    deque<Map*> vopen;
    vector<Map*> vclose;

using std::begin;
using std::end;
auto isInClose = [&amp;vclose](auto&amp; node){
    auto node_pos = find_if(begin(vclose), end(vclose), [&amp;](auto&amp; cnode){
        return cnode == node;
    });
    return node_pos != end(vclose);
};

auto openPush = [&amp;vopen](auto&amp; node){
    vopen.emplace_back(node);
};

auto openGet = [&amp;vopen](){
    auto node = vopen.back();
    vopen.pop_back();
    return node;
};

auto processNode = [](auto&amp; node){
    cout &lt;&lt; node-&gt;val &lt;&lt; " ";
};

auto node = &amp;graph[0];
openPush(node);
do{
    node = openGet();
    if(!isInClose(node))
    {
        processNode(node);
        vclose.emplace_back(node);
        for(auto&amp; l : node-&gt;link)
        {
            if (!isInClose(l))
            {
                openPush(l);
            }
        }
    }
}while(!vopen.empty());

}

Output:

Keywords: Algorithm data structure

Added by azn_romeo_4u on Fri, 24 Dec 2021 06:02:08 +0200

Popular Keywords

©2024 Programming VIP