A graph is a flexible data structure that typically serves as a model for defining relationships or connections between objects. Objects are represented by vertices (V), and relationships or associations between objects are represented by edges (E) of the graph. Graphs can be divided into directed graphs and undirected graphs. Generally, G=(V,E) is used to represent graphs. An adjacency matrix or adjacency list is often used to describe a graph. In the basic algorithm of graph, the first thing to contact is the graph traversal algorithm, which can be divided into breadth-first search (BFS) and depth-first search (DFS) according to the order of accessing nodes.

Breadth first search (BFS) Breadth first search accesses all the adjacent nodes of the current vertex before traversing the vertex further in the graph. A. First select a vertex as the starting node and dye it gray while the rest of the nodes are white. B. Put the starting node into the queue. C. Select a vertex from the beginning of the queue, find all adjacent nodes, put the found adjacent nodes into the end of the queue, paint the visited nodes black, and the unvisited nodes white. If the color of vertices is gray, it is found and placed in the queue, if the color of vertices is white, it is not found d. The next node in the queue is processed in the same way. Basically, the top of the queue is black, the top of the queue is gray, and the top of the queue is white. A diagram to express this process is as follows:

- Initial state, starting from vertex 1, queue ={1}
- Access the adjacent vertices of 1, 1 out of queue black, 2,3 in queue, queue ={2,3,}
- Access the adjacent node of 2, 2 out,4 in, queue ={3,4}
- Access 3 adjacent node, 3 out of queue, queue ={4}
- Access the adjacent node of 4, 4 out of queue, queue ={null} node 5 is unreachable to 1. The above graph can be represented by the following adjacency matrix:

```
int maze[5][5] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 1, 0 },
{ 0, 1, 1, 1, 0 },
{ 1, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 0 }
};
Copy the code
```

The BFS core code is as follows:

```
#include <iostream>
#include <queue>
#define N 5
using namespace std;
int maze[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 1, 0 },
{ 0, 1, 1, 1, 0 },
{ 1, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 0 }
};
int visited[N + 1] = { 0, };
void BFS(int start)
{
queue<int> Q;
Q.push(start);
visited[start] = 1;
while(! Q.empty()) { int front = Q.front(); cout << front <<"";
Q.pop();
for (int i = 1; i <= N; i++)
{
if(! visited[i] && maze[front - 1][i - 1] == 1) { visited[i] = 1; Q.push(i); } } } } intmain()
{
for (int i = 1; i <= N; i++)
{
if (visited[i] == 1)
continue;
BFS(i);
}
return 0;
}
Copy the code
```

Depth-first search (DFS) After a vertex is accessed during the search, a depth-first search recursively accesses all unaccessed adjacent vertices of that vertex. In the initial condition, all nodes are white. Select one as the starting vertex and follow the following steps to iterate: a. B. Select one of the adjacent vertices of the vertex and continue the process (i.e. find the adjacent nodes of the adjacent nodes) until a vertex has no adjacent nodes, and black it, indicating that the vertex has been accessed. Go back to the vertex above the blackened vertex, find the remaining adjacent nodes of the vertex above the blackened vertex, and continue. If all the adjacent nodes have been accessed from below, black themselves, and go back to the next level above. D. Continue at the next level until all vertices have been accessed. This process can be more clearly expressed in a diagram:

- The initial state, we start at vertex one
- After visiting vertex 1,2, and 3, it terminates at vertex 3
- Go back from vertex 3 to vertex 2, continue to access vertex 5, and terminate at vertex 5
- We go back from vertex 5 to vertex 2, and we end at vertex 2
- We go back from vertex 2 to vertex 1 and end at vertex 1
- The access starts at vertex 4 and ends at vertex 4

The above graph can be represented by the following adjacency matrix:

```
int maze[5][5] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 0 },
{ 1, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0 }
};
Copy the code
```

The DFS core code is as follows (implemented recursively) :

```
#include <iostream>
#define N 5
using namespace std;
int maze[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 0 },
{ 1, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0 }
};
int visited[N + 1] = { 0, };
void DFS(int start)
{
visited[start] = 1;
for (int i = 1; i <= N; i++)
{
if(! visited[i] && maze[start - 1][i - 1] == 1) DFS(i); } cout << start <<"";
}
int main()
{
for (int i = 1; i <= N; i++)
{
if (visited[i] == 1)
continue;
DFS(i);
}
return 0;
}
Copy the code
```

Non-recursion is implemented as follows, using a stack:

```
#include <iostream>
#include <stack>
#define N 5
using namespace std;
int maze[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 0 },
{ 1, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0 }
};
int visited[N + 1] = { 0, };
void DFS(int start)
{
stack<int> s;
s.push(start);
visited[start] = 1;
bool is_push = false;
while(! s.empty()) { is_push =false;
int v = s.top();
for (int i = 1; i <= N; i++)
{
if(maze[v - 1][i - 1] == 1 && ! visited[i]) { visited[i] = 1; s.push(i); is_push =true;
break; }}if(! is_push) { cout << v <<"";
s.pop();
}
}
}
int main()
{
for (int i = 1; i <= N; i++)
{
if (visited[i] == 1)
continue;
DFS(i);
}
return 0;
}
Copy the code
```

It is also possible for DFS to access the node read first and then not output the node when traceback occurs. The difference between the algorithm and what I did up here is the timing of the output point is different, but the idea is the same. DFS has good applications in both loop monitoring and topological sorting.

PS: The text and text are my original, painting for several hours, reprint indicate the source, respect knowledge labor, thank you ~