精华内容
下载资源
问答
  • 有向图的路径发现,从一个顶点出发,找到以该顶点为起始点的所有路径

    有向图中以一个顶点为起始点的所有路径,有向图中所有路径存储

    适用于:有向图中设定从一个顶点出发,存储该顶点的所有路径,对于有向有环图同样适用(程序中记录了经过的节点,可以避免有环图的特例)。 适用于:有向图中,从一个顶点出发,存储所有以该顶点为起始点的路径。

    网上找到一些相关的,但是大都是值给出两点间所有路径,没有想要的功能。


    有向图的路径发现

    适用于:有向图中设定从一个顶点出发,存储该顶点的所有路径,对于有向有环图同样适用(程序中记录了经过的节点,可以避免有环图的特例)。 适用于:有向图中,从一个顶点出发,存储所有以该顶点为起始点的路径。

    图: 1->2 ,1->3, 1->4, 1->8 ,2->3 ,4->5 ,5->6 ,5->7 ,8->7 ,6->1 ,7->1 设定的顶点1,得到以下结果。 [1, 2] [1, 3] [1, 4, 5, 6] [1, 8, 7]



    主方法类:

    package cn.com.hadoop.dfsPath;
    
    import java.io.BufferedReader;
    import java.io.DataInputStream;
    import java.io.File;
    import java.io.FileInputStream;
    import java.io.FileNotFoundException;
    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.Iterator;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Set;
    import java.util.Map.Entry;
    
    import cn.com.hadoop.bean.Node;
    
    public class oneTest {
    
    	static HashMap<Integer, Node> nodes = new HashMap<Integer, Node>();
    	static Set<Integer> visited = new HashSet<Integer>();
    	static int count = 1;
    	static ArrayList<Queue<Integer>> paths = new ArrayList<Queue<Integer>>();
    	public static double relationDiscover() {
    
    		return 0;
    	}
    
    	public static void main(String[] args) throws FileNotFoundException {
    		readLittleDirectGraph();//给nodes添加小有向图
    		
    		Queue<Integer> tmpQ = new LinkedList<Integer>();
    		//1.测试一个节点
    		paths.add(tmpQ);
    		tmpQ.add(7);
    		visited.add(7);
    		queuePaths(tmpQ);
    		if(true)return;
    		
    		//2.遍历所有节点
    		Iterator<Entry<Integer, Node>> iterator=  (Iterator<Entry<Integer, Node>>)nodes.entrySet().iterator();
    		while(iterator.hasNext()){
    			Entry<Integer, Node> entry = iterator.next();
    			int key = entry.getKey();
    			Node node = entry.getValue();
    			//给定ID,求出以该点为顶点的所有路径
    			paths.add(tmpQ);
    			
    			tmpQ.add(key);
    			visited.add(key);
    
    			queuePaths(tmpQ);
    			//清除本次ID的所得路径
    			paths.clear();
    			visited.clear();
    			tmpQ.clear();
    		}
    	}
    
    	/**
    	 * 将图数据放入hashmap中<ID,Node>
    	 */
    	public static void readDirectGraph() {
    
    		File file1 = new File("initColorCite.txt");
    		File file2 = new File("newCite.txt");
    		FileInputStream fis;
    		DataInputStream in;
    		BufferedReader br;
    
    		try {
    			fis = new FileInputStream(file1);
    			in = new DataInputStream(fis);
    			br = new BufferedReader(new InputStreamReader(in));
    
    			String strLine;
    			while ((strLine = br.readLine()) != null) {// 此次循环,将所有node节点初始化ID及其color.
    				String[] parts = strLine.split(" ");
    
    				Node node = new Node(Integer.parseInt(parts[0]),
    						Integer.parseInt(parts[1]));
    				nodes.put(Integer.parseInt(parts[0]), node);
    			}
    		} catch (Exception e) {
    			e.printStackTrace();
    		}
    
    		try {
    			fis = new FileInputStream(file2);
    			in = new DataInputStream(fis);
    			br = new BufferedReader(new InputStreamReader(in));
    
    			String strLine;
    			ArrayList<Integer> neighbours = new ArrayList<Integer>();
    			while ((strLine = br.readLine()) != null) {
    				neighbours.clear();
    
    				String[] parts = strLine.split("\t");
    				Node node = nodes.get(Integer.parseInt(parts[0]));
    				for (int i = 1; i < parts.length; i++) {
    					if (parts[i].equals(""))
    						continue;
    					neighbours.add(Integer.parseInt(parts[i]));
    				}
    				node.setNeighbours(neighbours);
    			}
    		} catch (Exception e) {
    			e.printStackTrace();
    		}
    		System.out.println("图!");
    
    	}
    	
    	/**
    	 * 将自定义的小图放入hashmap中<ID,Node>
    	 */
    	public static void readLittleDirectGraph(){
    		ArrayList<Integer> neighborT = new ArrayList<Integer>();
    		
    		Node node1 = new Node(1, 1);
    		neighborT.add(2);
    		neighborT.add(3);
    		neighborT.add(4);
    		neighborT.add(8);
    		node1.setNeighbours(neighborT);
    		
    		Node node2 = new Node(2, 1);
    		neighborT.clear();
    		neighborT.add(3);
    		node2.setNeighbours(neighborT);
    		
    		Node node3 = new Node(3, 1);
    		Node node4 = new Node(4, 1);
    		neighborT.clear();
    		neighborT.add(5);
    		node4.setNeighbours(neighborT);
    		
    		Node node5 = new Node(5, 1);
    		neighborT.clear();
    		neighborT.add(6);
    		neighborT.add(7);
    		node5.setNeighbours(neighborT);
    		
    		Node node6 = new Node(6, 1);
    		neighborT.clear();
    		neighborT.add(1);
    		node6.setNeighbours(neighborT);
    		
    		Node node7 = new Node(7, 1);
    		neighborT.clear();
    		neighborT.add(8);
    		node7.setNeighbours(neighborT);
    		
    		Node node8 = new Node(8, 1);
    		neighborT.clear();
    		neighborT.add(7);
    		node8.setNeighbours(neighborT);
    		
    		nodes.put(1, node1);
    		nodes.put(2, node2);
    		nodes.put(3, node3);
    		nodes.put(4, node4);
    		nodes.put(5, node5);
    		nodes.put(6, node6);
    		nodes.put(7, node7);
    		nodes.put(8, node8);
    	}
    	
    	/**
    	 * 正确
    	 * 2017.7.6
    	 * 传入的是同一层的所有ID,如第一层只有1,第二层为2,3,4,8,第三层为第二层所有ID的neighbors且这些与前几层不重复。
    	 * @param paraQueue
    	 */
    	public static void queuePaths(Queue<Integer> paraQueue ){
    		System.out.println(" ~~~~~~~~~~~~~~~~~~~~~~~~   ");
    			Queue<Integer> baseQueue = new LinkedList<Integer>(paraQueue);//上一级的路径,不添加本次路径。
    			
    			Queue<Integer> neighborQueue = new LinkedList<Integer>();
    			Queue<Integer> existNeighborQueue = new LinkedList<Integer>();
    			System.out.println("visit   " + visited);
    			System.out.println("basen   " + baseQueue);
    			//遍历队列。将第二层中的ID也加入visited
    			Queue<Integer> curQueue = null;
    			for (Iterator<Integer> iterator = baseQueue.iterator(); iterator.hasNext();) {
    				int i = iterator.next();
    				//从paths集合中找到包含i的队列
    				for(Queue<Integer> q : paths){
    					if(q.contains(i)){
    						curQueue = q;
    						break;
    					}
    				}
    				
    				int c = 0;
    				ArrayList<Integer> neighbors = nodes.get(i).getNeighbours();
    				Queue<Integer> curTmpQueue = new LinkedList<Integer>(curQueue);
    				for(int i1 : neighbors){
    					if (visited.contains(i1))
    						continue;
    					c++;
    					if(c>1){
    						visited.add(i1);
    						existNeighborQueue.add(i1);
    						Queue<Integer> newQueue = new LinkedList<Integer>(curTmpQueue);
    						newQueue.add(i1);
    						paths.add(newQueue);
    					}else{
    						visited.add(i1);
    						existNeighborQueue.add(i1);
    						curQueue.add(i1);
    					}
    				}
    			}
    			System.out.println("visit   " + visited);
    			System.out.println("exist   " + existNeighborQueue);
    			//遍历paths
    			for (Iterator<Queue<Integer>> iterator = paths.iterator(); iterator.hasNext();) {
    				Queue<Integer> q = iterator.next();
    				System.out.println(q);
    			}
    			if (existNeighborQueue.isEmpty()) { //遍历结束,跳出,否则为死循环。
    				System.out.println("—————————结束——————————");
    				return;
    			}
    			queuePaths(existNeighborQueue);
    		}
    }
    


    Node类:

    package cn.com.hadoop.bean;
    
    import java.util.ArrayList;
    
    public class Node {
    	
    	private int id;
    	private int color;
    	private int initColor;
    	private boolean isVisited = false;
    	private ArrayList<Integer> neighbours;
    	public Node(int id) {
    		this.id = id;
    	}
    	public Node(int id, int initColor) {
    		this.id = id;
    		this.color = initColor;
    		this.initColor = initColor;
    		this.neighbours = new ArrayList<Integer>();
    	}
    	public int getId() {
    		return id;
    	}
    	public void setId(int id) {
    		this.id = id;
    	}
    	public int getColor() {
    		return color;
    	}
    	public void setColor(int color) {
    		this.color = color;
    	}
    	public int getInitColor() {
    		return initColor;
    	}
    	
    	public ArrayList<Integer> getNeighbours() {
    		return neighbours;
    	}
    	public void setNeighbours(ArrayList<Integer> neighbours) {
    		for(int id : neighbours)
    			this.neighbours.add(id);
    	}
    	public boolean getIsVisited() {
    		return isVisited;
    	}
    	public void setIsVisited(boolean isVisited) {
    		this.isVisited = isVisited;
    	}
    	
    }
    


     

    文中使用了广度遍历,在此基础上加入了路径添加(即paths.add(newQueue)),剔除重复点加入避免了重复路径(即visited的功能)。

    展开全文
  • 有向图和无向图以及拓扑的复习

    万次阅读 2018-10-14 17:43:36
    1)关于有向图,百科中是这样描述的:一个有向图D是指一个有序三元组(V(D),A(D),ψD),其中ψD为关联函数,它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或)对。 理解:如图D,...

    备注:大一学了图后,一段时间没用就还给老师了,如今重新复习一下,理解有误的地方请指教。


    有向图和无向图的定义

    1)关于有向图,百科中是这样描述的:一个有向图D是指一个有序三元组(V(D),A(D),ψD),其中ψD为关联函数,它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或点)对。
    理解:如图D,如果e是D的一条边,而这时候存在这样的一个关系,ψD,有A,B两点,使得,ψD(A,B)=e(到底是怎样的关系?我觉得在应用中,需要我们自己制定,就像在预算100元的条件下,你选择怎样的交通工具快速到达目的地),通俗理解:边有方向的图。即AB != BA。
    [外链图片转存失败(img-OHZsll7R-1567908307459)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539483515239_C07BA5588B40E754EB534225BA630A0D “图片标题”)]


    (2)平行边:在图中,如果起点和终点相同则称为平行边,平行边的条数则称为重数。如图:e2和e3为平行边,B和C之间的重数为2。
    [外链图片转存失败(img-EMKaEUe6-1567908307460)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539483671400_6DA66AE52EFE0CF2370DF02226877263 “图片标题”)]


    (3)关于无向图:了解了有向图,那它就好理解了,就是有向图中去掉所有的方向,AB=BA,如图,就是去掉D中的所有箭头(此时,又称为基础图,反之给无向图添上箭头的有向图又称为定向图)。
    [外链图片转存失败(img-DJM75Udh-1567908307461)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539483731056_5FB56EBF13116F56F22CCFD0F068F03B “图片标题”)]


    (4)出度和入度:如图D,以点A为例子,在所有与A关联的边中,以A为起点的边的条数称为出度。而入度则刚好相反,以A为终点的边的条数则称为入读。其中,入度+出度,我们称为A的度。注意特殊情况:如图:A有一个自环,起点和终点都是自己,此时出度算一度,入度也算一度。如图:A的出度为3,入度也为2,A的度的5。


    (5)邻接矩阵和关联矩阵定义:设D(V,E)是有向图,其中V={v1,v2,v2…vn},E={e1,e2,e3,…em}称A(D)=(aij)nxn是D的领接矩阵,其中aij是以vi为起始点,以vj为终点的边的条数。若图D中无环,则称M(D)=(mij)nxm为关联矩阵。[i,j是下标,n是点的个数,m是边的数量注意:1.关联矩阵是针对边来说的,所以矩阵大小为n*m,它的取值如下:

    图片来源于百科
    例子:
    图片来源于百科
    (6)补充:对于无向图而言:邻接矩阵则是对称的,且只有0和1,因为没有方向的区别后,要么有边,要么没边:
    在这里插入图片描述
    从图我们可以看到,它是关于对角线对称的一个矩阵,我们在编程中,遍历和存储是只需要关注上半部分或者下半部分即可。
    在这里插入图片描述


    (7)跟邻接矩阵一样,用来存储图中信息的,还有邻接表:如果学过链表了,就很好理解了,首先在一个数组中存储各个点(对象或者成为链),而每个对象又保存着一个next引用指向连接的点在数组中的坐标,如图:A到E在数组中存储后,坐标依次排列,A连B,B的坐标为1,所以指向的地方标记为1,代表A连着B,接着,B连着E,E的坐标为4,这1的引用指向4。

    从图我们就可以得出邻接表的存储方式了:即链表加数组,这存储结构比起纯粹用数组(邻接矩阵)要节约很多空间。邻接矩阵,我们需要一个n*n维的数组,复杂度为O(n^2),而邻接表是根据点和边来保存数据的,当一个起点决定后,就采用深度搜索的方法沿着边,保存连接点的信息,复杂度为O(n+m)

    另外,若果是有向图,我们在保存下一个顶点时,还需要保存边的权值,看图中每个格子都分成两小格了吗,第二个小格子就是用来存储权值的。

    图来自百度词条,好难画
    在这里插入图片描述


    拓扑排序

    百度词条这样描述:对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。
    理解:(1)根据定义,我们可以知道它是针对有向图而言的.(2)它是一个包含有向图的所有点的线性序列,且满足两个条件:a.有向图的每个顶点只出现一次。b.若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 应该出现在顶点 B 的前面。

    备注:图来源于百度,之前都没发现,它的786,应该是678,C0是连着C2和C6的
    [外链图片转存失败(img-q5yfBWrf-1567908307464)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539485618410_F203E6F40B767104E9635E84C103CA7C “图片来源于百科”)]

    (2)注意,拓扑排序并不是唯一的,它的排序方式:以上图为例子:a.首先我们从有向图图中选择一个没有前驱(即入度为0)的顶点并输出,这里我们可以选择c0或者c1。b.从图中删除输出的顶点和所有以它为起点的有向边。c.循环 a步骤 和 b步骤,终止条件为当前的有向图为空或当前图中不存在无前驱的顶点为止。备注:若当前图中不存在无前驱的顶点,说明有向图中必然存在环。


    展开全文
  • 图论算法——dfs求有向图和无向图两间所有路径

    千次阅读 多人点赞 2019-06-12 09:28:24
    DFS大法好! DFS作为搜索算法,最常...我在这里就介绍一下dfs求两的的所有路径,这个算法最开始在数据结构大作业里面用到了,当时费了一番劲写出来后,就想oj题里面这么变态的算法肯定不会出,后来还真的见过了。。。

    DFS大法好!
    DFS作为搜索算法,最常用于图,对图的遍历,探寻路径,甚至是求一些情况下的最短路。我在这里就介绍一下dfs求两点的的所有路径,这个算法最开始在数据结构大作业里面用到了,当时费了一番劲写出来后,就想oj题里面这么变态的算法肯定不会出,后来还真的见过了。。。
    哈密顿绕行世界问题 HDU - 2181

    就以这张图为介绍,v1是出发点,v3是终点:
    v1到v3

    1. v1开始出发,v1被标记访问过,并入栈,到v2,标记并入栈;
    2. 到v3,此时v3是终点,到达函数开始的判断条件,输入堆栈经过的路径。一条路找到(1,2,3)。此时虽然v3可以到v5,但也没有必要探寻下去:算法的角度来说如果继续探寻下去v3就会被标记,就算有路可以到,下次就不会背进入递归了;实际应用来说也没必要绕一圈再到一个地方。这算是一个剪枝吧。
    3. v3回溯到v2,v2没有可走的路了,堆栈中的v2出栈,v2并取消标记;
    4. v2回溯到v1,有v4可走,入栈并标记。探寻v2可走,入栈并标记。v2到v3,另一条路找到(1,4,2,3);
    5. 从v3回溯到v4,探寻到v5可走,入栈并标记;
    6. v5没路可走了,回溯到v4到v1,程序结束。

    输入样例

    5 6
    
    1 2
    2 3
    3 5
    1 4
    4 2
    4 5
    
    1 3
    

    输出样例

    1 2 3
    1 4 2 3
    
    #include<stdio.h>
    #include<math.h>
    int map[100][100]={0};///map[i][j]为0表示i, j两点之间不通,为1表示有一条路
    int stack[120],v[100]={0},top=0,m,n,start,end;
    void dfs(int pos)//从pos点开始访问
    {
    	int i;
    	if(pos==end){//到达终点
    		for(i=0;i<top;i++)
    			printf("%d ",stack[i]);
    		printf("%d\n",end);	
    		return;
    	}
    	v[pos]=1;//标记被访问过 
    	stack[top++]=pos;//经过的路径加入队列
    	for(i=1;i<=n;i++){
    		if(!v[i]&&map[pos][i])//如果这个点没有被访问过,而且b与这个点相连,就继续搜索
    			dfs(i);
    	}
    	v[pos]=0;//删除标记 
    	top--;//队列里删除b
    }
    
    int main()
    {
        int i,x,y;
        printf("分别输入顶点数n和路径数m:"); 
        scanf("%d %d",&n,&m);//n是顶点数,m是边数 
        
        printf("输入m条路径:"); 
        for(i=1; i<=m; i++) {
            scanf("%d %d", &x,&y);
            map[x][y] = 1;//这两点之间有路径
    		//map[y][x] = 1; //无向图加上这一句即可 
        }
        
        printf("输入起始点和终点:");
        scanf("%d %d", &start,&end);
        
        printf("\n程序执行结果为:\n"); 
        dfs(start);
        return 0;
        
    }
    

    想要知道每条路径的长度也很容易,输入信息的时候加上路径长度,函数多一个参数,每次递归的时候加上这两点路径的长度,到达终点输出就行了,求最短路的话每次到终点比较一下就好了。这里我就不再多写了。
    以下为原话。。。。
    用数组代替堆栈了,c写堆栈不方便。数据结构大作业要用到这个算法,昨天整整一下午还有晚自习都在找这个算法,今天才发现昨天一直多输出一个东西,那是测试用的,开始写的没删掉,就一直以为错了。今天才努(tao)力(ke)写出来了,2333。
    附上我的大作业:校园导航系统

    展开全文
  • JAVA代码详解: 有向图中判断欧拉路径欧拉回路 欧拉路径是图中访问每一条边一次的路径。 欧拉回路是在同一顶点上开始结束的欧拉路径。 有欧拉回路的图称为欧拉图。 上一篇博客讨论了无向图的欧拉回路。接...

    JAVA代码详解: 有向图中判断欧拉路径和欧拉回路

    欧拉路径是图中访问每一条边一次的路径。

    欧拉回路是在同一顶点上开始和结束的欧拉路径。

    有欧拉回路的图称为欧拉图。

    上一篇博客讨论了无向图的欧拉回路。接下来这一篇博客讨论有向图中判断欧拉路径和欧拉回路问题。

    例如,下图的欧拉循环为1、0、3、4、0、2、1


    如何检查有向图是否是欧拉图?

    如果以下条件为真(成立),则有向图具有欧拉回路

    1)所有非零度顶点都属于单个强连通分量。

    2)每个顶点的进出度相同。

    在计算机科学中,Kosaraju的算法(也称为Kosaraju-Sharir算法)是线性时间的算法来找到一个有向图的强连通分量。

    为了比较进度和出度,我们需要存储每个顶点的进度和出度。通过邻接表的大小,可以得到输出度。通过创建一个大小等于顶点数的数组,可以存储度数。

    package com.bean.algorithm.basic;
    
    import java.util.Iterator;
    import java.util.LinkedList;
    
    public class EulerCircuit6 {
    
    	private int V; // 顶点数量
    	private LinkedList<Integer> adj[];// 邻接表
    	private int in[]; // 维护入度
    
    	EulerCircuit6(int v) {
    		V = v;
    		adj = new LinkedList[v];
    		in = new int[V];
    		for (int i = 0; i < v; ++i) {
    			adj[i] = new LinkedList();
    			in[i] = 0;
    		}
    	}
    
    	void addEdge(int v, int w) {
    		adj[v].add(w);
    		in[w]++;
    	}
    
    	void DFSUtil(int v, Boolean visited[]) {
    		// 将当前节点标记为已访问
    		visited[v] = true;
    
    		int n;
    
    		// 对与此顶点相邻的所有顶点遍历
    		Iterator<Integer> i = adj[v].iterator();
    		while (i.hasNext()) {
    			n = i.next();
    			if (!visited[n])
    				DFSUtil(n, visited);
    		}
    	}
    
    	// 返回此图的反转(或转置)
    	EulerCircuit6 getTranspose() {
    		EulerCircuit6 g = new EulerCircuit6(V);
    		for (int v = 0; v < V; v++) {
    			// 对与此顶点相邻的所有顶点遍历
    			Iterator<Integer> i = adj[v].listIterator();
    			while (i.hasNext()) {
    				g.adj[i.next()].add(v);
    				(g.in[v])++;
    			}
    		}
    		return g;
    	}
    
    	// 如果图是强连接的,则返回true
    	Boolean isSC() {
    		// Step 1: 将所有顶点标记为未访问(对于第一个DFS)
    		Boolean visited[] = new Boolean[V];
    		for (int i = 0; i < V; i++)
    			visited[i] = false;
    
    		// Step 2: 从第一个顶点开始进行DFS遍历.
    		DFSUtil(0, visited);
    
    		// 如果DFS遍历没有访问所有顶点,则返回false.
    		for (int i = 0; i < V; i++)
    			if (visited[i] == false)
    				return false;
    
    		// Step 3: 创建一个反转图
    		EulerCircuit6 gr = getTranspose();
    
    		// Step 4: 将所有顶点标记为未访问(对于第二个DFS)
    		for (int i = 0; i < V; i++)
    			visited[i] = false;
    
    		// Step 5: 从第一个顶点开始对反转图执行DFS.
    		// 起始顶点必须与第一个DFS的起始点相同
    		gr.DFSUtil(0, visited);
    
    		// 如果在第二个DFS中未访问所有顶点,则返回false
    		for (int i = 0; i < V; i++)
    			if (visited[i] == false)
    				return false;
    
    		return true;
    	}
    
    	/*
    	 * 如果有向图有欧拉回路,则此函数返回true; 否则返回false
    	 */
    	Boolean isEulerianCycle() {
    		// 检查是否连接了所有非零度顶点
    		if (isSC() == false)
    			return false;
    
    		// 检查每个顶点的进出度是否相同
    		for (int i = 0; i < V; i++)
    			if (adj[i].size() != in[i])
    				return false;
    
    		return true;
    	}
    
    	public static void main(String[] args) throws java.lang.Exception {
    		EulerCircuit6 g = new EulerCircuit6(5);
    		g.addEdge(1, 0);
    		g.addEdge(0, 2);
    		g.addEdge(2, 1);
    		g.addEdge(0, 3);
    		g.addEdge(3, 4);
    		g.addEdge(4, 0);
    
    		if (g.isEulerianCycle())
    			System.out.println("给定的有向图中 存在 欧拉回路 eulerian ");
    		else
    			System.out.println("给定的有向图中 不存在 欧拉回路 eulerian ");
    	}
    
    }
    

    程序运行结果:

    给定的有向图中 存在 欧拉回路 eulerian 

    展开全文
  • 有向图邻接表

    千次阅读 2019-01-11 18:18:09
    邻接表有向图是指通过邻接表表示的有向图。...下面代码中route是每一条有向的道路,它存在起始点和终点,唯一名称,长度等,town对应每个点,其中有一个包含所有以自身为起点的路的map集合 如果做不重复遍历一定...
  • 判断有向图是否有环

    千次阅读 2014-12-19 00:24:28
    对于有向图的拓扑排序,大家都知道的kahn算法: 计算图中所有的入度,把入度为0的加入栈 如果栈非空: 如果图中还存在顶点,则表示图中存在环;否则输出的顶点就是一个拓扑排序序列 取出栈顶顶点a,输出...
  • 【图结构专题】有向图

    万次阅读 2018-03-19 22:00:26
    有向图 一. 有向图的相关术语 在有向图中,边是单向的:每条边连接的...(1)==有向图==:一幅有向图是由一组顶点一组有方向的边组成的,每条有方向的边都连接着有序的一对顶点。 (2)==顶点的出度==:该顶...
  • 算法——图之加权有向图

    万次阅读 2017-05-27 15:26:17
    这篇讨论加权有向图。 加权有向图是在有向图的基础上,边的赋予权重信息的。 加权有向图有很多应用。最典型的就是最短路径问题。我们日常生活中也经常遇到这种问题,例如从一个出发,到达另外一个,怎么过去才是...
  • 邻接表有向图

    千次阅读 2018-08-14 22:47:20
    邻接表有向图的介绍 邻接表有向图是指通过邻接表表示的有向图。 上面的图G2包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"&lt;A,B&gt;,&lt;B,C&gt;,&lt;B,E&gt;,&lt;...
  • 什么是最短路径? ...指定中的一顶点为源点,找出源点到其它顶点的最短路径其长度的问题,即是单源最短路径问题。 什么是Dijkstra算法? 求解单源最短路径问题的常用方法是Dijkstra(迪杰...
  • 不带权有向图、无向图效果展示分段代码全部源代码:传送门 当我们处理完几百几千乃至上万的图论数据后总是不可避免地要对数据进行数据可视化等的分析 ,甚至要在画好图的基础上进行一些上层修改,增加连线,高亮...
  • 判断有向图是否有环有三种方法:拓扑排序、深度遍历+回溯、深度遍历 + 判断后退边 这里使用 拓扑排序 深度遍历 + 回溯判断是不是环。使用 深度遍历 + 判断后退边找出环个数 以及环中元素 1、拓扑排序 ...
  • 图(有向图、无向图)

    万次阅读 2013-12-03 17:02:06
    ⑶均为 (Graph),它若干个不同的 v 1, v 2, …, v n,在其中一些之间用直线或曲线连接。中的这些被称为顶点 (vertex)或结点,连接顶点的曲线或直线称为边 (edge)。通常将这种由若干个顶点...
  • 前面实现了链表树,现在看看图。 链表是一对一的对应关系; 树是一对多的对应关系; 图是多对多的对应关系。 图一般有两种存储方式,邻接表邻接矩阵。...因此,有向图邻接表的空间复杂度为O(v+e),无向图加倍。
  • 带权有向图最短路径

    千次阅读 2014-07-28 13:14:36
    1、带权有向图最短路径 1) 适用条件&范围: a) 单源最短路径(从源点s到其它所有顶点v); b) 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图) c) 所有边权非负(任取(i,j)∈E都有Wij≥0); 2) 算法...
  • 图论算法——环和有向无环

    万次阅读 2019-05-20 18:21:06
    有向图相关的实际应用中,有向环特别重要。一幅图可能含有大量的环,通常,我们一般只关注它们是否存在。 调度问题 给定一组任务并安排它们的执行顺序,限制条件为这些任务的执行方法、起始时间以及任务的消耗等...
  • 再看一个例子: 将上述代码中的child_graph改一下: child_graph = {"0": "1#5", "1": "2", "2": "3#4", "3": "0", "4": "", "5": "6", "6": "0"} 然后起始点为"0": dfs("0") 输出结果为: 0 1 2 3 0 5 6 可见,...
  • 有向图的邻接矩阵的计算

    万次阅读 2017-12-09 10:00:15
    有向图D=,V={v1,v2,…vn}。 如:给定有向图D=, V={a,b,c,d}, E={,,,,,,}. 一、需求分析 程序应满足如下功能: 1.能由有向图转换为对应的邻接矩阵。 2.能计算邻接矩阵A,A ²,A ³…A ⁿ. 3.图的邻接...
  • C++ 有向图最短路径之Dijkstra算法

    千次阅读 2019-03-26 22:01:42
    一、思路 1.Dijkstra算法 每次都是从起始顶点v出发,找与v有关的有向边<v,u>。找到<v, u>之后,找有向边<...,如果通过绕过顶点u而使从v到k的路径更...如上面的有向图起始顶点为0 (1)先将顶点...
  • 具体来说,Dijkstra算法主要用来寻找一个边的权值不为负的有向图中的任意一点到其他任意结点(在两相互联通的情况下)之间的最小路径。如果利用Dijkstra算法找出从一点出发,到图中其他所有的最短路径,事实上...
  • 最短路径算法是图论中的常见问题,... 无权是有权最短路径的特例,即边的权重均是1。算法类似于BFS(宽度优先搜索),在实现时需要一个宽度优先搜索的队列。全局变量Distance用来保存所有到输入顶点的距离。以邻接
  • 有向图的最短路径算法

    千次阅读 2016-07-27 22:52:47
    图中边带有方向就是有向图,否则就是无向图。图的存储结构分为邻接表邻接矩阵。(邻接表主要采用顺序存储链式存储结合的方式)。采用链接表这种都是对于稀疏图而言的(就是边少对应也就权值少的这种图叫稀疏图)...
  • 对于一个带负权值边的有向图,实现Bellman-Ford算法,求出从指定顶点s到其余顶点的最短路径,并判断图中是否存在负环。 Bellman-Ford算法的基本思路 对图中的边进行V-1轮操作(为什么是V-1轮?除了起始点,就只有V-1...
  • 有向图欧拉回路条数-BEST定理

    千次阅读 2017-08-09 21:30:38
    教学香肠系列……给定一张所有入度=出度的有向图,求欧拉回路条数。 n≤500n\leq 500为了避免出现重复,对于这个无向图,我们先确定一条11号节点出发的起始边。找一个以11号为根的内向树(即每个有唯一的一条...
  • #include &lt;iostream&gt; #define MAXVEX 4 //起始顶点数默认为6,可在此直接...//该代码是无向图的邻接表 //注意1:下标0的位置都不用,所以要多开辟一个空间 //注意2:头结点信息既可以是字符A,B,C,D,...
  • 有向图的十字链表存储形式

    千次阅读 2014-06-29 16:32:14
    可以看成是将有向图的邻接表逆邻接表(只考虑入度)结合起来得到的一种链表。在十字链表中,对应于有向图中每一个顶点有一个节点,每一条弧也有一个结点。 顶点之间是数组顺序存储,而弧是链式存储。 弧结点...
  • 用邻接表存储有向图实现的dfsbfs

    千次阅读 2017-11-30 12:51:06
    cout 输入的结点个数弧的个数\n"; cin >> G.vexnum; cin >> G.arcnum; cout 输入各结点按顺序编号下对应信息:"; for (i = 1; i ; i++) { cin >> G.Node[i].data; } cout 输入弧的信息\n"; char ...
  • 无回路有向图(Directed Acyclic Graph)的拓扑排序: package com.neusoft.data.structure; /** * Java: 无回路有向图(Directed Acyclic Graph)的拓扑排序 * 该DAG图是通过邻接表实...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 132,132
精华内容 52,852
关键字:

有向图的起始点和