精华内容
下载资源
问答
  • 2018-06-13 18:48:18

    1.1 术语

    有向图是由一组顶点和一组有方向的边组成的,每条有方向的边都连接着有序的一对顶点。

    有向图中,一个顶点的出度为由该顶点指出的边的总数;一个顶点的入度为指向该顶点的边的总数。

    有向图中,有向路径由一系列顶点组成,对于其中的每个顶点都存在一条有向边从它指向序列中的下一个顶点。有向环为一条至少含有一条边且起点和终点相同的有向路径。简单有向环是一条(除了起点和终点)不含重复顶点和边的环。路径或者环的长度即为其中包含的边数。

    1.2 有向图的可达性

    在有向图中,深度优先搜索标记由一个集合的顶点可达的所有顶点所需的时间与被标记的所有顶点的出度之和成正比。

    多点可达性的一个重要实际应用是在典型的内存管理系统中,包括许多Java的实现。在有向图中,一个点表示一个对象,一条边则表示一个对象对另一个对象的引用。这个模型很好地表现了Java程序的内存使用状况。在程序执行的任何时候都有某些对象是可以被直接访问的,而不能通过这些对象访问到的所有对象都应该被回收以便释放内存。标记-清楚的垃圾回收策略会为每个对象保留一个位做垃圾收集之用。它会周期性地运行一个有向图可达性算法来标记所有可以被访问到的对象,然后清理所有对象,回收没有被标记的对象,以腾出内存为新的对象使用。

    1.3 环和有向无环图

    1.3.1 有向图中的环

    寻找有向环的算法如下:

    public class DirectedCycle {
    	private boolean[] marked;
    	private int[] edgeTo;
    	private Stack<Integer> cycle;    // 有向环中的所有顶点
    	private boolean[] onStack;    // 递归调用栈上的所有顶点
    
    	public DirectedCycle (Diagraph G) {
    		onStack = new boolean[G.V()];
    		edgeTo = new int[G.V()];
    		marked = new boolean[G.V()];
    		for (int v = 0; v < G.V() ; v++ ) {
    			if (!marked[v]) {
    				dfs(G, v);
    			}
    		}
    	}
    
    	private void dfs(Diagraph G, int v) {
    		onStack[v] = true;
    		marked[v] = true;
    		for (int w : G.adj(v) ) {
    			if (this.hasCycle()) {
    				return;
    			}else if (!marked[w]) {
    				edgeTo[w] = v;
    				dfs(G, w);
    			}else if (onStack[w]) {
    				cycle = new Stack<Integer>();
    				for (int x = v; x != w ; x = edgeTo[x] ) {
    					cycle.push(x);
    				}
    				cycle.push(w);
    				cycle.psuh(v);
    			}
    		}
    		onStack[v] = false;
    	}
    
    	public boolean hasCycle() {
    		return cycle != null;
    	}
    
    	public Iterable<Integer> cycle(){
    		return cycle;
    	}
    }

    该类为标准的递归dfs方法添加了一个布尔类型的数组onStack[]来保存递归调用期间栈上的所有顶点。当它找到一条边v-w并且w在栈中时,它就找到了一个有向环。环上所有顶点可通过edgeTo得到。

    1.3.2 顶点的深度优先次序与拓扑排序

    优先级限制下的调度问题等价于计算有向无环图中的所有顶点的拓扑排序。

    当且仅当一个有向图它是无环图时它才能进行拓扑排序。

    有向图中基于深度优先搜索的顶点排序:

    public class DepthFirstOrder {
    	private boolean[] marked;
    	private Queue<Integer> pre;    // 前序排列(在递归调用之前将顶点加入队列)
    	private Queue<Integer> post;    // 后序排列
    	private Queue<Integer> reversePost;    // 逆后续排列(在递归调用之后把顶点压入栈)
    
    	public DepthFirstOrder (Diagraph G) {
    		pre = new Queue<Integer>();
    		post = new Queue<Integer>();
    		reversePost = new Queue<Integer>();
    		marked = new boolean[G.V()];
    		for (int v = 0; v < G.V() ; v++ ) {
    			if (!marked[v]) {
    				dfs(G, v);
    			}
    		}
    	}
    
    	private void dfs(Diagraph G, int v) {
    		pre.enqueue(v);
    		marked[v] = true;
    		for (int w : G.adj(v) ) {
    			if (!marked[w]) {
    				dfs(G,w);
    			}
    		}
    		post.enqueue(v);
    		reversePost.push(v);
    	}
    
    	public Iterable<Integer> pre(){
    		return pre;
    	}
    
    	public Iterable<Integer> post(){
    		return post;
    	}
    
    	public Iterable<Integer> reversePost(){
    		return reversePost;
    	}
    }

    一个有向无环图的拓扑排序即为所有顶点的逆后续排列。

    使用深度优先搜索对有向无环图进行拓扑排序所需的时间和V+E成正比。

    1.4 有向图的强连通性

    如果两个顶点v和w是互相可达的,则称它们为强连通的。也就是说,既存在一条从v到w的有向路径,也存在一条从w到v的有向路径。如果一个有向图的任意两顶点都是强连通的,则称这个有向图也是强连通的。

    1.4.1 强连通分量

    作为一种平等关系,强连通性将所有顶点分为了一些平等的部分,每个部分都是由相互均为强连通的顶点的最大子集组成的。这些子集称为强连通分量。

    1.4.2 Kosaraju算法

    计算强连通分量的Kosaraju算法如下:

    public class KosarajuSCC {
    	private boolean[] marked;    
    	private int[] id;    // 强连通分量的标识符
    	private int count;    // 强连通分量的数量
    
    	public KosarajuSCC (Diagraph G) {
    		marked = new boolean[G.V()];
    		id = new int[G.V()];
    		DepthFirstOrder order = new DepthFirstOrder(G.reverse());
    		for (int s : order.reversePost() ) {
    			if (!marked[s]) {
    				dfs(G, v);
    				count++;
    			}
    		}
    	}
    
    	private void dfs(Diagraph G, int v) {
    		marked[v] = true;
    		id[v] = count;
    		for (int w : G.adj(v) ) {
    			if (!marked[w]) {
    				dfs(G,w);
    			}
    		}
    	}
    
    	public boolean stronglyConnected(int v, int w){
    		return id[v] = id[w];
    	}
    
    	public int id(int v){
    		return id[v];
    	}
    
    	public int count(){
    		return count;
    	}
    }

    使用深度优先搜索查找给定有向图G的反向图GR,根据由此得到的所有顶点的逆后序再次用深度优先搜索处理有向图G(Kosaraju算法),其构造函数中的每一次递归调用所标记的顶点都在同一个强连通分量中。

    Kosaraju算法的预处理所需的时间和空间与V+E成正比且支持常数时间的有向图强连通性的查询。

    更多相关内容
  • 有向图的路径发现,从一个顶点出发,找到以该顶点为起始点的所有路径

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

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

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


    有向图的路径发现

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

    图: 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的功能)。

    展开全文
  • 使用c++实现的Dijkstra算法,主要是为了在有向图中寻找到起始点到终点;再返回起始点的最短路径;
  • 有向图: : 找出 途中 从 A 到 F 一共有多少中走法, 包含的闭环 有哪些 构思: 遍历前 先准备一个 list 用来存放当前路径, 从A开始 先找到B ,B找到D, D 到F, 此时 F为所找目标节点, 此时算是找到一条路径, ...

     有向图:   

    :  

    找出 途中 从 A  到  F  一共有多少中走法,  包含的闭环 有哪些   

    构思:   

    遍历前  先准备一个 list 用来存放当前路径,

    从A开始  先找到B  ,B找到D, D 到F,   此时  F为所找目标节点,  此时算是找到一条路径,     此时路径为    A ,B,D,F

    接下来  从 F 返回上一层   D   再找D 的另一个节点  C   ,C有两个子节点, 随便选一个  B,  此时 当前路径中存在一个B,重复了, 所以此处是一个环,  然后返回上一级C   再从C到 E   E到F ,   此时路径为   A ,B,D,C,E,F 

    再依次返回, 每上一层 都遍历找没有被访问过的子节点,    直到访问结束.

    (如果看不明白的童鞋还是多跑几次代码 ,然后找规律吧.这个确实不太好解释哈)

    其中用到递归

    上代码:     

     

    
    /**
     * @Annotion:   节点实体,一个实体对应的是一条线,链接两个节点
     * @ClassName: Node
     * @Author:
     * @Date: 2019/9/29  10:11
     * @Version: 1.0
     */
    public class Node {
        /**上游节点*/
        private String source;
        /**下游节点*/
        private String target;
    
        public Node(String source, String target) {
            this.source = source;
            this.target = target;
        }
    
        public String getSource() {
            return source;
        }
    
        public void setSource(String source) {
            this.source = source;
        }
    
        public String getTarget() {
            return target;
        }
    
        public void setTarget(String target) {
            this.target = target;
        }
    }
    /**
     * @Annotion: 从  一个点  到另一个点所有路径走法 ,并输出环
     * @ClassName: TwoPointsPath
     * @Author: 
     * @Date: 2019/9/29  9:54
     * @Version: 1.0
     */
    public class PointsPath {
        /**当前路径*/
        private static List<String> nowPath = new ArrayList<>();
    
        /**
         *
         * @param nodeList
         * @param source 起始节点
         * @param target 目标节点
         */
        public static void findAllPath(List<Node> nodeList,String source,String target){
            if(nowPath.contains(source)){
                System.out.println("这是一个环:"+nowPath);
                nowPath.remove(nowPath.size()-1);
                return;
            }
            for(int i = 0 ;i<nodeList.size();i++){
                Node node = nodeList.get(i);
                if(node.getSource().equals(source)){
                    nowPath.add(node.getSource());
                    if(node.getTarget().equals(target)){
                        nowPath.add(node.getTarget());
                        System.out.println("这是一条路径:"+nowPath);
                        /*因为添加了终点路径,所以要返回两次*/
                        nowPath.remove(nowPath.size()-1);
                        nowPath.remove(nowPath.size()-1);
                        /*已经找到路径,返回上层找其他路径*/
                        continue;
                    }
                    findAllPath(nodeList,node.getTarget(),target );
                }
            }
            /*如果找不到下个节点,返回上层*/
            if(nowPath.size()>0){
                nowPath.remove(nowPath.size()-1);
            }
    
        }
    
        /**
         * 测试
         */
        public static void main(String[] args){
            List<Node> list = new ArrayList<>();
            list.add(new Node("A", "B"));
            list.add(new Node("A", "C"));
            list.add(new Node("B", "D"));
            list.add(new Node("D", "F"));
            list.add(new Node("D", "C"));
            list.add(new Node("C", "B"));
            list.add(new Node("C", "E"));
            list.add(new Node("E", "F"));
    
            findAllPath(list,"A","F");
        }
    
    }

     

     

     

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

    万次阅读 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步骤,终止条件为当前的有向图为空或当前图中不存在无前驱的顶点为止。备注:若当前图中不存在无前驱的顶点,说明有向图中必然存在环。


    展开全文
  • JAVA代码详解: 有向图中判断欧拉路径欧拉回路 欧拉路径是图中访问每一条边一次的路径。 欧拉回路是在同一顶点上开始结束的欧拉路径。 有欧拉回路的图称为欧拉图。 上一篇博客讨论了无向图的欧拉回路。接...
  • 再看一个例子: 将上述代码中的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 可见,...
  • 什么是最短路径? ...指定中的一顶点为源点,找出源点到其它顶点的最短路径其长度的问题,即是单源最短路径问题。 什么是Dijkstra算法? 求解单源最短路径问题的常用方法是Dijkstra(迪杰...
  • Dijkstra算法实现有向图单源最短路径

    千次阅读 2016-10-24 11:53:15
    给定一个带权有向图G=(V,E),其中每条边的权都是非负实数。另外,还给定V中的一个顶点,称为源,现在要求解的是从源到其他所有顶点的最短路长度,即所经过路径的权的,这就是所谓的单源最短路径问题。   #...
  • 有向图的邻接矩阵 通过邻接矩阵来表示有向图。如下如所示: 上面的有向图G2包含了“A, B, C, D, E, F, G”共7个顶点,而且包含了“<A, B>, <B, C>, <B, E>, <B, F>, <C, F>, <D, ...
  • 图论算法——环和有向无环

    万次阅读 多人点赞 2019-05-20 18:21:06
    有向图相关的实际应用中,有向环特别重要。一幅图可能含有大量的环,通常,我们一般只关注它们是否存在。 调度问题 给定一组任务并安排它们的执行顺序,限制条件为这些任务的执行方法、起始时间以及任务的消耗等...
  • 图论算法——DFS求有向图或无向图两间所有路径

    万次阅读 多人点赞 2019-06-12 09:28:24
    DFS大法好! DFS作为搜索算法,最常...我在这里就介绍一下dfs求两的的所有路径,这个算法最开始在数据结构大作业里面用到了,当时费了一番劲写出来后,就想oj题里面这么变态的算法肯定不会出,后来还真的见过了。。。
  • 何为(Graph) 形似如下抽象结构: 这看起来的确有点抽象 ̄□ ̄||。。 我们再看一张: 这是一张二叉树,我在之前的基础上减去了几根“联系”就变成了树。 所以在一定程度上,可以把理解为树延伸(...
  • 【图结构专题】有向图

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

    千次阅读 2019-01-11 18:18:09
    邻接表有向图是指通过邻接表表示的有向图。...下面代码中route是每一条有向的道路,它存在起始点和终点,唯一名称,长度等,town对应每个点,其中有一个包含所有以自身为起点的路的map集合 如果做不重复遍历一定...
  • 1. 创建一个import networkx as nxg = nx.Graph()g.clear() #将上元素清空所有的构建复杂网络的操作基本都围绕这个g来执行。2. 节点节点的名字可以是任意数据类型的,添加一个节点是g.add_node(1)g.add_node(&...
  • 判断有向图是否有环

    千次阅读 2019-04-08 20:35:41
    中删除所有以a为起始点的边,如果删除的边的另一个顶点入度为0,则把它入栈 3.如果中还存在顶点,则表示中存在环;否则输出的顶点就是一个拓扑排序序列 例题:leetcode207 课程表 class Solution { public:...
  • C++ 有向图最短路径之Dijkstra算法

    千次阅读 2019-03-26 22:01:42
    一、思路 1.Dijkstra算法 每次都是从起始顶点v出发,找与v有关的有向边<v,u>。找到<v, u>之后,找有向边<...,如果通过绕过顶点u而使从v到k的路径更...如上面的有向图起始顶点为0 (1)先将顶点...
  • 有向图最短路径(LINGO实现)

    千次阅读 2020-02-07 14:07:42
    model: sets: cities/A,B1,B2,C1,C2,C3,D/;...除了起点重点,出入度相同; @sum(roads(i,j)|i #eq#1:x(i,j))=1;!启动只有1个出度; @sum(roads(i,j)|j #eq#n:x(i,j))=1;!终点只有1个入度; end
  • Java:判断有向图中的环路(DFS)

    千次阅读 2020-07-03 17:37:15
    问题定义 我们先从一个简单的问题展开:一个有向图G,包含了0,1,2,3,4五个顶点,其中边有0->1,1->2,2->0,0->3,0->4。判断是否出现环路。 解析 有向图如图所示:
  • 不带权有向图、无向图效果展示分段代码全部源代码:传送门 当我们处理完几百几千乃至上万的图论数据后总是不可避免地要对数据进行数据可视化等的分析 ,甚至要在画好图的基础上进行一些上层修改,增加连线,高亮...
  • 算法——图之加权有向图

    万次阅读 2017-05-27 15:26:17
    这篇讨论加权有向图。 加权有向图是在有向图的基础上,边的赋予权重信息的。 加权有向图有很多应用。最典型的就是最短路径问题。我们日常生活中也经常遇到这种问题,例如从一个出发,到达另外一个,怎么过去才是...
  • 查阅了网上许多关于通过DFS算法对有向图中所有简单回路的查找,发现有很多关于使用DFS求解有向回路中所有简单回路的帖子,(在按照节点编号情况下)但大多数仅仅寻找了编号递增的回路。又或者未对结果去重。P.S.下述...
  • 前面实现了链表树,现在看看图。 链表是一对一的对应关系; 树是一对多的对应关系; 图是多对多的对应关系。 图一般有两种存储方式,邻接表邻接矩阵。...因此,有向图邻接表的空间复杂度为O(v+e),无向图加倍。
  • 有向图的邻接矩阵的计算

    万次阅读 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.图的邻接...
  • ①无向图的非递归深度优先搜索需借用一个堆栈保存被访问过的顶点,以便回溯查找已被访问结点的被访问过的邻接点。 ②访问起始顶点v0,visited[v0]标记1,v0入栈,指针p指向v0对应的边表首结点; ③从左到右扫描p所指的...
  • 特点:是以起始点为中心外层层扩展(?) 基本思想: 指定起点s,即从顶点s开始计算。 引进两个集合SU。 S:记录已求出最短路径的顶点(以及相应的最短路径长度), U:记录还未求出最短路径的顶点(以及该...
  • 创建(无)向图,深度优先遍历,广度优先遍历 代码实现: #include<stdio.h> #include<stdlib.h> #include<string.h> #define MaxVertexNum 100 #define MaxSize 10 //顶点数目的最大值 ...
  • 有向无环(邻接矩阵邻接表)

    千次阅读 2020-04-08 01:23:39
    是由顶点的穷非空集合顶点之间边的集合组成,通常表示为:  G=(V,E) 其中:G表示一个,V是G中顶点的集合,E是G中顶点之间边的集合。 注: 在线性表中,元素个数可以为零,称为空表; 在树中,...
  • 【题目】试写一个求有向图G中所有简单回路的算法 【测试数据】123456对应ABCDEF 【结果】 【答案】 /*---------------------------------------------------------------- |7.30 求有向图中所有简单回路 ....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 150,117
精华内容 60,046
关键字:

有向图的起始点和