精华内容
下载资源
问答
  • 一个是创建弧的信息,包括弧的相关顶点和权值,可存储到二维数组里,其中,二维数组的下标分别表示两个顶点的弧尾和弧头编号,权值存放在对应的数组中。 创建一个网: 请输入有向网N的顶点数和弧数:6 9 请输入6个...


    可分两部分:一个是创建顶点信息,可用一个一维数组存储;另一个是创建弧的信息,包括弧的相关顶点和权值,可存储到二维数组里,其中,二维数组的下标分别表示两个顶点的弧尾和弧头编号,权值存放在对应的数组中。
    创建一个网:
    请输入有向网N的顶点数和弧数:6 9
    请输入6个顶点的值:
    a b c d e f
    请分别输入9条弧的弧尾 弧头 权值(以空格分隔):
    a b 6
    a e 5
    a f 9
    f c 7
    b c 8
    b f 6
    c d 5
    d a 12
    e d 3

    code:

    #include <stdio.h>
    #include <string.h>
    #include <malloc.h>
    #include <stdlib.h>
    #include <iomanip>
    #include <iostream>
    using namespace std;
    typedef char VertexType[4];
    typedef char InfoPtr;
    typedef int VRType;
    #define INFINITY 65535
    #define MAXSIZE 100
    typedef enum{DG,DN,UG,UN}GraphKind;//图的类型,有向图、有向网、无向图、无向网
    typedef struct  
    {
    	VRType adj;//无权图,1表示相邻,0表示不相邻;对于带权图,存储权值
    	InfoPtr *info; //弧或边的相关信息
    }ArcNode,AdjMatrix[MAXSIZE][MAXSIZE];
    typedef struct  
    {
    	VertexType vex[MAXSIZE];//用于存储顶点
    	AdjMatrix arc;
    	int vexnum, arcnum;//顶点数和边(弧)的数
    	GraphKind kind;//图的类型
    
    }MGraph;
    
    void CreateGraph(MGraph *N);
    int LocateVertex(MGraph N,VertexType v);
    void DestoryGraph(MGraph *N);
    void DisplayGraph(MGraph N);
    void main()
    {
    	MGraph N;
    	cout << "创建一个网:" << endl;
    	CreateGraph(&N);
    	cout << "输出网的顶点和弧:" << endl;
    	DisplayGraph(N);
    	DestoryGraph(&N);
    	system("pause");
    }
    void CreateGraph(MGraph *N)
    {
    	int i, j, k, w;
    	VertexType v1, v2;
    	cout << "请输入有向网N的顶点数和弧数:";
    	cin >> (*N).vexnum >> (*N).arcnum;
    	cout << "请输入" << N->vexnum << "个顶点的值:" << endl;
    	for (i = 0; i < N->vexnum;i++)
    	{
    		cin >> N->vex[i];
    
    	}
    	for (i = 0; i < N->vexnum;i++)
    	{
    		for (j = 0; j < N->vexnum; j++)
    		{
    			N->arc[i][j].adj = INFINITY;
    			N->arc[i][j].info = NULL;
    
    		}
    	}
    	cout << "请分别输入" << N->arcnum << "条弧的弧尾 弧头 权值(以空格分隔):" << endl;
    	for (k = 0; k < N->arcnum;k++)
    	{
    		cin >> v1 >> v2 >> w;
    		i = LocateVertex(*N, v1);
    		j = LocateVertex(*N, v2);
    		N->arc[i][j].adj = w;
    	}
    
    	
    	N->kind = DN;
    
    }
    
    int LocateVertex(MGraph N, VertexType v)
    {
    	int i;
    	for (i = 0; i < N.vexnum;++i)
    	{
    		if (strcmp(N.vex[i],v)==0)
    		{
    			return i;
    		}
    		
    	}
    	return -1;
    }
    
    void DestoryGraph(MGraph *N)
    {
    	int i, j;
    	for (i = 0; i < N->vexnum;i++)
    	{
    		for (j = 0; j < N->vexnum;j++)
    		{
    			if (N->arc[i][j].adj!=INFINITY)
    			{
    				if (N->arc[i][j].info!=NULL)
    				{
    					free(N->arc[i][j].info);
    					N->arc[i][j].info = NULL;
    				}
    			}
    		}
    	}
    	N->vexnum = 0;
    	N->arcnum = 0;
    }
    
    
    void DisplayGraph(MGraph N)
    {
    	int i, j;
    	cout << "有向网具有" << N.vexnum << "个顶点" << N.arcnum << "条弧,顶点依次是:";
    
    	for (i = 0; i < N.vexnum;++i)
    	{
    		cout << N.vex[i] << " ";
    	}
    	cout << endl << "有向网N的" << endl;
    	cout << "顶点:";
    	for (i = 0; i < N.vexnum;i++)
    	{
    		cout << setw(7) << N.vex[i];
    	}
    	cout << endl;
    	for (i = 0; i < N.vexnum;i++)
    	{
    		cout << setw(6) << N.vex[i];
    		for (j = 0; j < N.vexnum;j++)
    		{
    			cout << setw(7) << N.arc[i][j].adj;
    
    		}
    		cout << endl;
    	}
    }

    结果:

     

    展开全文
  • 这里有一个无向图的深度遍历算法,无向图 深度优先遍历 c语言实现, 有向图的DFS遍历跟这个算法一样。 利用DFS判断一个有向图是否有环的思路是:对一个节点v进行深度遍历,判断是否能从v到达自己这个节点,即是否...

    这里有一个无向图的深度遍历算法,无向图 深度优先遍历 c语言实现, 有向图的DFS遍历跟这个算法一样。
    利用DFS判断一个有向图是否有环的思路是:对一个节点v进行深度遍历,判断是否能从v到达自己这个节点,即是否存在从v到v的环路。
    在图的深度遍历中,我们将图中每个节点设置为三个状态:-1,0,1,分别表示还没发现的节点;已经发现但是还没处理完的节点;已经处理完的节点。对应上述思路,假设我们正在处理v,那么v的状态为0,其余正在处理节点的状态也为0,如果从状态为0的节点遍历到状态为0的节点就存在环。
    下面是leetcode中的一个题:Course Schedule,可以用dfs来解决,代码如下(下面代码效率很低,仅用来说明用dfs发现环的思路),

    
    import java.util.ArrayList;
    import java.util.List;
    
    public class Solution {
    
        boolean flag = true;
    
        public void dfs(List<List<Integer>> adjList,int v,int[] color){
    
            color[v] = 0;   //表示正在处理v节点
            List<Integer> adjs = adjList.get(v); 
    
            for(int i=0;i<adjs.size();i++){
                if(color[adjs.get(i)]==-1){
                    dfs(adjList,adjs.get(i),color);
                }else if(color[adjs.get(i)]==0){//回到了状态为0的节点,有环
                    flag = false;
                }
            }
            color[v] = 1;
        }
    
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            List<List<Integer>> adjList = new ArrayList<List<Integer>>();
    
            //根据course个数初始化一个空的邻接表
            for(int i=0;i<numCourses;i++){
                adjList.add(new ArrayList<Integer>());
            }
            //初始化color数组
            int[] color = new int[numCourses];
            for(int i=0;i<numCourses;i++){
                color[i] = -1;
            }
    
            //adjList表示邻接表,头结点是后面的课程,后面的list表示先修课
            //由先修课指向 后修课
            for(int i=0;i<prerequisites.length;i++){
                int[] cp = prerequisites[i];
                adjList.get(cp[1]).add(cp[0]);
            }
    
            //下面对邻接表进行深度遍历,看看是否有环,从每一个节点都遍历一次
            for(int i=0;i<numCourses;i++){
                dfs(adjList, i, color);
                if(!flag){
                    return false;
                }
                for(int j=0;j<numCourses;j++){
                    color[j] = -1;
                }
            }
            return flag;
        }
    
        public static void main(String[] args) {
            Solution s = new Solution();
            //4, [[0,1],[3,1],[1,3],[3,2]]
            int[][] nums = {{0,1},{0,2},{1,2}};
    
            System.out.println(s.canFinish(3, nums));
        }
    }
    展开全文
  • 有向图和无向图

    万次阅读 多人点赞 2019-04-13 18:51:19
    有向图和无向图是我们常用到的术语,本文属于简单的科普帖。 全部由无向边构成图称为无向图(Undirected Graph),全部由有向边构成图称为无向图(Directed Graph)。有向,顾名思义,有方向。本文中顶点Vertex(V)...

    有向图、无向图

    有向图和无向图是我们常用到的术语,本文属于简单的科普帖。

    全部由无向边构成图称为无向图(Undirected Graph),全部由有向边构成图称为有向图(Directed Graph)。有向,顾名思义,有方向。本文中顶点Vertex(V),边Edge(E)

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

    在这里插入图片描述
    (2)描述图的邻接矩阵和关联矩阵
    【邻接矩阵】

    定义:
    设无向图G=(V,E),其中顶点集V=v1,v2,…,vn,边集 E=e1,e2,…,eε。用aij表示顶点vi与顶点vj之间的边数,可能取值为0,1,2,…,称所得矩阵A=A(G)=(aij)n×n为图G的邻接矩阵。邻接矩阵可以描述有向图和无向图。

    示例,求图所示简单图的邻接矩阵?
    在这里插入图片描述
    解:根据定义,可求得该无向图的邻接矩阵为
    在这里插入图片描述

    邻接矩阵的存储特点:
    (a)无向图的邻接矩阵一定是一个对称矩阵,有向图不一定是。
    *(b)邻接矩阵所需的存储空间值域只与顶点数有关系。
    (c)用邻接矩阵存储图,容易判断两个点之间是否有边。
    (d)如果一个有向图的邻接矩阵为三角矩阵(主对角线为0),则它的拓扑排序一定存在。
    *(e)小技巧:
    无向图:邻接矩阵的第i行或者第i列的非零元素的个数正好是第i个顶点Vi的度;
    有向图:邻接矩阵的第i行的非零元素个数正好是第i个顶点Vi的出度,第i列非零元素的个数正好是第i个顶点Vi的入度。

    【关联矩阵】

    定义:
    设任意图G=(V,E),其中顶点集V=v1,v2,…,vn,边集E=e1,e2,…,eε。用mij表示顶点vi与边ej关联的关系,可能取值为0,1,-1,称所得矩阵M(G)=(mij)n×ε为图G的关联矩阵。
    在这里插入图片描述
    mij 表示i行j列,探究顶点Vi和边Ej之间的关系,形成下列的关联矩阵
    示例:
    在这里插入图片描述
    关联矩阵
    在这里插入图片描述

    连通图、连通分量

    连通图:无向图中,若从顶点u到顶点v有路径,称为u,v是连通的。若图中任意两个顶点均是连通的,则称为连通图。
    连通分量:无向图中极大连通子图称为连通分量。

    强连通图、强连通分量

    强连通图:有向图中,若从顶点u到顶点v有路径,称为u,v是连通的。若图中任意两个顶点均是连通的,则称为强连通图。
    连通分量:无向图中极大连通子图称为强连通分量。特:强连通图只有强连通分量(本身),非强连通图有多个强连通分量。

    另外,本文参考路了下面两位作者的优秀博客
    https://blog.csdn.net/Hanging_Gardens/article/details/55670356
    https://blog.csdn.net/legendaryhaha/article/details/83049101

    展开全文
  • dfs判断一个有向图是否有环

    万次阅读 2018-01-18 20:23:34
    我们可以用一个color数组代表每个结点的状态,-1代表还没被访问,0代表正在被访问,1代表访问结束 如果一个状态为“0”的结点,与他相连的结点状态也为“0”的话就代表环,这个可以dfs实现 #include <...

    解决这个问题的算法的思路是对一个节点u进行dfs,判断是否能从u回到自己这个节点,即是否存在从u到u的回路。 

    我们可以用一个color数组代表每个结点的状态,-1代表还没被访问,0代表正在被访问,1代表访问结束
    如果一个状态为“0”的结点,与他相连的结点状态也为“0”的话就代表有环,这个可以用dfs实现

    #include <iostream>
    #include <vector>
    #include <string.h>
    #include <stdio.h>
    
    using namespace std;
    
    
    /*
    color代表每个结点的状态,-1代表还没被访问,0代表正在被访问,1代表访问结束
    如果一个状态为“0”的结点,与他相连的结点状态也为0的话就代表有环,这个可以用dfs实现
    */
    
    const int N = (int)1e5 + 10;
    
    vector <int> vec[N];
    int color[N];
    
    bool dfs(int u) {
        color[u] = 0; // 0表示正在访问
        for (int v: vec[u]) {
            if (color[v] == 0) { //如果正在访问的点又被访问到则代表有环
                return false;
            } else if (color[v] == -1) { // -1代表还没有访问
                if (!dfs(v)) {
                    return false;
                }
            }
        }
        color[u] = 1; // 1代表访问结束
        return true;
    }
    
    int main()
    {
        int n, m;
        cin >> n >> m;
        for (int i = 0; i < m; i++) {
            int from, to;
            cin >> from >> to;
            vec[from].push_back(to);
        }
        memset(color, -1, sizeof(color));
        auto check = [&] () -> bool {
            for (int i = 1; i <= n; i++) {
                if (color[i] == -1) {
                    if (!dfs(i)) {
                        return false;
                    }
                }
            }
            return true;
        };
        puts(check() ? "no have" : "have");
        return 0;
    }
    
    /*
    int n,m;
    
    for(i -> m)
        vec[u].p(v)
    
    
        
        dfs(x)
            if(flag) return
            color x <- 0;
            for i -> size
                if color u = -1
                    dfs u
                else if color u = 0
                    flag = true
                    return
                    
            color x = 1
    
    */
    

     

     

     

     

     

    展开全文
  • 无向图有向图邻接矩阵表示

    千次阅读 2016-12-03 09:16:52
    1.无向图的邻接矩阵表示法验证程序  采用邻接矩阵表示向图,完成图的创建、图的深度优先遍历、图的广度优先遍历操作。其中图的顶点信息是字符型,图中顶点序号按字符顺序排列。本输入样例中所用的图如下所示...
  • 有向图和无向图差别就是句代码的差别 ,无向图中代码注释掉即可 有向图和有向网的差别也就是权值的差别 有向网需要赋予权值 有向图有连线自动赋值为1 深度优先采用递归方法(参考前面几篇文章,里面有具体的...
  • 算法——图之有向图

    千次阅读 2017-05-24 20:02:43
    我们主要讨论一下方面: 1.有向图表示 ...和无向图中的一样,我们也采用邻接表矩阵的方式来表示有向图。只需要修改addEdge方法,只增加条边,而不是增加双向边就可以了。 public class DiGraph
  • 判断一个有向图是否有环

    万次阅读 2012-12-22 00:47:20
    给出一个有向图,判断图中是否存在回路。 Input 第1行:输入图的顶点个数N(1 ≤ N≤ 2,500)和C(图的边数,1 ≤ C ≤ 6,200); 第2到C+1行中,第i+1行输入两个整数,分别表示第i条边的起点和终点的...
  • 的邻接矩阵表示
  • package dn1124; /**  * @author sj E-mail: ... * @version 创建时间: 2017-11-26 下午10:16:38  * 类说明: (带权有向图)邻接矩阵表示图代码实现  */ public class Graph { public static final int MAX_WEIG
  • 有向图及拓扑排序

    万次阅读 2018-10-20 23:06:53
    虽然边的性质不同,但我们仍然可以邻接表来表示有向图。对有向图的结构定义如下: #include <map> #include <forward_list> using namespace std; struct DirectedGraph { size_t V, E;...
  • 概率有向图模型

    万次阅读 2017-03-05 21:11:44
    个人感觉概率有向图模型最大的意义在于:一个特定的有向图表示将联合概率分布分解为条件概率分布乘积的形式。 2. 概念 2.1 等价概念 概率有向图模型、贝叶斯网络(Bayesian network)、信念网络...
  • 有向图和无向图邻接矩阵储存

    万次阅读 多人点赞 2017-04-08 09:15:47
    所谓邻接矩阵,是用一个二维数组存储,边使用矩阵构建模型,这使得每一个顶点和其它顶点之间都边的有无 的 表示的机会。若边,则他们交点 为1 ,否则为0。当然,如果是一副边权值的,交点存储的是他们边...
  • 有向图的邻接表表示

    万次阅读 2011-04-15 09:27:00
    在邻接表表示法中,两种结点,分别是头结点和表结点头结点后面跟的表结点表示是所有起点为头结点,终点为表结点的边。#include using namespace std; #define MAX_VERTEX_NUM 50//定义的最大顶点数 typedef ...
  • 图论-有向图缩点

    千次阅读 2018-04-22 19:29:48
    强连通(strongly connected): 在一个有向图G里,设两个点 a b 发现,由a有一条路可以走到b,由b又有一条路可以走到a,我们就叫这两个顶点(a,b)强连通。强连通图: 如果 在一个有向图G中,每两个点都强连通,我们...
  • 判断一个图是否有环 无向图 有向图

    万次阅读 2011-06-11 21:44:00
    http://www.cnblogs.com/hiside/archive/2010/12/01/1893878.htmlhttp://topic.csdn.net/u/20071023/11/3edb81fc-37b2-4506-906e-44dc0fc521f2.html一、无向图:方法1:如果存在回路,则必存在一个子图,是一个环路...
  • 邻接链表存储无向图和有向图

    千次阅读 2017-04-08 09:48:44
    篇文章我们说到邻接矩阵存储有向图和无向图,这种方法的有点是很直观的知道点与点之间的关系,查找的复杂度是为O(1)。但是这种存储方式同时存在着占用较多存储空间的问题, 邻接矩阵存储很好理解,但是,有...
  • 有向图的深度和广度遍历

    万次阅读 2018-05-04 09:33:26
    对于下图所示的有向图(访问顺序按序号从小到大),试写出: (1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树;(2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树。 package com.test.tree; ...
  • 两种方式判断有向图是否有环...我们用一个变量标记某结点的访问状态(未访问,访问过,其后结点都被访问过),然后判断每一个结点的深度遍历路线即可。 def dfs(G,i,color): r = len(G) color[i] = -1 have_cir...
  • 由邻接矩阵画有向图、无向图

    万次阅读 2017-07-19 10:39:08
    由邻接矩阵画有向图、无向图 由邻接矩阵画有向图的逻辑如下: 设邻接矩阵的行(列)数为N,矩阵中非零元素的个数为M,画布宽为W、高为H 1、有向图顶点数为N、有向边数为M,问题转化为:画正N边形的所有顶点、以及顶点...
  • 有向图和无向图邻接矩阵储存及代码实现

    万次阅读 多人点赞 2017-09-14 17:26:48
    所谓邻接矩阵,是用一个二维数组存储,边使用矩阵构建模型,这使得每一个顶点和其它顶点之间都边的有无 的 表示的机会。若边,则他们交点 为1 ,否则为0。当然,如果是一副边权值的,交点存储的是他们边...
  • 图论基础知识(四) —— 有向图

    千次阅读 2019-03-01 15:51:52
    称为一个有向图,其中,V称为顶点集,其中的元素称为顶点或点;A称为弧集,其中的元素是弧。   由定义可见,有向图和无向图的区别仅仅在于有向图的弧集是有序对的多重集,而无向图的边集是无序顶点对的多重集,无...
  • 有向图的几算法分析总结

    万次阅读 2016-12-27 09:52:46
    简介  前面讨论的很多文章里,都是针对无向图...和无向图比起来,有向图更加多了种出入度的概念。因为方向的有向性,很多以前在无向图里看起来比较简单的问题在这里会变得更加有意思。   有向图定义  
  • 数据结构:有向无环表示

    千次阅读 2017-02-10 11:22:31
    数据结构:有向无环表示最近在做workflow的时候有用到怎么去存储一个有向无环,在百度上看到一个答复感觉很棒 http://blog.chinaunix.net/uid-24774106-id-3505579.html文中使用先是 malloc 一个内存然后每当...
  • 有向图 G=(V, E) 的拓扑排序

    千次阅读 2020-08-13 20:55:21
    有向图的拓扑排序是针对...只有有向图中入度为0的顶点才能成为拓扑排序的第一个顶点,不断重复地寻找入度为0的顶点,即可得到拓扑排序结果,具体方法可以通过深度优先搜索或广度优先搜索解决有向图的拓扑排序问题。
  • 【图结构专题】有向图

    万次阅读 2018-03-19 22:00:26
    有向图中,边是单向的:每条边连接的两个顶点都是一个有序对,它们的邻接性是单向的。我们开发过程中碰到的很多场景都是有向图:比如任务調度的依赖关系,社交网络的任务关系等等都是天然的有向图。 以下概念都是...
  • 判断无向图和有向图是否有回路

    万次阅读 多人点赞 2014-03-06 00:22:47
    连接顶点u到它的某一祖先顶点v的边),即在DFS对顶点进行着色过程中,若出现所指向的顶点为黑色,则此顶点是一个已经遍历过的顶点(祖先),出现了后边,若完成DFS后,则回路;另外,无环中变的个数E  2...
  • 概率图模型之有向图与无向图

    千次阅读 2016-06-12 20:32:18
    图模型图结构描述随机变量之间的依赖关系,结点表示随机变量,边表示随机变量之间的依赖关系,可以是有向图和无向图。 无向图模型 无向图模型又叫马尔可夫网络、马尔可夫随机场,是关于组有马尔可夫性
  • 有向图的环和有向无环图

    千次阅读 2018-07-25 07:10:00
    本篇主要分享关于有向图的环和有向无环图(DAG,估计做大数据的同学到处都可以看到),所以相关概念我就不做详细介绍了。 用有向图中各个节点代表着一个一个的任务,...
  • 有向图和无向图的相关概念

    千次阅读 2020-04-29 15:44:42
    图的定义:  图在数据结构中是中一对多的关系,一般分为无向图与无向图  常用 邻接矩阵 或者 邻接链表 ...对于图7-1所示的无向图G1和有向图G2,它们的数据结构可以描述为:  G1=(V1,E1), 其中 V1={a,b,c,d...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,090,437
精华内容 436,174
关键字:

我们用一个有向图来表示