精华内容
下载资源
问答
  • 有向图邻接

    千次阅读 2019-01-11 18:18:09
    邻接有向图是指通过邻接表表示的有向图有向图可以理解为一种数据结构,处理特定场景的问题会比较简单 对于java来说,用map实现有向图比较便于进行查找操作。 实现有向图这种数据结构并不困难,难的是如何...

    邻接表有向图是指通过邻接表表示的有向图。

    有向图可以理解为一种数据结构,处理特定场景的问题会比较简单

    对于java来说,用map实现有向图比较便于进行查找操作。

    实现有向图这种数据结构并不困难,难的是如何对有向图遍历。

    下面代码中route是每一条有向的道路,它存在起始点和终点,唯一名称,长度等,town对应每个点,其中有一个包含所有以自身为起点的路的map集合

    如果做不重复遍历一定要加限制条件,下面的后面两个方法(不包含递归的方法)就是以距离和经过的点的数量为限制进行遍历查找

    /**
         * 选取两地间所有不重复的路线
         *
         * @param towns
         * @return
         */
        public LinkedList<String> findRoutesNonRepetitive(String towns) {
            // 处理参数
            String[] townArray = towns.toUpperCase().split("-");
            String beginName = townArray[0];
            if (!Utils.checkTownName(beginName, townsMap)) {
                System.out.println("起始城镇名称错误");
                return null;
            }
            String endName = townArray[1];
            if (!Utils.checkTownName(endName, townsMap)) {
                System.out.println("终点城镇名称错误");
                return null;
            }
    
            // 用于保存选取出的路线
            LinkedList<String> routeList = new LinkedList<>();
            // 用于标记已选过的路线
            LinkedList<String> flag = new LinkedList<>();
    
            selectRoutesByRecursionNonRepetitive(flag, beginName, endName, routeList);
    
            return routeList;
        }
    
     /**
         * 递归选出不重复路线
         *
         * @param flag
         * @param beginName
         * @param endName
         * @param routeList
         */
        public void selectRoutesByRecursionNonRepetitive(LinkedList<String> flag, String beginName, String endName, LinkedList<String> routeList) {
            // 遍历已存在的每一条线路
            for (String routeName : setAllRouteName) {
                if (routeName.startsWith(beginName)) {
                    // 判断该路线是否存在于标记路线中,不存在,说明此路尚未走,则此路可选
                    if (!flag.contains(routeName)) {
                        flag.add(routeName);
                        Route route = routeMap.get(routeName);
                        // 如果该路线的终点城镇名等于endName,则进行保存
                        if (route.getEndTownName().equals(endName)) {
                            String s = Utils.formatList(flag);
                            routeList.add(s);
                        }
                        // 将终点城镇赋值给起始城镇,递归遍历
                        beginName = route.getEndTownName();
                        selectRoutesByRecursionNonRepetitive(flag, beginName, endName, routeList);
                        // 递归之后要将起始城镇向前重置,并删除标记路线的最后一个节点
                        if (flag != null && flag.size() != 0) {
                            beginName = flag.removeLast().split("-")[0];
                        }
                    }
                }
            }
        }
    
        /**
         * 以站点数量为限制选取可重复路线
         *
         * @param i
         * @param towns
         */
        public LinkedList<String> selectRoutesByStops(int i, String towns) {
            // 处理参数
            int count = i;
            String[] townArray = towns.toUpperCase().split("-");
            String beginName = townArray[0];
            if (!Utils.checkTownName(beginName, townsMap)) {
                System.out.println("起始城镇名称错误");
                return null;
            }
            String endName = townArray[1];
            if (!Utils.checkTownName(endName, townsMap)) {
                System.out.println("终点城镇名称错误");
                return null;
            }
    
            // 用于保存选取出的路线
            LinkedList<String> routeList = new LinkedList<>();
            // 用于标记已选过的路线
            LinkedList<String> flag = new LinkedList<>();
    
            selectRoutesByRecursion(flag, beginName, endName, routeList, count, 0);
    
            return routeList;
    
        }
    
        /**
         * 递归选出可重复路线
         *
         * @param flag
         * @param beginName
         * @param endName
         * @param routeList
         * @param count     外部传入的限定值
         * @param sign      自身用于递归增长的判断值
         */
        public void selectRoutesByRecursion(LinkedList<String> flag, String beginName, String endName, LinkedList<String> routeList, int count, int sign) {
    
            // 遍历已存在的每一条线路
            for (String routeName : setAllRouteName) {
                sign++;
                // 自身递归小于等于限定值时,可以继续递归
                if (sign <= count) {
                    if (routeName.startsWith(beginName)) {
                        flag.add(routeName);
                        Route route = routeMap.get(routeName);
                        // 如果该路线的终点城镇名等于endName,则进行保存
                        if (route.getEndTownName().equals(endName)) {
                            String s = Utils.formatList(flag);
                            routeList.add(s);
                        }
                        // 将终点城镇赋值给起始城镇,递归遍历
                        beginName = route.getEndTownName();
                        selectRoutesByRecursion(flag, beginName, endName, routeList, count, sign);
                        // 递归之后要将起始城镇向前重置,并删除标记路线的最后一个节点
                        if (flag != null && flag.size() != 0) {
                            beginName = flag.removeLast().split("-")[0];
                        }
                    }
                }
                sign--;
            }
        }
    
    
        /**
         * 以总距离为限制选取可重复路线
         *
         * @param i
         * @param towns
         */
        public LinkedList<String> findRoutesByDistance(int i, String towns) {
            // 处理参数
            int totalDistance = i;
            String[] townArray = towns.toUpperCase().split("-");
            String beginName = townArray[0];
            if (!Utils.checkTownName(beginName, townsMap)) {
                System.out.println("起始城镇名称错误");
                return null;
            }
            String endName = townArray[1];
            if (!Utils.checkTownName(endName, townsMap)) {
                System.out.println("终点城镇名称错误");
                return null;
            }
    
            // 用于保存选取出的路线
            LinkedList<String> routeList = new LinkedList<>();
            // 用于标记已选过的路线
            LinkedList<String> flag = new LinkedList<>();
    
            queryRoutesByDistance(flag, beginName, endName, routeList, totalDistance, 0);
    
            return routeList;
    
        }
    
        /**
         * 根据距离,递归选出不重复路线
         *
         * @param flag
         * @param beginName
         * @param endName
         * @param routeList
         * @param totalDistance 外部传入的限定值
         * @param distance      自身用于递归增长的判断值
         */
        public void queryRoutesByDistance(LinkedList<String> flag, String beginName, String endName, LinkedList<String> routeList, int totalDistance, int distance) {
    
            // 遍历已存在的每一条线路
            for (String routeName : setAllRouteName) {
    
                distance += getDistanceOfTown(routeName);
                // 路线距离小于最大距离时,可以继续递归
                if (distance < totalDistance) {
                    if (routeName.startsWith(beginName)) {
    
                        flag.add(routeName);
                        Route route = routeMap.get(routeName);
                        // 如果该路线的终点城镇名等于endName,则进行保存
                        if (route.getEndTownName().equals(endName)) {
                            String s = Utils.formatList(flag);
                            routeList.add(s);
                        }
                        // 将终点城镇赋值给起始城镇,递归遍历
                        beginName = route.getEndTownName();
                        queryRoutesByDistance(flag, beginName, endName, routeList, totalDistance, distance);
                        // 递归之后要将起始城镇向前重置,并删除标记路线的最后一个节点
                        if (flag != null && flag.size() != 0) {
                            beginName = flag.removeLast().split("-")[0];
                        }
                    }
                }
                distance -= getDistanceOfTown(routeName);
            }
    
        }

     

     

    参考:http://www.cnblogs.com/skywang12345/

    展开全文
  • C# 有向图 邻接矩阵 实现路径查询 查询两间的所有路径
  • 有向图邻接矩阵

    万次阅读 2018-05-06 18:39:04
    :是一种线性结构,由n个和m条边组成,任意两个之间可以用连线连接. #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #define MAX_VALUE 8888 //初始化数组的默认值,相当于无限大 #...

    这里写图片描述

    图:是一种线性结构,由n个点和m条边组成,任意两个点之间可以用连线连接.

    #include <stdio.h>
    #include <stdlib.h>
    #define  MAX_VALUE 8888 //初始化数组的默认值,相当于无限大
    #define  MAX_POINT_NUM 10  //最大顶点数
    typedef int  matrix[MAX_POINT_NUM][MAX_POINT_NUM];
    
    //定义有向图的邻接矩阵的结构体
    typedef struct 
    {
        int vertex[MAX_POINT_NUM];//储存顶点的数组
        matrix vertex_matrix;//二维数组
        int vertex_num;//顶点数
        int arc_num;//边数
    }digraph;
    
    int  locatevertex(digraph * graph,int v)
    {
        int i;
        for(i=0;i<graph->vertex_num;i++)
        {
            if(graph->vertex[i]==v)
            {
                return i;
            }
        }
        return -1;
    }
    
    void  init_digraph(digraph * graph)
    {
        printf("please input vertex and arc:\n");//输入顶点和边数
        scanf("%d%d",&(graph->vertex_num),&(graph->arc_num));
        int i;
        printf("please input vertex point value:\n");//输入顶点的编号
        for(i=0;i<graph->vertex_num;i++)
        {
            scanf("%d",&graph->vertex[i]);
        }
        int j;
        i=0;
        for(i=0;i<graph->vertex_num;i++)
        {
            for(j=0;j<graph->vertex_num;j++)
            {
                graph->vertex_matrix[i][j]=MAX_VALUE;//统一初始化存放顶点间权重值
            }
        }
    
        int v1,v2;
        int weight;
        printf("please input between arc two point and weight:\n");
        //输入两个顶点及他们之间的权重值
        int k;
        for(k=0;k<graph->arc_num;k++)
        {
            scanf("%d%d%d",&v1,&v2,&weight);
            i=locatevertex(graph,v1);
            j=locatevertex(graph,v2);
            graph->vertex_matrix[i][j]=weight;
        }    
    }
    
    //打印有向图的邻接矩阵
    void print_digraph(digraph * graph)
    {
        int i,j;
        for(i=0;i<graph->vertex_num;i++)
        {
            for(j=0;j<graph->vertex_num;j++)
            {
                if(graph->vertex_matrix[i][j]==MAX_VALUE)
                {
                    printf("N\t");
                }
                else
                {
                    printf("%d\t",graph->vertex_matrix[i][j]);
                }
            }
            printf("\n");
        }
    }
    int main(int argc,const char *argv[])
    {
        digraph  graph;
        init_digraph(&graph);
        print_digraph(&graph);
        return 0;
    }

    运行结果:
    这里写图片描述

    展开全文
  • 邻接矩阵的记录 邻接矩阵分为两种: ...设表示一个有向图的连通关系的邻接矩阵为$A$,在$A$中的元素$A_{i,j}$如果为1,那么表示原图中点$i$,$j$之间通过一条长度为$1$的边直接相连,那么$A^k$中的$A^k...

    邻接矩阵的记录

    邻接矩阵分为两种:

    ①:存的是边权(记作$D$),

      

    ②:没有边权的, 记录的是连通关系(记作$A$),

      

     

     

    连通关系的邻接矩阵幂的意义:

    设表示一个有向图的连通关系的邻接矩阵为$A$,在$A$中的元素$A_{i,j}$如果为1,那么表示原图中点$i$,点$j$之间通过一条长度为$1$的边直接相连,那么$A^k$中的$A^k_{i,j}$表示点点$i$,点$j$之间能通过$k$条边相连。感性理解一下还是能够理解的。。。

    举个例子吧,先去大佬的blog中借用例子。。。https://blog.csdn.net/u010504064/article/details/39781709?utm_source=blogxgwz0

     

    在平方后我们依然得到了一个二维矩阵,其中的每个元素值的含义是以有向图中节点的直接邻接点是否可达为准。

    用图描述

     

    图1 有向图

     

    图2 有向图的邻接矩阵表示  

     

    图 3有向图的平方后的矩阵

     

          就是以1节点的邻接点2为准,这个邻接点所有的邻接点3,也就是说图3中第一行第三个元素的值为1表示1节点可以通过它的邻接点2访问到3,同理第二行最后一个元素为1表示节点2可以通过3访问到4,,当然元素为0表示该节点不能间接到达,当元素值为1表示有一条路径可以到达,元素值为2的时候有两条路径可以到达。

     

    那么$A^k$的意义是什么?(两个点之间若有边则$A[u][v]=1$)

    从$Floyd$算法的角度考虑,不难发现$A^k$的第$i$行第$j$列的数字含义是从$i$到$j$经过$k$步的路径方案总数。

     

     习题:

      Luogu 3758 [TJOI2017]可乐:https://www.luogu.org/problemnew/show/P3758

      解题思路:https://www.cnblogs.com/Dxy0310/p/9840451.html

    C=A×B

    转载于:https://www.cnblogs.com/Dxy0310/p/9838613.html

    展开全文
  • 有向图的出度和邻接点

    千次阅读 2019-01-03 23:55:37
    采用邻接矩阵存储有向图,输出顶点v的出度和所有邻接点。  Input 有多组测试数据,每组的第一行为图的顶点数n和边数e(0&lt;n&lt;20);第二行为n个顶点的值,按输入顺序从下标0开始存储;接下来有e行,...

     Problem Description

    采用邻接矩阵存储有向图,输出顶点v的出度和所有邻接点。

     Input

    有多组测试数据,每组的第一行为图的顶点数n和边数e(0<n<20);第二行为n个顶点的值,按输入顺序从下标0开始存储;接下来有e行,每行表示一条边所依附的两个顶点的下标i和j,中间用空格隔开;最后一行为顶点下标v(0<=v<n)。

     Output

    每组输出占两行,第一行为顶点v的出度,第二行按字母表顺序输出顶点v的邻接点,每两个邻接点之间有一逗号。(注:当v的出度为0时第二行为空行。)

     Sample Input

    4 4
    ABCD
    0 1
    0 2
    2 3
    3 0
    1
    
    5 7
    ABCDE
    0 2
    0 1
    1 3
    1 2
    2 4
    3 0
    4 3
    1

     Sample Output

    0
    
    2
    C,D
    #include <iostream>
    #include <stdlib.h>
    #define maxvex 20
    #include<stdio.h>
    using namespace std;
    
    typedef struct {
        int adjvex;
    
    } ArcCell,ArcCells[maxvex][maxvex];
    
    typedef struct {
        char vertex[maxvex];
        ArcCells arcs;
        int arcnum,vexnum;
        int deg[maxvex];
    } MatrixGraph;
    
    
    struct ArcNode {
        int adj;
        ArcNode* next;
    };
    
    typedef struct {
        ArcNode* firstedge;
        char vex;
    } Edge,Edges[maxvex];
    
    typedef struct {
        Edges edges;
        int arcnum,vertexnum;
        int deg[maxvex];
    } Graph;
    
    void CreatDG(Graph&G,int n,int e) {
        G.arcnum=e;
        G.vertexnum=n;
        for(int i=0; i<n; i++) {
            cin>>G.edges[i].vex;
            G.edges[i].firstedge=NULL;
            G.deg[i]=0;
        }
        for(int i=0; i<e; i++) {
            int a,b;
            cin>>a>>b;
            ArcNode* p=new ArcNode;
            p->adj=b;
            p->next=G.edges[a].firstedge;
            G.edges[a].firstedge=p;
        }
    }
    
    void Deg(Graph& G) {
        for(int i=0; i<G.vertexnum; i++) {
            ArcNode* p=G.edges[i].firstedge;
            while(p) {
                G.deg[p->adj]++;
                p=p->next;
            }
        }
    
    }
    
    void DegMartrix(MatrixGraph &G){
    for(int i=0;i<G.vexnum;i++){
        for(int j=0;j<G.vexnum;j++){
            if(G.arcs[i][j].adjvex!=0){
                G.deg[i]++;
            }
        }
    }
    
    }
    
    
    void PrintDegAdj(const MatrixGraph& G,int a){
    //for(int i=0;i<G.vexnum;i++){
            int blank=0;
             cout<<G.deg[a]<<endl;
        for(int j=0;j<G.vexnum;j++){
    
            if(G.arcs[a][j].adjvex!=0){
                if(blank!=0){
                    cout<<",";
                }
                cout<<G.vertex[j];
                blank++;
            }
        }
    cout<<endl;
    //}
    }
    
    void Print(Graph G) {
    
        for(int i=0; i<G.vertexnum; i++) {
    
            ArcNode* p=G.edges[i].firstedge;
            while(p) {
                cout<<p->adj<<" ";
                p=p->next;
            }
            cout<<endl;
        }
    }
    
    
    void CreatUDM(MatrixGraph &G,int n,int e) {
    
        G.arcnum=e;
        G.vexnum=n;
        for(int i=0; i<G.vexnum; i++) {
            cin>>G.vertex[i];
            G.deg[i]=0;
            for(int j=0; j<G.vexnum; j++) {
                G.arcs[i][j].adjvex=0;
    
            }
        }
    
    
    
        for(int i=0; i<G.arcnum; i++) {
            int a,b;
            cin>>a>>b;
            G.arcs[a][b].adjvex=1;
        //    G.arcs[b][a].adjvex=1;
        }
    
    }
    
    
    
    
    
    
    
    
    bool vistited[maxvex];
    
    void InitVistied() {
    
        for(int i=0; i<maxvex; i++) {
            vistited[i]=false;
        }
    }
    
    
    
    void MatrixDFSTraverse(MatrixGraph G,int v) {
        vistited[v]=true;
        cout<<G.vertex[v]<<":";
        for(int j=0; j<G.vexnum; j++) {
            if(G.arcs[v][j].adjvex!=0) {
                cout<<G.vertex[j];
            }
        }
        cout<<endl;
        for(int i=0; i<G.vexnum; i++) {
            if(!vistited[i]&&G.arcs[v][i].adjvex!=0) {
                MatrixDFSTraverse(G,i);
            }
        }
    
    
    }
    
    int main() {
        freopen("1.txt","r",stdin);
        int n,e;
    
        while(cin>>n>>e) {
           MatrixGraph g;
          CreatUDM(g,n,e);
          DegMartrix(g);
          int a;
          cin>>a;
          PrintDegAdj(g,a);
    
        }
        return 0;
    }
    
    
    
    
    

     

    展开全文
  • 有向图邻接表的实现

    千次阅读 2019-06-12 08:54:36
    #include <iostream> using namespace std; const int maxsize=10; int visited[maxsize]={0}; struct ArcNode//定义边表节点 ...//邻接点域 ArcNode *next; }; template<class DataType> struc...
  • GPLOTD(A,XY) 使用下面描述的默认样式绘制由邻接矩阵 A 和 xy 表示的有向图GPLOTD(A,XY,PARAM1,VAL1,...) 使用有效的参数名称/值对绘制有向图输入: A - NxN 邻接矩阵,其中 A(I,J) 非零当且仅当 I 和 J 之间...
  • 题目大意:给定一个有向图,从图中一点a到另一点b只走k步(包括b)有多少种方案? 2.这是一个很有用的性质,结论就是这个图邻接矩阵的k次幂对应的矩阵那个的数值。其实证明也不难,我们从矩阵乘法可以看出一点...
  • 定义有向图邻接矩阵A的周期为最小的d,使得存在正整数k,对于任意n>=k,都有\(A^n=A^{n+d}\) 最小的k称为A的幂敛指数。 现给出一个n个,m条边有向图,求它的邻接矩阵的周期对10^9+7取模的结果。 n<=100000,m...
  • 有向图-邻接

    千次阅读 2017-04-27 20:27:13
    有向图邻接表,自我感觉比邻接矩阵要理解复杂一点,但是节省的空间不是小数目,所以虽然复杂,但是我们还是要优先考虑邻接表吧。 下面代码简单的写了邻接表,但是基本核心的代码全部包括了,之后图中加权的我也在...
  • 写C程序,随机给出n*n的邻接矩阵,并打印输出邻接矩阵,以及有向图的边的个数,每个顶点... 这个题目涉及到了两个主要的知识,一个是数据结构中的有向图邻接矩阵的创建,还有就是离散数学中的Euler回路的判定定理。
  • GPLOTDC 绘制有向图GPLOTDC(A,XY) 使用下面描述的默认样式绘制由邻接矩阵 A 和 xy 表示的有向图GPLOTDC(A,XY,PARAM1,VAL1,PARAM2,VAL2,...) 使用有效的参数名称/值对绘制有向图 输入: A - NxN 邻接矩阵,其中 A(I...
  • 数据结构:图的实现(输出有向图邻接矩阵与出度和最大的) 【问题描述】 需要分别基于邻接矩阵和邻接表来实现图ADT 需要实现图的各个基本操作 小明最近在学习数据结构中图的相关知识,他需要输出有向图邻接...
  • 有向图的创建,插入删除顶点,插入删除弧,打印邻接矩阵和邻接表,查看顶点下标。 注:先分结构介绍,最后是完整代码和运行结果。 弧结点↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ typedef struct ArcNode ...
  • 有向图邻接矩阵的计算

    万次阅读 2017-12-09 10:00:15
    自主学习四.实验设计 实验题目:图的邻接矩阵计算 ...1.能由有向图转换为对应的邻接矩阵。 2.能计算邻接矩阵A,A ²,A ³…A ⁿ. 3.图的邻接矩阵可用来求到点之间的通路条数。所以程序应能求出点到点之间不同长
  • 1.生成一个100个,3000条边的有向随机图,任选一点作为源点,计算S到其他节点的距离。(注:图用邻接链表存储) 2.将实验一中的有向图变为DAG图。(从中去掉一些边,不允许用递归) 计算上述DAG图中的最长路径。
  • 邻接矩阵画有向图、无向图

    万次阅读 2017-07-19 10:39:08
    邻接矩阵画有向图、无向图 由邻接矩阵画有向图的逻辑如下: 设邻接矩阵的行(列)数为N,矩阵中非零元素的个数为M,画布宽为W、高为H 1、有向图顶点数为N、有向边数为M,问题转化为:画正N边形的所有顶点、以及顶点...
  • 为了下一步的有向有权单源最短路径做基础 代码 1.用邻接矩阵表示的 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class MatrixShortestPath { static int n;//...
  • 向图的度和邻接点

    千次阅读 2018-12-24 19:43:34
    采用邻接矩阵存储无向连通,输出顶点v的度和所有邻接点。 Input 多组测试数据,每组的第一行为的顶点数n和边数e(0&lt;n&lt;20);第二行为n个顶点的值,按输入顺序从下标0开始存储;接下来e行,每...
  • #include &lt;iostream&gt; #define MAXVEX 4 //起始顶点数默认为6,可在此直接...//该代码是无向图邻接表 //注意1:下标0的位置都不用,所以要多开辟一个空间 //注意2:头结点信息既可以是字符A,B,C,D,...
  • 代码中设置两没边,则这两对应的二维数组值为0,其他有边的两看是否为带权图,是则二维数组值就为两的权值,不是则用一个特定的数字来代表这两有边,当然还要判断这个图是有向图还是无向图了,具体实现看
  • 有向图邻接表遍历 ,有注释,只想赚分,原作者别介意。
  • 1072: 有向图邻接矩阵存储根计算 题目描述 若有向图中存在一个顶点v,从v可以通过路径到达图中其他所有顶点,那么称v为该有向图的根。假设图G采用邻接矩阵存储,求有向图的所有根。 输入 第一行为一个整数n,表示...
  • 邻接链表存储无向图和有向图

    千次阅读 2017-04-08 09:48:44
    上一篇文章我们说到用邻接矩阵存储有向图和无向图,这种方法的有点是很直观的知道之间的关系,查找的复杂度是为O(1)。但是这种存储方式同时存在着占用较多存储空间的问题, 邻接矩阵存储很好理解,但是,有...
  • package algorithm; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.util.StringTokenizer; public class GraphReverse { private static int ... //的个数 priv

空空如也

空空如也

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

有向图邻接点