标签: graph-theory

我在罗莎琳德上遇到了一个问题，我认为我已经正确解决了，但我被告知我的答案不正确。该问题可以在这里找到：http://rosalind.info/problems/grph/

它是基本图论，更具体地说，它涉及返回重叠 DNA 字符串的邻接列表。

“对于一个字符串集合和一个正整数k，字符串的重叠图是一个有向图Ok，其中每个字符串由一个节点表示，当有长度时，字符串s与字符串t通过有向边连接s 的 k 后缀与 t 的长度 k 前缀匹配，只要 s\xe2\x89\xa0t；我们要求 s\xe2\x89\xa0t 来防止重叠图中出现有向循环（尽管可能存在有向循环）。

给定：FASTA 格式的 DNA 字符串集合，总长度最多为 10 kbp。

返回： O3对应的邻接表。您可以按任何顺序返回边。”

所以，如果你有：

\n

Rosalind_0498\n AAATAAA

\n\n

Rosalind_2391\n AAATTTT

\n\n

Rosalind_2323\n TTTTCCC

\n\n

Rosalind_0442\n AAATCCC

\n\n

Rosalind_5013\n GGGTGGG

\n

您必须返回：

罗莎琳德_0498 罗莎琳德_2391

罗莎琳德_0498 罗莎琳德_0442

罗莎琳德_2391 罗莎琳德_2323

解析包含 DNA 字符串的 FASTA 文件后，我的 python 代码如下：

        listTitle = []\n        listContent = []\n\n    #SPLIT is the parsed list of DNA …

问题是 ：

我知道我们应该将图形复制到 G1 和 G2 中，并且可能使用 Dijstra 的算法。我不确定我应该如何以一种方式连接 G1 和 G2，以便为这个问题找到正确的解决方案。

我碰巧在大学的一个图论可视化项目中工作。对于这个项目，我们不能使用任何现有的库来处理图形存储和算法（所以我不能使用 D3 或 python 的 NetworkX 之类的东西）。这个项目更多是关于算法的可视化（BFS、DFS、Dijkstra、Colouring 等），所以我使用 p5js 作为我的可视化辅助工具选择了 JavaScript。

我面临的问题是我试图在顶点之间绘制箭头，但结果并没有达到预期：

编辑 1

将问题更改为符合 mod 的评论。

这是一个sketch.js展示我如何努力使它工作：

var x1; //starting vertex
var x2; //ending vertex
var r = 16; //vertex radius


function setup() {
    createCanvas(640, 480);
    x1 = createVector(random(0, width/2), random(0, height/2)); //random position to the upper left
    x2 = createVector(random(width/2, width), random(height/2, height)); //random position to the lower right
}

function draw() {
    background(200);
    stroke(0);
    var offset = r;
    ellipse(x1.x, x1.y, r, r); //starting vertex
    ellipse(x2.x, …

在 Python 中打印图形的最简单方法是什么？即我想可视化图形的最大集团。

我目前的数据结构是：

adjacency_matrix = [[False, True, False, ...], 
                    [True, False, True, ...],
                    ..]

adjacency_set = [[45, 2], [1, 32], ...]

max_clique = [23, 143, 1, 2, 42, 12, 3, ...] # the vertices in the max clique

我会使用 matplotlib 来做到这一点吗？

我的代码有效，但不适用于所有测试用例。

我在这里尝试做的是创建一个“布尔值 ifparent 数组”，它保存我正在遍历的路径的记录。

“布尔访问数组”记录所有访问过的顶点。

我正在为 DFS 使用堆栈。

//v is no of vertex, adj[] is the adjacency matrix
bool isCyclic(int v, vector<int> adj[])
{
    stack<int> st;
    st.push(0);

    vector<bool> visited(v, false);
    vector<bool> ifparent(v, false);
    int flag= 0;

    int s;
    while(!st.empty()){
        s= st.top();
        ifparent[s]= true;
        visited[s]=true;
        flag=0;

        for(auto i: adj[s]){
            if(visited[i]){
                if(ifparent[i])
                    return true;
            }
            else if(!flag){
                st.push(i);
                flag= 1;
            }
        }

        if(!flag){
            ifparent[s]= false;
            st.pop();
        }
    }

    return false;

}

我正在研究图形，所以我尝试使用 networkx 和 matplotlib 在 Python 中给定字典绘制图形，这是我的代码：

import networkx as nx
import matplotlib.pyplot as plt
G = nx.Graph()
graph = {
    "A":["B","C"],
    "B":["D","E"],
    "C":["E","F"],
    "D":["B","G"],
    "E":["B","C"],
    "F":["C","G"],
    "G":["D","F"]
}
x=10
for vertex, edges in graph.items():
    G.add_node("%s" % vertex)
    x+=2
    for edge in edges:
        G.add_node("%s" % edge)
        G.add_edge("%s" % vertex, "%s" % edge, weight = x)
        print("'%s' it connects with '%s'" % (vertex,edge))
nx.draw(G,with_labels=True)

plt.show()

我已经尝试了函数draw_networkx_edge_labels但似乎我需要一个位置，因为我动态添加了节点，所以我需要一种方法来绘制适合我当前实现的边缘标签。

我的任务是设计一种算法，该算法在 O(V + E) 时间内在具有 V 个节点和 E 条边的加权无向图中找到最短路径。图的权重都是正整数，没有权重大于 15。

我相信我可以使用 Dijkstra 算法来找到从源节点到目标节点的最短路径，但我认为它不满足运行时约束。

了解 BFS 和 DFS 的运行时，我认为对这些算法进行某种修改将使我达到 O(V + E)，但我不确定要朝哪个方向前进或如何利用 < = 15 边缘权重约束。

任何帮助表示赞赏。

从杰夫·埃里克森的讲义上的图形算法，有一个锻炼，以检查是否给定顶点之间的步行路程s，并t可以通过3有向图整除。

我的想法是在图上使用广度优先搜索来获取从s到 的所有路径t。如果简单路径的长度不能被 3 整除，则再次运行该算法以检查循环长度不能被 3 整除的位置s和t位置之间是否存在循环。但是，我觉得该方法非常低效。

如果您对这个问题有任何好的建议，那就太好了。

我已经设法创建了一个随机的无向加权图，用于使用 Dijkstra 算法进行测试，但是我怎样才能做到让每个节点至少有一条边将它们连接到图？

我正在使用 Networkx，我的图形生成器如下：

import networkx as nx
import random

random.seed()
nodes = random.randint(5,10)
seed = random.randint(1,10)
probability = random.random()
G = nx.gnp_random_graph(nodes,probability,seed, False)
for (u, v) in G.edges():
    G.edges[u,v]['weight'] = random.randint(0,10)

这很好地创建了图形，我设法绘制了它，所以我实际上可以看到它，我的问题是边缘创建的概率。我不希望它太高以至于所有节点都具有最大边数，但是设置一个低值可能会导致节点具有 0 个边。有没有办法确保每个节点至少有一条边？

我正在尝试在 Hackerrank 上解决这个问题：

我有这个输入：

........#....#..#..#....#...#..#.#.#.#.#.#..#.....
..#..#..#.#....#..#.....#......#..##...........##.
.........#.###.##...#.....##......###............#
....##........#..#.#.#......#...#.##.......##.....
.................###...#.#...#......#.#.#.#.#...#.
.........#.....#...........##....#.#.#.##.....##..
.....#.##............#....#......#..#..#...##.....
.#.......###....#.#..##.##.#...##...#........#...#
..#.##..##..........#..........##.....##..........
#.#..##......#.#.#..##.###...#.........###..#...#.
.#..#..............#...#........#..#...#....#..#..
##..#..#........#....#........#...#.#......#.....#
#.#.......#.#..#...###..#..#.##...#.##.......#...#
#.#...#...#.....#....#......##.#.#.........#....#.
.#..........#......##..#....#....#.#.#..#..###....
#.#............#.##..#.##.##......###......#..#..#
.#..#.##...#.#......................#........#....
.....#....#.#..........##.#.#................#....
##............#.#......####...#.........#..##..#..
....#..##..##...#.........##..##....#..#.##...#...
.#........#...#..#...........#.###.....##.....##..
.......#..#..##...#..###.....#..##.........#......
...#......#..#...........###...............#......
...##.###.#.#....#...#..#.#.#....#....#.##.#...#..
..........#.......#..#..#...###....##.....#..#....
.............##.##.#.......#.#....#.......#..#..#.
.......#........#.....#....##...#...#.#...#.#.##..
.....#..#..#........#..#.....#...#.##.#....#...#..
....................#.#...#....###...###...##...#.
##.#.....##.....#..#.#.#...........#.#.##...#..#.#
#...........#....#.##...#.#.....#...#.....#.#.....
..#..##...#........#.##..#.....##.......#...#.#.#.
......#....#...##...........#..#.......#.##.......
......#..#..#.###..........#...#...........#..#...
....#.#..#..#.#.#...#.......#...#.##......#.......
....#.......#..#........#...#.#...#......#.......#
.#....##...#.#..#....#.#.##........#..#.#.........
#....#.......#..##......##...............#..#.##..
...#..##.......#.....#....#...#.#......#..##..###.
.....#...#...#...#...#...#..##...#..#.............
....##......#...#..#...#...#.#....#.....#..#.##...
...##.......#..##.....#........#.#....#...#.......
..#...#....#...#.###......#................#......
...#...###...#..##...###.....................#....
.....#....#....#...#.#.#.##....##......#....##....
...#.###...##.........#..........#.##.#.....#.....
##..#...#.........#.......#......##...........####
...###.#..........#.....#####........#..#.#.#...#.
...#..#.....#..##.##.#.....##...#...#.#.....#...##
.##.......#.##....#............#..................
#.....#.........#.#.........#..###....##...##.....
#....#.....#...#.....#.##...##...####........#....
#...........#..#...#........#.##..##..#...#.#.....
..#.#................#......###..##.#.#...##...#..
.#.#....#..#............#....#......#............#
..#..#...#.#.#...#...........#.......##.#...#.#...
#..........#.....#.....#......#.......#.#...##....
.......#...........#...........#....#............#
...####.#.....#.##.....#.......##.#..#......#.....
.#..#.....#..#......#.............#.#.#..##...#...
..#.#.#.........#...#..#.......#................##
.#..##.#.#...#.............#..#..........#..#...#.
....#........#......#...###..#.#..................
#..#..#.....#.#.#...##....##........#........#....
.....#.#.......##.......#.....#........#..##..#...
#.#.##........#..##.#..#.#...#........#.#......#..
....#.#.#.......#.##.##...##...#..#.###...#.#.#...
.....##.#....#........#....#.#........#.#.#.....#.
.....#..##..#.#....#.......#...#.#.###.........#.#
#.....#.##..#.......###.........#..##..#......##..

70 行，maxTime 为 2244

这是我的策略，但它适用于某些测试用例：

import …