图的类型与表示

图结构基本概念

图形可视化交互区

布局:

选择图示例:

当前图的属性总结

数据结构表示区

邻接矩阵

邻接表

邻接矩阵: 行/列代表节点。单元格 `[i][j]` 的值表示从节点 `i` 到节点 `j` 的边的权重 (或1代表存在边)。0 或空表示无直连边。无向图的矩阵是对称的。可通过编辑单元格修改图结构 (对角线不可编辑)。

邻接表: 列出每个节点及其直接连接的邻居。格式为 `节点: 邻居1(权重), 邻居2(权重), ...`。此区域为只读，反映当前图状态。

检测图中的环:

使用三种颜色（状态）标记节点：白色（未访问）、灰色（正在访问，在当前递归栈中）、黑色（已访问完成）。
从一个白色节点开始DFS。
将当前节点标记为灰色。
遍历其邻居：
- 如果遇到白色邻居，递归访问它。
- 如果遇到灰色邻居，说明遇到了返祖边，检测到环。
- 如果遇到黑色邻居，忽略它（它及其子树已探索完毕）。
当一个节点的所有邻居都处理完毕后，将其标记为黑色。
对图中所有未访问过的节点重复此过程，以处理非连通图。

操作说明

图形交互区：

拖拽节点：点击并拖动节点改变其位置（不影响图结构）。

选择节点/边：单击节点或边以选中它们（高亮显示）。再次单击画布空白处取消选择。

添加节点：点击"添加节点"按钮，在弹窗中输入节点标签。

删除节点：先单击选中一个节点，点击"删除选中节点"按钮（会有确认提示）。

添加边：点击"添加边"按钮，在弹窗中选择源/目标节点，设置权重和方向（若适用）。

删除边：先单击选中一条边，点击"删除选中边"按钮（会有确认提示）。

更改布局：使用"布局"下拉菜单选择不同的自动布局算法。

导出：点击"导出 PNG"或"导出 JSON"保存当前图形。

查看信息：鼠标悬停在节点或边上可以查看其ID、标签或权重等信息。

数据结构表示区：

邻接矩阵：直接编辑表格中的数值 (小屏幕设备上隐藏)。

将值设为 0 或空可删除对应边。
将值设为正整数可添加或修改边的权重 (无权图视为1)。
修改会自动更新图形和邻接表。无向图的矩阵会自动保持对称。对角线单元格不可编辑。
**注意:** 请输入有效的非负整数。

邻接表：此区域为 **只读**，实时显示由图形或邻接矩阵更新后的结构。

切换视图：点击"邻接矩阵"或"邻接表"标签切换显示 (若矩阵可见)。

顶部/控件区：

选择图示例：下拉菜单选择不同的预设图示例，观察其结构和表示。

操作说明：点击此按钮显示本帮助窗口。

总结与代码区：

**属性总结**：实时显示当前图形的节点数、边数、连通性、是否含环等属性。环路会被高亮显示。

**代码示例**：点击"查看 C++ 代码示例"按钮，在弹窗中查看相关算法的C++代码片段及中文解释。

代码示例 (C++) - 检测有向图中的环 (DFS)

#include < iostream > // C++ 标准输入输出库 #include < vector > // 使用向量 (动态数组) using namespace std; vector < vector> adj;// 使用邻接表表示图 (graph[u] 存储节点 u 的所有出边指向的节点) vector visited;// 访问状态数组: 0 = 未访问 (白色), 1 = 正在访问 (灰色, 在当前DFS路径上), 2 = 已访问完成 (黑色) int numNodes;// 节点数量 bool hasCycle = false;// 标记是否检测到环 void dfs(int u) // 参数 u: 当前访问的节点 { visited[u] = 1;// 1. 将当前节点标记为"正在访问"(灰色) // 2. 遍历当前节点 u 的所有邻居 v for (int v : adj[u]) { if (visited[v] == 0) { // 3a. 如果邻居 v 未访问过 (白色) dfs(v); // 递归访问邻居 v if (hasCycle) return; // 如果在子调用中发现了环，立即向上返回 } else if (visited[v] == 1) { // 3b. 如果邻居 v 正在访问中 (灰色) // 这意味着我们找到了一个反向边，指向当前 DFS 路径上的一个祖先节点，形成了一个环！ hasCycle = true; // (可选) 在这里可以记录环路路径信息 return; // 找到环，可以结束当前 DFS 分支 } // 3c. 如果 visited[v] == 2 (黑色)，说明邻居 v 已经被完全访问过且不在当前路径上，跳过，继续检查下一个邻居 } // 4. 当前节点 u 的所有邻居都已访问完成，将 u 标记为"已访问完成"(黑色) visited[u] = 2; } // 参数 n: 图中的节点总数,参数 graph: 图的邻接表表示 bool detectCycle(int n, const vector>& graph) { numNodes = n; adj = graph; // 复制图结构 (或使用引用) visited.assign(numNodes, 0); // 初始化所有节点的访问状态为 0 (未访问) hasCycle = false; // 重置环标记 // 遍历图中每一个节点 for (int i = 0; i < numNodes; ++i) { // 如果节点 i 还没有被访问过 (可能是非连通图或新的 DFS 起点) if (visited[i] == 0) { dfs(i); // 从节点 i 开始进行深度优先搜索 if (hasCycle) break; // 如果在任何一个 DFS 分支中找到了环，就可以停止搜索 } } return hasCycle; // 返回最终是否检测到环 } /* int main() { // 假设节点编号从 0 到 n-1 int n = 4; // 节点数量 vector> exampleGraph(n); // 创建邻接表 // 添加边 (示例: 0->1, 1->2, 2->0, 0->3) exampleGraph[0].push_back(1); exampleGraph[1].push_back(2); exampleGraph[2].push_back(0); // 这条边形成了环 0 -> 1 -> 2 -> 0 exampleGraph[0].push_back(3); // 0 到 3 的边 // 调用检测函数 if (detectCycle(n, exampleGraph)) { cout << "图中包含环" << endl; } else { cout << "图中不包含环" << endl; } return 0; } */