标签: graph-theory

在阅读了Stevey Yegge的" Get That Job At Google"文章之后,我发现这个小小的引用很有趣:

每当有人给你一个问题时,请考虑图表.它们是代表任何一种关系的最基本和最灵活的方式,因此任何有趣的设计问题都有一个图表涉及50-50左右.在转向其他解决方案类型之前,请确保您无法想出使用图表解决问题的方法.这个提示很重要!

有哪些问题可以通过图形数据结构/算法得到最好的表示和/或解决？

我能想到的一个例子是:导航单元(ala Garmin,TomTom),它提供从当前位置到另一个位置的道路方向,利用图形和高级路径算法.

还有什么其他的？

我试图找到一个图形数据结构,以便在C#中重用,但没有任何成功.当然,我可以从数据结构书中借鉴,但我希望它更具商业实用性(？)如果您能告诉我实现图表的最佳方法,我将不胜感激.谢谢

假设我以下面的方式连接节点,我如何得出给定点之间存在的路径数量和路径详细信息？

1,2 //node 1 and 2 are connected
2,3
2,5
4,2
5,11
11,12
6,7
5,6
3,6
6,8
8,10
8,9

找到1到7的路径:

答案:找到2条路径,它们是

1,2,3,6,7
1,2,5,6,7

在这里找到的实现很好,我将使用相同的

这是python中上面链接的片段

# a sample graph
graph = {'A': ['B', 'C','E'],
             'B': ['A','C', 'D'],
             'C': ['D'],
             'D': ['C'],
             'E': ['F','D'],
             'F': ['C']}

class MyQUEUE: # just an implementation of a queue

    def __init__(self):
        self.holder = []

    def enqueue(self,val):
        self.holder.append(val)

    def dequeue(self):
        val = None
        try:
            val = self.holder[0]
            if len(self.holder) == 1:
                self.holder = [] …

我读到它是理想的通过邻接列表表示稀疏图形和通过邻接矩阵表示密集图形.但我想了解稀疏图和密集图之间的主要区别.

我想知道是否有人可以推荐一个好的C++树实现,希望有一个stl兼容,如果可能的话.

为了记录,我之前已经多次编写树算法,我知道它可以很有趣,但是如果可能的话,我想要务实和懒惰.因此,实际的工作解决方案链接就是目标.

注意:我正在寻找一个通用树,而不是平衡树或地图/集,在这种情况下,结构本身和树的连接性很重要,而不仅仅是数据.因此,每个分支都需要能够保存任意数量的数据,并且每个分支应该是可单独迭代的.

我有一个无向的正边缘权重图(V,E),我想要一个覆盖顶点V的子集k的最小生成树(Steiner树问题).

我不是将生成树的大小限制为k个顶点; 而且我确切地知道MST中必须包含哪些 k个顶点.

从整个MST开始,我可以削减边缘/节点,直到我得到包含所有k的最小MST .

我可以使用Prim算法来获取整个MST,并开始删除边缘/节点,同时不破坏子集k的MST; 或者我可以使用Floyd-Warshall获得所有对最短路径并以某种方式结合路径.有没有更好的方法来解决这个问题？

我注意到一个反复出现的问题是:"什么是语言X的良好网络图库".我和很多图书馆一起玩过,我可以与你分享我的经历.

Python: NetworkX是一个强大的库,它具有内置的可视化功能,但也有一个使用pyGraphviz的Graphviz接口.(pyGraphviz和NetworkX由同一作者撰写).NetworkX是开源的,非常容易使用.

Perl: 开发Circos可视化基因组和其他高度复杂的数据集.它将始终使用圆形布局,但如果您的网络非常大并且其"模块化"分数较低,则它通常是最合适的布局.Circos是开源的.

.Net: NodeXL由Microsoft Research开发,既是Excel的附加组件,也是.Net 3.5库的附加组件.它非常开放(对于微软的标准)并使用Fruchterman-Reingold算法进行可视化.

Java: JUNG2最近发布,也是一个强大的库.具有扩展的可视化和关键指标支持.JUNG2是开源的.

UbiGraph: UbiGraph具有与不同语言的接口,包括Python(和NetworkX具有UbiGraph支持),Ruby,PHP,Java,C,C++,C#,Haskell和OCaml.它使用XML-RPC服务器对网络图进行非常简洁的三维可视化.基本版本是免费的,您必须支付专业版.

独立: 您可以随时使用的现成的货架包,如:Graphviz的(赢,Linux和OSX),Pajek(胜),UCINET(胜),甚至Visio中(胜).

我相信还有更多的软件包,但这些是我自己使用的软件包.还有哪些其他库或包？

relaxation of an edge在图论的背景下意味着什么？我在研究Dijkstra的单源最短路径算法时遇到了这个问题.

在Magento中,有一个功能,您可以通过指定在运行总计之前和之后来定义总计算的顺序.

我添加了一个自定义总计,如果我将以下行添加到config.xml,则排序错误.错误的意思是:tax_shipping来之前 shipping.这会导致运费的税费增加两倍.

但这违反了这一条件

tax_shipping
after: shipping

我的猜测:整套规则必定存在一些矛盾.但我怎么能找到它呢？

这是我添加的唯一规则.没有这个规则,tax_shipping就会排序shipping.

<shippingprotectiontax>
    <class>n98_shippingprotection/quote_address_total_shippingprotectionTax</class>
    <after>subtotal,discount,shipping,tax</after>
    <before>grand_total</before>
</shippingprotectiontax>

下面我粘贴usort调用返回的已排序数组.Mage_Sales_Model_Quote_Address_Total_Collector::_getSortedCollectorCodes() 对于那些没有安装Magento的人,代码如下:

/**
 * uasort callback function
 *
 * @param   array $a
 * @param   array $b
 * @return  int
 */
protected function _compareTotals($a, $b)
{
    $aCode = $a['_code'];
    $bCode = $b['_code'];
    if (in_array($aCode, $b['after']) || in_array($bCode, $a['before'])) {
        $res = -1;
    } elseif (in_array($bCode, $a['after']) || in_array($aCode, $b['before'])) {
        $res = 1;
    } else { …

我正在研究一个整数序列,它没有相同的数字(不失一般性,让我们假设序列是一个排列1,2,...,n)到它的自然递增顺序(即1,2,...,n).我正在考虑直接交换元素(无论元素的位置如何;换句话说,交换对任何两个元素都有效),交换次数最少(以下可能是一个可行的解决方案):

交换两个元素的约束条件是应将其中一个或两个交换到正确的位置.直到每个元素都放在正确的位置.

但我不知道如何在数学上证明上述解决方案是否是最优的.有人可以帮忙吗？