精华内容
下载资源
问答
  • 哈密顿路径

    千次阅读 2019-01-10 12:33:50
    这个“哈密瓜路径”网上查了好久没搞明白,我这个的代码无奈定义了4个节点和5条边,将就混过课程设计课。...(2)设计算法判断图G是否存在哈密顿路径,如果存在,输出一条哈密顿路径即可; (3)分析算法...

    这个“哈密瓜路径”网上查了好久没搞明白,我这个的代码无奈定义了4个节点和5条边,将就混过课程设计课。

    放代码和结果从我做起!欢迎大家留言!

    1.  问题描述

    在图G中找出一条包含所有顶点的简单路径,该路径称为哈密顿路径。

    2. 基本要求

    (1)图G是非完全有向图,且图G不一定存在哈密顿路径;

    (2)设计算法判断图G是否存在哈密顿路径,如果存在,输出一条哈密顿路径即可;

    (3)分析算法的时间复杂度。

    3. 问题分析

    哈密顿路径也称作哈密顿链,指在一个图中沿边访问每个顶点恰好一次的路径。寻找这样的一个路径是一个典型的NP-完全(NP-complete)问题。图中有的边可以不经过,但是不会有边被经过两次。与欧拉图的区别:欧拉图讨论的实际上是图上关于边的可行便利问题,而哈密顿图的要求与点有关。

    判定:

    一.Dirac定理(充分条件)

    设一个无向图中有N个顶点,若所有顶点的度数大于等于N/2,则哈密顿回路一定存在(N/2指的是向上取整)。

    二.基本的必要条件

    设图G=<V, E>是哈密顿图,则对于v的任意一个非空子集S,若以|S|表示S中元素的数目,G-S表示G中删除了S中的点以及这些点所关联的边后得到的子图,则W(G-S)<=|S|成立。其中W(G-S)是G-S中联通分支数。

    三.竞赛图(哈密顿通路)

    N(N>=2)阶竞赛图一点存在哈密顿通路。

    4. 概要设计

    在Dirac定理的前提下构造哈密顿回路的过程:

    1)任意找两个相邻的节点S和T,在其基础上扩展出一条尽量长的没有重复结点的路径。即如果S与结点v相邻,而且v不在路径S -> T上,则可以把该路径变成v -> S -> T,然后v成为新的S。从S和T分别向两头扩展,直到无法继续扩展为止,即所有与S或T相邻的节点都在路径S -> T上。

    2)若S与T相邻,则路径S -> T形成了一个回路。

    3) 若S与T不相邻,可以构造出来一个回路.设路径S -> T上有k+2个节点,依次为S, v1, v2, ..., vk, T.可以证明存在节点vi(i属于[1, k]),满足vi与T相邻,且vi+1与S相邻.找到这个节点vi,把原路径变成S -> vi -> T -> vi+1 ,即形成了一个回路。

    4)到此为止,已经构造出来了一个没有重复节点的的回路,如果其长度为N,则哈密顿回路就找到了。如果回路的长度小于N,由于整个图是连通的,所以在该回路上,一定存在一点与回路之外的点相邻。那么从该点处把回路断开,就变回了一条路径,同时还可以将与之相邻的点加入路径。再按照步骤1的方法尽量扩展路径,则一定有新的节点被加进来。接着回到路径2。

    证明:

      根据鸽巢定理,既然与S和T相邻的点都在路径上,它们分布的范围只有v1,v2,---,vk这k个点,k<=N-2,跟据哈密顿回路的第一个判断条件,d(S)+d(T)>=N,那么v1,v2,---,vk这k个点中一定有至少2个点同时与S和T相连,根据鸽巢定理,肯定存在一个与S相邻的点vi和一个与T相邻的点vj,满足j=i+1。

    哈密顿路径的伪代码如下:

    算法:哈密顿路径

    输入:哈密顿回路的起始点s,哈密顿回路中终点s之前的点t

    输出:最终的哈密顿回路ans[ ]

               1.初始化,令s = 1,t为s的任意一个邻接点;

                2.如果ans[]中元素的个数小于n,则从t开始向外扩展,如果有可扩展点v,放入ans[]的尾部,并且t=v,并继续扩展,如无法扩展进入步骤3;

                3.将当前得到的ans[]倒置,s和t互换,从t开始向外扩展,如果有可扩展点v,放入ans[]尾部,并且t=v,并继续扩展。如无法扩展进入步骤4;

                        3.1如果当前s和t相邻,进入步骤5。否则,遍历ans[],寻找点ans[i],使得ans[i]与t相连并且ans[i +1]与s相连,将从ans[i + 1]到t部分的ans[]倒置,t=ans[i +1],进如步骤5;

                        3.2如果当前ans[]中元素的个数等于n,算法结束,ans[]中保存了哈密顿回路(可看情况是否加入点s).否则,如果s与t连通,但是ans[]中的元素的个数小于n,则遍历ans[],寻找点ans[i],使得ans[i]与ans[]外的一点(j)相连,则令s=ans[i - 1],t = j,将ans[]中s到ans[i - 1]部分的ans[]倒置,将ans[]中的ans[i]到t的部分倒置,将点j加入到ans[]的尾部,转步骤2;

     

    时间复杂度:

      如果说每次到步骤5算一轮的话,那么由于每一轮当中至少有一个节点被加入到路径S -> T中,所以总的轮数肯定不超过n轮,所以时间复杂度为O(n^2).空间上由于边数非常多,所以采用邻接矩阵来存储比较适合。

    5. 编程结果

    #include<stdio.h>
    #include<stdlib.h>
    #define Maxsize 10
    #define MAX_NO_LIMIT 10000000
    typedef char Datatype;
    int visited[Maxsize] = { 0 };
    int s[Maxsize] = { 0 };
    int count = 0;
    typedef struct
    {
    	Datatype vertex[Maxsize];
    	int edge[Maxsize][Maxsize];
    	int vertexnum, edgenum;
    
    }graph;
    void creatgraph(graph *G, Datatype a[], int n, int e)
    {
    	int i, j, k;
    	G->vertexnum = n;
    	G->edgenum = e;
    	for (i = 0; i<G->vertexnum; i++)
    	{
    		G->vertex[i] = a[i];
    	}
    	for (i = 0; i<G->vertexnum; i++)
    	{
    		for (j = 0; j<G->vertexnum; j++)
    		{
    			G->edge[i][j] = 0;
    		}
    	}
    	for (k = 0; k<G->edgenum; k++)
    	{
    		printf("输入两个定点");
    		scanf_s("%d%d", &i, &j);
    		G->edge[i][j] = 1;
    		G->edge[j][i] = MAX_NO_LIMIT;
    	}
    
    }
    void DFS(graph *G, int v)          //count是全局变量并已初始化为0
    {
    	int j;
    	visited[v] = 1; //对访问点进行标记
    	s[count++] = v;//S表示路径,这里为开头为v
    	for (j = 0; j <G->vertexnum; j++) {
    		if (G->edge[v][j] == 1 && visited[j] == 0)
    			DFS(G, j); //这里对点进行递归
    	}
    	if (j == G->vertexnum) {   //取消回溯
    		visited[v] = 0;
    		count--;
    	}
    }
    int main()
    {
    	int i;
    	char ch[] = { 'a','b','c','d' };
    	graph MG;
    	creatgraph(&MG, ch, 4, 5);
    	DFS(&MG, 0);
    	for (i = 0; i<4; i++)
    	{
    		printf("%d",s[i]);
    	}
    	system("pause");
    	return 0;
    }

     

    展开全文
  • 导入eclipse就可以使用,用两种方式实现了寻找哈密顿路径
  • (2)设计算法判断图G是否存在哈密顿路径,如果存在,输出一天哈密顿路径即可; (3)分析算法的时间复杂度。 3、设计思想 寻找哈密顿路径的过程是一个深度优先遍历的过程。在遍历过程中,如果有回溯,说明遍历...

    不要自卑,去提升实力
    互联网行业谁技术牛谁是爹
    如果文章可以带给你能量,那是最好的事!请相信自己
    加油o~

    1、问题描述

    在图G中找出一条包含所有顶点的简单路径,该路径称为哈密顿路径

    2、基本要求

    (1)图G是非完全有向图,且图G不一定存在哈密顿路径;
    (2)设计算法判断图G是否存在哈密顿路径,如果存在,输出一天哈密顿路径即可;
    (3)分析算法的时间复杂度。

    3、设计思想

    寻找哈密顿路径的过程是一个深度优先遍历的过程。在遍历过程中,如果有回溯,说明遍历经过的路线中存在重复访问的节点,所以,可以修改深度优先遍历算法,使其在遍历过程中取消回溯。

    以下代码仅供参考
    以下代码仅供参考
    以下代码仅供参考

    /**
     *作者:魏宝航
     *2020年11月22日,下午21:47
     */
    import java.io.IOException;
    import java.util.Scanner;
    
    public class MatrixUDG {
    
        private char[] mVexs;       
        private int[][] mMatrix;   
        private int num;
        private int edge;
        private boolean[] visit;
        private int[] road;
        private static int count=0;
        private int m=0;
    
        public MatrixUDG(char[] vexs, char[][] edges) {
    
            num = vexs.length;
            edge = edges.length;
    
            visit=new boolean[num+10];
            road=new int[num+10];
    
            mVexs = new char[num];
            for (int i = 0; i < mVexs.length; i++)
                mVexs[i] = vexs[i];
    
            mMatrix = new int[num][num];
            for(int i=0;i<edge;i++){
                for(int j=0;j<edge;j++){
                    if(edges[i][j]=='∞'){
                        mMatrix[i][j]=Integer.MAX_VALUE;
                    }
                    else{
                        mMatrix[i][j]=1;
                    }
                }
            }
        }
    
        public void print() {
            System.out.printf("Martix Graph:\n");
            for (int i = 0; i < mVexs.length; i++) {
                for (int j = 0; j < mVexs.length; j++){
                    if(mMatrix[i][j]<Integer.MAX_VALUE){
                        System.out.printf("%d ", mMatrix[i][j]);
                    }else{
                        System.out.print("∞ ");
                    }
                }
    
                System.out.printf("\n");
            }
        }
    
        public void DFS(int v){
            visit[v]=true;
            road[count++]=v;
            for(m=0;m<num;m++){
                if(mMatrix[v][m]==1&&visit[m]==false){
                    DFS(m);
                }
            }
            if(m==num){
                visit[v]=false;
                count--;
            }
        }
        
        public void Hamilton(){
            for(int i=0;i<num;i++){
                DFS(i);
            }
            System.out.print(road[0]+1);
            for(int i=1;i<num;i++){
                System.out.print("->"+(road[i]+1));
            }
        }
        
        public static void main(String[] args) {
    
            char[] vexs2={'1','2','3','4'};
            char[][] edges2=new char[][]{
                    {'∞','1','1','∞'},
                    {'∞','∞','∞','∞'},
                    {'∞','1','∞','1'},
                    {'∞','1','∞','∞'},
            };
            
            MatrixUDG g=new MatrixUDG(vexs2,edges2);
            g.print();
            g.Hamilton();
        }
    }
    
    展开全文
  • 哈密顿路径Problem Statement: 问题陈述: Given a graph G. you have to find out that that graph is Hamiltonian or not. 给定图G。 您必须找出该图是否为哈密顿量 。 Example: 例: Input: 输入: ...

    哈密顿路径

    Problem Statement:

    问题陈述:

    Given a graph G. you have to find out that that graph is Hamiltonian or not.

    给定图G。 您必须找出该图是否为哈密顿量

    Example:

    例:

    Input:

    输入:

    hamiltonian path

    Output: 1

    输出1

    Because here is a path 0 → 1 → 5 → 3 → 2 → 0 and 0 → 2 → 3 → 5 → 1 → 0

    因为这里是路径0→1→5→3→2→0和0→2→3→5→1→0

    Algorithm:

    算法:

    To solve this problem we follow this approach:

    为了解决这个问题,我们采用以下方法:

    1. We take the source vertex and go for its adjacent not visited vertices.

      我们获取源顶点,并寻找其相邻的未访问顶点。

    2. Whenever we find a new vertex we make it source vertex and we repeat step 1.

      每当我们找到一个新顶点时,就将其设为源顶点,然后重复步骤1。

    3. When a vertex count is equal to the vertex number then we check that from vertex is there any path to the source vertex. If there is exist a path to the source vertex then we will mark it and if not then make that vertex as unmarked and continue the process.

      当顶点数等于顶点数时,我们检查从顶点开始是否存在到源顶点的任何路径。 如果存在到源顶点的路径,那么我们将对其进行标记,如果没有,则将该顶点设为未标记并继续该过程。

    4. If there is no such path then we say NO.

      如果没有这样的路径,那么我们说不。

    检查图是否为哈密顿的C ++实现 (C++ Implementation to check a graph is Hamiltonian or not )

    #include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    
    void addedge(list<int>* g, int u, int v)
    {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    int hamiltonian(list<int>* g, int v, int s, int& count, bool* vis, int& h)
    {
        if (count > 1 && s == 0) {
            h = 1;
            return 1;
        }
        list<int>::iterator it;
        for (it = g[s].begin(); it != g[s].end(); it++) {
            if (!vis[*it]) {
                vis[*it] = true;
                count++;
                if (count == v) {
                    vis[0] = false;
                }
                hamiltonian(g, v, *it, count, vis, h);
                vis[0] = true;
                vis[*it] = false;
                count--;
            }
        }
        return 0;
    }
    
    int main()
    {
        int num;
        cin >> num;
        for (int i = 0; i < num; i++) {
            int v, e;
            cin >> v >> e;
            list<int> g[v];
            int x, y;
            for (int j = 0; j < e; j++) {
                cin >> x >> y;
                addedge(g, x, y);
            }
            bool vis[v];
            memset(vis, false, sizeof(vis));
            int count = 1;
            vis[0] = true;
            int h = 0;
            hamiltonian(g, v, 0, count, vis, h);
            cout << h << endl;
        }
        return 0;
    }
    
    

    Output

    输出量

    1
    5
    8
    0 1
    0 2
    1 2
    1 3
    1 4
    3 4
    3 2
    2 4
    1
    
    
    

    翻译自: https://www.includehelp.com/icp/check-a-graph-is-hamiltonian-or-not-hamiltonian-path.aspx

    哈密顿路径

    展开全文
  • 四面体网格上哈密顿路径和循环的存在性与构造
  • 哈密顿路径问题 【哈密顿路径问题】 哈密顿路径问题是哈密顿圈问题的变种。如果有向图G中的路径P恰好包含每一个顶点一次,则称为是一条哈密顿路径哈密顿路径问题是NP完全的 证明哈密顿路径是NP完全,可以通过3-...

    哈密顿路径问题
    【哈密顿路径问题】
    哈密顿路径问题是哈密顿圈问题的变种。如果有向图G中的路径P恰好包含每一个顶点一次,则称为是一条哈密顿路径。

    哈密顿路径问题是NP完全的
    证明哈密顿路径是NP完全,可以通过3-SAT归约到哈密顿路径。这与3-SAT归约到哈密顿问题是很相似的(只是没有t到s的边)。

    3-SAT归约到哈密顿问题:https://blog.csdn.net/Valieli/article/details/104360907

    展开全文
  • 这个 MATLAB 函数 c% 让我们创建下图(1)--(2)--(3)--(4) | / \ | | | / \ | | | / \ | | (5)------(6) | | | | | | | (7)-------------------(8) g=[0...#注意:此代码也可用于查找哈密顿循环。 为了确保源和目标相同。
  • 哈密顿路径 状压DP

    2020-10-06 22:40:17
    对于某类问题, 求解经过所有点的最短路径(哈密顿路径)或者求经过所有点最短路径后再回到开始的地方(哈密顿回路)例如旅行商问题(TSP)。 首先我们假设 每个点与点之间的权值(路的长度)已经求出 记为 w[i][j]. ...
  • 汉密尔顿路径(哈密顿路径)解析

    千次阅读 2017-04-26 22:45:49
    转自:汉密尔顿路径(哈密顿路径)解析 汉密尔顿路径(哈密顿路径哈密顿路径也称作哈密顿链,指在一个图中沿边访问每个顶点恰好一次的路径。寻找这样的一个路径是一个典型的NP-完全(NP-complete)问题。后来人们...
  • 链接传送门 状压dp 我对状态压缩的理解:把当前的情况,转化为一个二进制数(或许有其他形式?暂时还没见到),用二进制的0和1来代表当前的情况 AC代码 #include <bits/stdc++.h> using namespace std;...
  • 这个包提供了基于哈密顿路径的动态双向增量序列的实现。 它采用 libsvm 格式提供的稀疏术语文档矩阵,并计算术语空间的序列。 有几个距离函数可用。 用法 给定一个稀疏 libsvm 格式的输入矩阵,DynamicBiseriation ...
  • 问题 在有向无环图DAG(Directed acyclic graph)中,哈密顿路径问题(Hamiltonian-path)可以在多项式时间内解决。请给出具体算法。 算法思路 算法: 对有向无环图进行拓扑排序(topological sort) 验证排序结果 如果...
  • 竞赛图与哈密顿路径的定义. 竞赛图:竞赛图是一张有向无环图G={V,E}G=\{V,E\}G={V,E},满足有∣E∣=∣V∣(∣V∣−1)|E|=|V|(|V|-1)∣E∣=∣V∣(∣V∣−1)边且两点之间仅有一条边,也就是说两点之间有且仅有一条边. ...
  • 如果图GGG中的一个路径包括每个边恰好一次,则该路径称为欧拉路径(Euler path)\text{(Euler path)}(Euler path)。 如果一个回路是欧拉路径,则称为欧拉回路(Euler circuit)\text{(Euler circuit)}...
  • 竞赛图构造哈密顿路径
  • 哈密顿路径 && 竞赛图

    千次阅读 2018-05-26 11:13:07
    哈密顿图就是从一点出发,经过所有的必须且只能一次,最终回到起点的路径.  图中有边可以不经过,但不会有边被经过两次. 竞赛图(哈密顿通路):有向完全图 任意两个不同的点之间恰有一条连边  N(N&amp;gt;=2)...
  • 汉密尔顿式 该项目试图说明如何使用 WebGL 和three.js... Solvable意味着该图确实有一些哈密顿路径,解决方案将打印在左侧。 每次刷新页面时都会生成一个新图表,最多 10 个节点。 有些可以解决,有些则不能。 享受!
  • 题意:给一副n个点的无向图(完全图),求从点0到n-1的最短哈密顿路径 思路:状压DP入门题,这题的子问题其实是每个点的使用状况,这种集合类的DP一般都是状压DP,所以我们用dp[i][j]表示当前在第i个点的时候,所有...
  • 提出了一种基于有穷自动机的解决哈密顿路径问题的DNA算法,将有穷自动机的状态用含有DNA限制性内切酶的识别位点的DNA双链分子来编码,通过限制性内切酶的生物化学反应来实现状态的转移。算法的创新之处在于用DNA计算...
  • 但我还是纠结于哈密顿路径的求法,也许这不是标准的竞赛图,但是和Dirac定理求哈密顿回路思想类似,这里是从一个节点开始不断往后判断节点在哪两个节点之间,但是对于插入头部和尾部那里还不是很懂,以后专攻图论时...
  • 保存模版 #include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std;......
  • 哈密顿路径+状压dp

    2019-08-14 17:41:12
    下一个m行,每一行都有两个整数a,b(0,b)表示路径必须首先访问城市。 输入端带有EOF。 输出量 对于每个测试用例,输出Hamilton路径的最小长度。 如果找不到路径,则输出-1。 样本输入 3 0 -1 2 4 -1 ...
  • 1.竞赛图存在哈密顿路径 2.竞赛图存在哈密顿回路,当且仅当它是强联通的 所以我们将图缩点后,拓扑排序后一定是一条链,且之前的块内的点和之后块内的点的边一定全都由前面指向后面 而每个块都是强联通的,所以我们...
  • 题目大意:给定一个 N 个点的无向图,点有点权,求从 0 号点走到 N-1 号点的最短哈密顿路径是多少。 题解:由于哈密顿路径的定义是每个顶点必须经过且仅能经过一次,因此,可用当前是否经过了这些点和当前在哪个点来...
  • 题目分析:最短哈密顿路径的模板题,比赛的时候为什么没看出来呢。。好像是被 n * m 很小所迷惑了,感觉像是一道搜索题,但想了半天没什么思路就不想做了,赛后回顾一下的时候发现,k 给的特别小,最大只有 11 ,而....
  • 哈密顿路径会计算到,能够不做处理,最后减去边的条数就可以,每一个环会算两遍,最后要除以2. 代码: #include #include #include #include #include #include #include #include #include #...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,119
精华内容 1,247
关键字:

哈密顿路径