精华内容
下载资源
问答
  • 有向图邻接矩阵c++运算操作 基本操作 邻接矩阵 c++实现
  • 有向图邻接矩阵

    万次阅读 2018-05-06 18:39:04
    :是一种线性结构,由n个点和m条边组成,任意两个点之间可以用连线连接. #include <stdio.h> #include <stdlib.h> #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;
    }

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

    展开全文
  • C# 有向图 邻接矩阵 实现路径查询 查询两点间的所有路径
  • //数值类型 整型//创建有向图邻接矩阵//把邻接矩阵转换成临界表//把值大于50的顶点保存在单链表中//输出邻接矩阵,临界表,大于50的结点#include&lt;stdio.h&gt;#include&lt;malloc.h&gt;#define ...
    //数值类型 整型
    //创建有向图邻接矩阵
    //把邻接矩阵转换成临界表
    //把值大于50的顶点保存在单链表中

    //输出邻接矩阵,临界表,大于50的结点

    #include<stdio.h>
    #include<malloc.h>


    #define VNUM 20
    #define max 20


    //定义邻接矩阵
    typedef struct
    {
    int vexs[VNUM];
    int arcs[VNUM][VNUM];
    int vexNum,arcNum;
    }MGraph;


    //定义临界表边结点
    typedef struct ArcNode
    {
    int adjvex;
    struct ArcNode * nextArc;
    }ArcNode;


    //定义临界表表头结点
    typedef struct VertexNode
    {
    int vertex;
    ArcNode *FirstArc;
    }VertexNode;


    //定义图的临接表类型
    typedef struct ALGraph
    {
    VertexNode adjlist[max];
    }ALGraph;


    //定义单链表结点
    typedef struct Lnode
    {
    int data;
    struct Lnode *next;
    }Lnode,*LinkList;


    void CreateGraph(MGraph *G,int v,int a,LinkList *L);
    void CreateAdjlist(ALGraph *G,int v,MGraph *M);
    void initLinkList(LinkList *L);
    void displayALGraph(ALGraph *A,int v);
    void displayLinkList(LinkList L);
    void displayMGraph(MGraph *G,int v,int a);




    void initLinkList(LinkList *L)
    {
    *L=(LinkList)malloc(sizeof(Lnode));
    if(*L==NULL)
    return 0;
    (*L)->next=NULL;
    return 1;
    }


    void CreateGraph(MGraph *G,int v,int a,LinkList *L)
    {
    int i,j,k;
    LinkList s;
    for(i=0;i<v;i++)
    {
    printf("请输入第%d个顶点的值\n",i+1);
    scanf("%d",&G->vexs[i]);
    if(G->vexs[i]>50)
    {
    s=(LinkList)malloc(sizeof(Lnode));
    s->data=G->vexs[i];
    s->next=(*L)->next;
    (*L)->next=s;
    }
    }
    for(i=0;i<v;i++)
    for(j=0;j<v;j++)
    G->arcs[i][j]=0;
    for(k=0;k<a;k++)
    {
    printf("请读入第%d条边邻接的两个从1开始的序号\n",k+1);
    scanf("%d%d",&i,&j);
    G->arcs[i-1][j-1]=1;
    }
    }


    void CreateAdjlist(ALGraph *G,int v,MGraph *M)
    {
    int i,m,n;
    ArcNode *p;
    for(i=0;i<v;i++)
    {
    G->adjlist[i].vertex=M->vexs[i];
    G->adjlist[i].FirstArc=NULL;
    }
    for(m=0;m<v;m++)
    for(n=0;n<v;n++)
    {
    if(M->arcs[m][n]==1)
    {
    p=(ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex=n;
    p->nextArc=G->adjlist[m].FirstArc;
    G->adjlist[m].FirstArc=p;
    }
    }

    }


    //输出邻接矩阵
    void displayMGraph(MGraph *G,int v,int a)
    {
    int i,j;
    for(i=0;i<v;i++)
    {
    for(j=0;j<v;j++)
    {
    printf("%d ",G->arcs[i][j]);
    }
    printf("\n");
    }
    }


    //输出单链表
    void displayLinkList(LinkList L)
    {
    LinkList p=L->next;
    if(p==NULL)
    printf("没有大于50的顶点\n");
    while(p)
    {
    printf("%d \n",p->data);
    p=p->next;
    }
    }


    //输出临接表
    void displayALGraph(ALGraph *A,int v)
    {
    int i;
    ALGraph *p=A;
    for(i=0;i<v;i++)
    {
    printf("%d %d->",i,p->adjlist[i].vertex);
    while(p->adjlist[i].FirstArc)
    {
    printf("%d->",p->adjlist[i].FirstArc->adjvex);
    p->adjlist[i].FirstArc=p->adjlist[i].FirstArc->nextArc;
    }
    printf("\n");
    }
    printf("\n");
    }


    void main()
    {
    int v,a;//定点数和边数
    MGraph G;
    ALGraph A;
    LinkList L;
    initLinkList(&L);
    printf("请输入顶点数和边数\n");
    scanf("%d%d",&v,&a);
    printf("创建邻接矩阵\n");
    CreateGraph(&G,v,a,&L);
    printf("创建邻接表\n");
        CreateAdjlist(&A,v,&G);
    printf("输出邻接矩阵\n");
    displayMGraph(&G,v,a);
    printf("输出邻接表\n");
    displayALGraph(&A,v);
    printf("输出顶点大于50的单链表\n");
    displayLinkList(L);
    }

    展开全文
  • 有向图邻接矩阵深度优先搜索

    千次阅读 2018-11-04 18:34:29
    上一个文章是写的无向图和邻接链表的广度搜索,深度搜索就用矩阵有向图了。 矩阵处理起来还是会比链表简单一些。 先分析数据结构: 1.储存所有结点的集合用到了一个单向循环链表,为什么要用循环链表呢,因为在...

    上一个文章是写的无向图和邻接链表的广度搜索,深度搜索就用矩阵和有向图了。
    矩阵处理起来还是会比链表简单一些。

    先分析数据结构:
    1.储存所有结点的集合用到了一个单向循环链表,为什么要用循环链表呢,因为在存储结点数据的时候是按照输入数据的顺序来储存的,如果是用一个数组或者单向链表,我们可以得到数组或链表第一个元素作为源节点的遍历,但是我要是指定数组中的第三个元素作为源节点呢。这样就不太好操作了,所以用了一个循环的链表,先把指针移到指定的任意一个源节点作为表头再继续操作。
    其他的就是普通的二维数组结构体等没什么特别的了。

    注意:
    结点的输入顺序还是得记一个位置,因为二维数组是按那个顺序建立的,有一个position可以把二维数组和链表一一对应起来。
    其实很难一次性不出问题,我一般第一次运行都是得不到结果或者只得到部分结果。但是只要会调试,其他的都不是什么问题了,特别是main函数是一个一个处理的,每个函数都是一次一次调用的,在调试的时候哪里出问题了会很明显。
    还有就是最近发现的一个小skill,在定义结构体的时候可以把key啊这类的明显的不同的变量先定义,在调试的时候就能先显示看到它。
    下面代码看函数名基本就知道是在干嘛,注释写的有点少将就看一下。

    #include "stdafx.h"
    #include<stdio.h>
    #include<stdlib.h>
    #define N 6       //plane to create a 6*6 matrix
    int time;    //the whole proccess's time 
    int n = 0;
    
    
    typedef enum Color{ W, G, B }Color;
    typedef struct vertex_ *vertex;
    typedef struct vertex_
    {
    	int key;
    	int d;     //start time
    	int f;     //final time
    	int position;  //store the position of this vertex, position .position is determined by input sentence
    	Color c;
    	vertex parent;
    }v;
    
    typedef struct list_ *list;
    typedef struct list_      //创建一个单向循环链表
    {
    	vertex v;
    	list next;
    //	int position;   //to correspond this position with metrix
    }l;
    
    void DFS_VISIT(int a[][N], list head, vertex x);
    void DFS(int a[][N], vertex b[]);
    
    vertex INI_VERTEX(int key)
    {
    	vertex x = (vertex)malloc(sizeof(v));
    	x->key = key;
    	x->d = 0;
    	x->f = 0;
    	x->position = n;
    	x->parent = NULL;
    	x->c = W;
    	n++;
    	return x;
    }
    
    void INI_METRIX(int a[][N])
    {
    	for (int i = 0; i < N; i++)
    		for (int j = 0; j < N; j++)
    			a[i][j] = 0;
    }
    list INI_LIST(list x)
    {
    	x = (list)malloc(sizeof(l));
    	x = NULL;
    	return x;
    //	x->next = NULL;
    //	x->v = NULL;
    }
    void CONNECTION(int a[][N],vertex out, vertex in)  
    {
    	a[out->position][in->position] = 1;
    }
    
    list MOVE_HEAD(list head, vertex x)
    {
    	list p = (list)malloc(sizeof(l));
    	p = head;
    	if (head->v->position == x->position)
    	{
    		return head;
    	}
    
    	else
    	{
    		p = p->next;
    		while (p != head)
    		{
    			if (p->v->position == x->position)
    				return p;
    			p = p->next;
    		}
    	}
    }
    
    void DFS(int a[][N],list head)
    {
    	list p = head;
    	while(p->next!=head)  //循环一圈
    	{
    		if (p->v->c == W)
    			DFS_VISIT(a, head, p->v);
    		p=p->next;
    	}
    	if (p->v->c == W)
    		DFS_VISIT(a, head, p->v);
    }
    
    
    void DFS_VISIT(int a[][N], list head, vertex x)
    {
    	time = time++;
    	x->d = time;
    	x->c = G;
    	for (int i = 0; i<N; i++)
    		if (a[x->position][i] == 1 )
    		{
    			list p = head;
    			while (p->next != head)  //循环一圈
    			{
    				if (p->v->position == i && p->v->c == W)
    				{
    					p->v->parent = x;
    					DFS_VISIT(a,head, p->v);
    				}
    				p=p->next;
    			}
    			//97行p->next了,在检查while的时候还要next,就会导致链表的最后一个元素无法进行处理,所以最后追加一个对最后一个元素的处理,下面还有两个类似的处理
    			//个人感觉比起先判断p==head的代码量要少那么一点点。
    			if (p->v->position == i && p->v->c == W)         
    			{
    				p->v->parent = x;
    				DFS_VISIT(a, head, p->v);
    			}
    			
    		}
    	x->c = B;
    	time = time + 1;
    	x->f = time;
    }
    
    list INSERT_VERTEX(list head, vertex x)
    {
    	list new_p = (list)malloc(sizeof(l));
    	new_p->next = NULL;
    	new_p->v = x;
    //	new_p->position = n;
    //	n++;
    	if (head == NULL)
    	{
    		head = new_p;
    		head->next = head;
    	}
    	else 
    	{
    		list p = head;        //遍历传进来这个链表,看他是什么情况
    		while (p->next != head)
    		{
    			p = p->next;
    		}     //遍历一遍,找到新节点插入的位置,
    		p->next = new_p;
    		new_p->next = head;
    	}
    	return head;
    }
    int main()
    {
    	int a[N][N];
    	list b = (list)malloc(sizeof(l));
    	vertex p1, p2, p3, p4, p5, p6;
    	INI_METRIX(a);
    	b=INI_LIST(b);
    	
    	p1=INI_VERTEX(8);
    	p2=INI_VERTEX(3);
    	p3=INI_VERTEX(6);
    	p4=INI_VERTEX(7);
    	p5=INI_VERTEX(5);
    	p6=INI_VERTEX(10);
    	
    
    	b=INSERT_VERTEX(b, p1);
    	b=INSERT_VERTEX(b, p2);
    	b=INSERT_VERTEX(b, p3);
    	b=INSERT_VERTEX(b, p4);
    	b=INSERT_VERTEX(b, p5);
    	b=INSERT_VERTEX(b, p6);
    
    
    	CONNECTION(a, p1, p2);
    	CONNECTION(a, p1, p3);
    	CONNECTION(a, p2, p3);
    	CONNECTION(a, p3, p4);
    	CONNECTION(a, p4, p2);
    	CONNECTION(a, p5, p4);
    	CONNECTION(a, p5, p6);
    	CONNECTION(a, p6, p6);
    	
    	printf("当头指针是p3,(key=6)时\n");
    	b=MOVE_HEAD(b, p3);
    
    
    	DFS(a, b);
    	list p=b;
    	while (p->next != b)
    	{
    		printf("(%d,  d=%d,f=%d)\n", p->v->key, p->v->d, p->v->f);
    		p = p->next;
    	}
    	printf("(%d,  d=%d,f=%d)\n", p->v->key, p->v->d, p->v->f);
        return 0;
    }
    
    
    

    在这里插入图片描述

    在这里插入图片描述

    展开全文
  • 有向图邻接矩阵幂的意义

    千次阅读 2019-09-29 07:37:59
    邻接矩阵的记录 邻接矩阵分为两种: ...设表示一个有向图的连通关系的邻接矩阵为$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

    展开全文
  • %% 无向图邻接矩阵和关联矩阵转换function w = incandadf(F,f)%F为输入无向图矩阵可以是邻接矩阵或关联矩阵%% 邻接矩阵转关联矩阵if f == 0 m = sum(sum(F))/2; n = size(F,1); w = zeros(n,m); k = 1; for i = 1:n ...
  • 写C程序,随机给出n*n的邻接矩阵,并打印输出邻接矩阵,以及有向图的边的个数,每个顶点的度,并判断该图中是否存在Euler回路: (1)如果为n阶,则随机产生一个n*n的邻接矩阵; (2)输出邻接矩阵,边的个数,每个...
  • 无向图有向图邻接矩阵表示法

    千次阅读 2016-12-03 09:16:52
    1.无向图邻接矩阵表示法验证程序  采用邻接矩阵表示无向图,完成图的创建、图的深度优先遍历、图的广度优先遍历操作。其中图的顶点信息是字符型,图中顶点序号按字符顺序排列。本输入样例中所用的图如下所示...
  • GF = [ [0,4,6,0,0], [0,0,2,3,0], [0,0,0,0,4], [0,0,0,0,5], [0,0,0,0,0] ] g={} for i in range(len(GF)): a=[] for j in range(len(GF)): if GF[i][j]!=0: a.appe...
  • 有向图邻接矩阵

    2013-06-17 12:33:46
    c语言写的有向图邻接矩阵的实现,通过使用图的邻接矩阵实现图的存储结构存储。
  • 有向图不对称邻接矩阵变无向图对称邻接矩阵 一个简单图实例 import numpy as np # 使用numpy编写的上述有向图邻接矩阵如下: # 不对称邻接矩阵 A = np.matrix([ [0,1,0,0], [0,0,1,1], [0,1,0,0], [1,0,1,0]...
  • *顺序储存有向图邻接矩阵 *定义一个边的权值的二维数组 *定义一个点的一维数组 *创建一个邻接矩阵 *输出这个邻接矩阵 */ #include<stdio.h> #include<string.h> #include<stdlib.h> #define ...
  • 向图邻接矩阵的创建

    千次阅读 多人点赞 2019-01-29 16:00:49
    首先创建邻接矩阵的结构体,变量存放顶点信息的一维数组(Vexs),存放边的信息的二维数组(Edge),当前的顶点数和边数这四个变量,然后创建一个子函数CreateMGraph用来创建无向图邻接矩阵,在创建一个子函数...
  • ——邻接矩阵

    千次阅读 2016-09-06 21:54:38
    邻接矩阵分为有向图邻接矩阵和无向图邻接矩阵。对无向图(无向简单图)而言,邻接矩阵一定是对称的,而且对角线一定为零,有向图则不一定如此。 “test.cpp” #define _CRT_SECURE_NO_WARN
  • 数据结构 有向图邻接矩阵

    千次阅读 2019-12-18 11:44:13
    数据结构 有向图邻接矩阵邻接矩阵中,每一个元素表示行对应的顶点与列对应的定点之间是否有弧(1有,0没有)
  • 向图邻接矩阵转邻接表,邻接表转邻接矩阵

    千次阅读 多人点赞 2018-06-19 14:19:26
    ///printf(" 有向图G的邻接矩阵:\n"); //DispMat(g); G=new ALGraph; //printf(" 图G的邻接矩阵转换成邻接表:\n"); MatToList(g,G); DispAdj(G); /* printf(" 图G的邻接表转换成邻接邻阵:\n"); for (i=0;i;i...
  • package Graph; import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class AdjMatrix { ... //邻接矩阵 public AdjMatrix(String fileName) { File f
  • 有向图邻接矩阵、邻接表和逆邻接表

    万次阅读 多人点赞 2018-12-24 14:18:05
    1、如何根据有向图画出邻接矩阵?...画有向图的邻接表时,要看出边,即自身指向别人的边。 如图所示: 第一排的v1,指向v2和v3,因此两个黄色方框内的数字分别代表v2和v3的下标,即1和2; 第二排的v...
  • C语言建立有向图邻接矩阵及其遍历操作 1 /*C语言建立有向图邻接矩阵及其遍历操作*/ 2 #include"stdio.h" 3 #include"stdlib.h" 4 //图的邻接矩阵储存结构 5 typedef char elemtype; 6...
  • 邻接矩阵有向图、无向图

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

    千次阅读 2017-12-29 21:15:58
    无向图和有向图邻接矩阵中的表示方法:  无向图和有向图大同小异,在这里只以无向图为例,代码部分通过简单调整即可对应编译有向图 邻接矩阵数据类型定义 #define MaxVertices 100 //定义最大容量 ...
  • 有向图邻接矩阵的计算

    万次阅读 2017-12-09 10:00:15
    自主学习四.实验设计 实验题目:图的邻接矩阵计算 ...1.能由有向图转换为对应的邻接矩阵。 2.能计算邻接矩阵A,A ²,A ³…A ⁿ. 3.图的邻接矩阵可用来求点到点之间的通路条数。所以程序应能求出点到点之间不同长
  • 向图邻接矩阵转换为邻接表 代码如下(C): #include <stdio.h> #include<stdlib.h> #define MAXV 100 //以下定义邻接矩阵类型 typedef struct { int vexs[MAXV]; int arcs[MAXV]...
  • 一次上机练习——有向图邻接矩阵转化为邻接表并存储顶点大于50的值 小渣渣写的和大家一起学习进步
  • 问题描述 : 目的:使用C++模板设计并逐步完善图的邻接矩阵抽象数据类型(ADT)。 内容: (1)请参照图的邻接矩阵模板类原型,设计并逐步完善图的邻接矩阵ADT。...注意:DG(有向图), DN(有向网.
  • Python语言,用邻接矩阵实现图 通过二维数组建立无向图 通过二维数组建立有向图 通过边建立有向图 为方便查看,通过NetworkX显示图。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,236
精华内容 12,094
关键字:

有向图的邻接矩阵