图(plus)DFS(e.g.)

图的专有名词

顶点(vertex) 边(edge) 路径 无向图 有向图 带权图 边带权值**

ABCDE均为顶点，AB BC等均为边 A到C的路径有A->B->C,A->C 上图为一个无向图，顶点之间的连接无方向 顾名思义，有向图就是顶点之间的连接有方向

图的表示方式

1.邻阶矩阵（二维数组） 2.邻接表（链表）

DFS

DFS,即深度优先搜索 首先访问第一个邻接结点，再以这个结点作为初始访问结点，访问它的第一个邻接结点，是一个递归的过程 思路

访问初始结点，并标记它已被访问查找它的第一个邻接结点x若这个邻接结点x不存在,则回到第一步，并从下一个结点开始访问若x未被访问，则循环123查找结点的下一个邻接结点，转到操作3

核心代码 C++实现

void dfs(int i) { cout << vertex[i] << "-> "; vis[i] = true; int fn = findFirstNeighbor(i); while (fn != -1) { if (!vis[fn]) { dfs(fn); } fn = findNextNeighbor(i, fn); } } void dfs() { for (int i = 0; i < vertex.size(); i++) { if (!vis[i]) { dfs(i); } } }

e.g.Prime Ring Problem

AC code

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> using namespace std; int matrix[37] = { 0,0,1,1,0,1, 0,1,0,0,0,1, 0,1,0,0,0,1, 0,1,0,0,0,1, 0,0,0,0,0,1, 0,1,0,0,0,0,0 }; int res[25]; bool vis[25]; void dfs(int index, int n); int main() { int n,num=0; while (cin >> n) { num++; memset(res, 0, sizeof(res)); memset(vis, 0, sizeof(vis)); res[0] = 1; vis[1] = true; cout << "Case " << num << ":" << endl; dfs(1, n); cout << endl; } return 0; } void dfs(int index, int n) { if (n == index) { if (matrix[1 + res[index-1]]) { for (int i = 0; i < n; i++) { if (i != n - 1) { cout << res[i] << " "; } else { cout << res[i] << endl; } } } } else { for (int i = 2; i <= n; i++) { if (!vis[i] && matrix[i + res[index - 1]]) { res[index] = i; vis[i] = true; dfs(index + 1, n); vis[i] = false; } } } }

用空间换时间+dfs dfs+bfs input

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

output

1 2 5 6 3 7 8 4 1 2 3 4 5 6 7 8 #define _CRT_SECURE_NO_WARNINGS #include<bits/stdc++.h> using namespace std; int n, m; bool vis1[100005]; bool vis2[100005]; struct Edge { int begin; int end; }; vector<Edge>edge; vector<int>v[1000005]; void dfs(int index); void bfs(int index); bool cmp(Edge& e1, Edge& e2) { if (e1.end == e2.end)return e1.begin < e2.begin; return e1.end < e2.end; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; edge.push_back(Edge{ u, v }); } sort(edge.begin(),edge.end(), cmp); for (int i = 0; i < m; i++) { v[edge[i].begin].push_back(i); } dfs(1); cout << endl; bfs(1); return 0; } void dfs(int index) { cout << index << " "; vis1[index] = true; for (int i = 0; i < v[index].size(); i++) { int vertex = edge[v[index][i]].end; if (!vis1[vertex]) { dfs(vertex); } } } void bfs(int index) { queue<int>q; q.push(index); cout << index << " "; vis2[index] = true; while (!q.empty()) { int f = q.front(); for (int i = 0; i < v[f].size(); i++) { int vertex = edge[v[f][i]].end; if (!vis2[vertex]) { q.push(vertex); cout << vertex << " "; vis2[vertex] = true; } } q.pop(); } }