精华内容
下载资源
问答
  • 已知邻接矩阵求可达矩阵的MATLAB代码
  • 采用Warshall算法,从邻接矩阵求可达矩阵
  • 算法如下: #include "stdio.h" #include "stdlib.h" #include "string.h" #define MAX 10 ...void Warshell(int (*AdjMarix)[MAX],int n){//warshell算法传递闭包 int i,j; for(i=0;i<n;i++) ...

    算法如下:

    #include "stdio.h" 
    #include "stdlib.h"
    #include "string.h"
    #define MAX 10
    
    int AdjM[MAX][MAX];//全局变量
    
    void Warshell(int (*AdjMarix)[MAX],int n){//warshell算法求传递闭包
    int i,j;
    for(i=0;i<n;i++)
       for(j=0;j<n;j++)
            if(AdjMarix[i][j])
                AdjM[i][j]=1;
            else
                AdjM[i][j]=0;     
    
    
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(AdjM[j][i]==1){
                for(int k=0;k<n;k++){
                    if(AdjM[i][k])
                        AdjM[j][k]=1;
                }
            }
    
    for(i=0;i<n;i++)
        AdjM[i][i]=1;
    
    printf("可达矩阵为:\n");
    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            printf("%d  ",AdjM[i][j]);
        printf("\n");
        }
    }
    
    int Q_judge(int (*AdjM)[MAX],int n){
    int i,j;
    for(i=0;i<n;i++)
        for(j=i;j<n;j++)
            if(!(AdjM[i][j]*AdjM[j][i]))
                return 0;
    printf("强连通\n");
    return 1;
    }
    
    int D_judge(int (*AdjM)[MAX],int n){
    int i,j;
    for(i=0;i<n;i++)
        for(j=i;j<n;j++)
            if((AdjM[i][j]+AdjM[j][i])==0)
                return 0;
    printf("单向连通\n");
    return 1;
    }
    
    
    int R_judge(int (*AdjM)[MAX],int n){
    int i,j;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(AdjM[i][j])
                AdjM[j][i]=1;
    Warshell(AdjM,n);
    for(i=0;i<n;i++)
        for(j=i;j<n;j++)
            if((AdjM[i][j]*AdjM[j][i])==0)
                return 0;
    printf("弱连通\n");
    return 1;
    }
    
    int main(){
    int n;
    printf("请输入结点个数:");
    scanf("%d",&n);
    int AdjMarix[MAX][MAX];
    printf("请输入邻接矩阵:\n");
    for(int i=0;i<n;i++)
       for(int j=0;j<n;j++){
            scanf("%d",&AdjMarix[i][j]);
            AdjM[i][j]=AdjMarix[i][j];
        }
    Warshell(AdjM,n);
    if(Q_judge(AdjM,n));
    else if(D_judge(AdjM,n));
    else if(R_judge(AdjM,n));
    else printf("不连通\n");
    system("pause");
    }
    

    测试结果如下:
    测试结果

    展开全文
  • 1、邻接矩阵  将一个n个节点的图,转化成一个n*n的矩阵G,G[i][j]表示第i个节点到第j个节点的的权重。    对于上图邻接矩阵为:   2、度  度分为入度和出度:某个节点的入度就是可以通过一条边到达这个...

    一、介绍概念

     

    1、邻接矩阵

           将一个n个节点的图,转化成一个n*n的矩阵G,G[i][j]表示第i个节点到第j个节点的的权重。

          

          对于上图邻接矩阵为:

          

    2、度

          度分为入度和出度:某个节点的入度就是可以通过一条边到达这个节点的节点个数,某个节点的出度就是可以通过一条边到达其它节点的节点个数

          

         在这个图中只有3节点可以到达0节点,0节点可以到达1节点和2节点,所以0节点的入度为:1,出度为2

    3、可达矩阵:

         可达矩阵是一个n*n的矩阵rechG,如果节点i可以到达节点j,那么rechG[i][j]=1,反之,则为rechG[i][j]=0;可以采取这种计算方式:

            tmpG=G+G^{^{2}}+G^{^{3}}+\cdots +G^{^{n}}

           rechG[i][j]=\left\{\begin{matrix} 1, tmpG[i][j]!=0 & \\ 0, tmpG[i][j]==0& \end{matrix}\right.

    4、连通(有向图)

          (1)强连通:当每个节点都可以到达其它节点的时候就是强连通

          如图:(下图就是一个强连通图)

          

          (2)单向连通:只要对任意两个节点:节点i, 节点j,如果i可以到达j(条件1),或者j可以到达i(条件2),只要满足一个条件,就是单向连通图。

           如果:(下图是一个单向连通图)

          

             (3)弱连通:将有向图转化成无向图的时候,如果这个无向图是强连通,那么原图是弱连通。

               结论:单向连通图一定是弱通图,弱连通图不一定是单向连通图

               如下图:是弱连通图,单不是单向连通图

               

    二、实现思路(邻接矩阵)

    1、出度和入度

         出度邻接矩阵第i行的和(主对角线为0)就是第i个节点的出度

         入度邻接矩阵第j列的和(主对角线为0)就是第j个节点的入度

    如下是代码:graphic[i][j]是邻接矩阵:

    /*输出有序顶点对,以及每个顶点的入度和出度*/
    void display_degree()
    {
        cout << "\n每个顶点的入度和出度如下:" << endl;
        for (int i = 0; i < vernum; i++)
        {
            cout << "第" << i << "个顶点的入度和出度:";
            int intoDegree = 0;  //入度
            int outDegree = 0;   //出度
            for (int j = 0; j < vernum; j++)
            {
                if (graphic[j][i] != 0&&i!=j)
                    intoDegree++;  
                if (graphic[i][j] != 0&&i!=j)
                    outDegree++;
            }
            cout << intoDegree << "\t" << outDegree << endl;
        }
    }

    2、可达矩阵:

    可达矩阵计算方式很多,下面给出其中一种解法:rechG是计算的可达矩阵

         

            tmpG=G+G^{^{2}}+G^{^{3}}+\cdots +G^{^{n}}

           rechG[i][j]=\left\{\begin{matrix} 1, tmpG[i][j]!=0 & \\ 0, tmpG[i][j]==0& \end{matrix}\right.

    代码如下:

    /*矩阵乘法*/
    void matrix_multi(int A[][MAX],int B[][MAX])
    {
        //乘法的最后结果保存再A矩阵中
        int result[MAX][MAX];
        memset(result, 0, sizeof(result));
        for (int i = 0; i < vernum; i++)
        {
            for (int j = 0; j < vernum; j++)
            {
                for (int v = 0; v < vernum; v++)
                {
                    result[i][j] += A[i][v] * B[v][j];
                }
            }
        }
        //拷贝到A中
        for (int i = 0; i < vernum; i++)
        {
            for (int j = 0; j < vernum; j++)
            {
                A[i][j] = result[i][j];
            }
        }

    }

    /*求可达矩阵*/
    void rechable_matrix()
    {
        int tmp_matrix[MAX][MAX];   //可到达矩阵的每一项比如A^i
        for (int i = 0; i < vernum; i++)   //主对角线设置为1
            graphic[i][i] = 1;
        for (int i = 0; i < vernum; i++)
        {
            for (int j = 0; j < vernum; j++)
            {
                tmp_matrix[i][j] = graphic[i][j];
                rech_matrix[i][j] = graphic[i][j];
            }
        }
        for (int i = 1; i < vernum; i++)
        {
            for (int j = 0; j < i; j++)
            {
                matrix_multi(tmp_matrix, graphic);
            }
            //相加
            for (int m = 0; m < vernum; m++)
            {
                for (int n = 0; n < vernum; n++)
                {
                    rech_matrix[m][n] = rech_matrix[m][n] + tmp_matrix[m][n];
                }
            }
        }
        cout << "可达矩阵为:" << endl;
        for (int i = 0; i < vernum; i++)
        {
            for (int j = 0; j < vernum; j++)
            {
                if (rech_matrix[i][j] != 0)
                    cout << "1" << "\t";
                else
                    cout << "0" << "\t";
            }
            cout << endl;
        }
    }

    3、判断图的连通性

    强连通:通过上面计算的可达矩阵,如果所有元素都不为0,就是强连通

    单向连通图:如果已经判断不为强连通,计算对于所有i,j的rech_matrix[i][j]不为0(条件1)和rech_matrix[j][i]不为0(条件2),如果条件1和条件2满足其中一个条件,就是单向连通图。

    弱连通图:如果不是强连通图,将有向图变成无向图,如果无向图是强连通,那么有向图是弱连通。

    三、代码如下

    // graphics_judge.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
    //
    
    
    #include <iostream>
    using namespace std;
    #define MAX 100
    
    //邻接矩阵的变量
    int vernum;    //节点个数
    int graphic[MAX][MAX];
    int rech_matrix[MAX][MAX]; //可达矩阵
    
    /*初始化矩阵*/
    void init_graphic();
    /*输出有序顶点对,以及每个顶点的入度和出度*/
    void display_degree();
    /*矩阵乘法*/
    void matrix_multi(int A[][MAX], int B[][MAX]);
    /*求可达矩阵*/
    void rechable_matrix();
    /*判断强连通或则若连通:通过可达矩阵判断,强连通返回0,单向连通返回1,否则返回-1*/
    int judge_connected_graph();
    /*判断是否是弱连通*/
    void judge_connected_weakgraph();
    
    
    int main()
    {
    	init_graphic();
    	display_degree();
    	rechable_matrix();
    	int flag = judge_connected_graph();
    	if (flag == 0)
    	{
    		cout << "输入的图是强连通图" << endl;
    	}
    	else
    	{
    		if (flag == 1)
    			cout << "输入的图是单向连通图" << endl;
    		judge_connected_weakgraph();
    	}
    	return 0;
    }
    
    /*初始化矩阵*/
    void init_graphic()
    {
    	cout << "请输入图的节点个数:";
    	cin >> vernum;
    	cout << "请输入一个为" << vernum << "的0,1方正:" << endl;
    	for (int i = 0; i < vernum; i++)
    	{
    		for (int j = 0; j < vernum; j++)
    		{
    			cin >> graphic[i][j];
    			if (i == j)
    				graphic[i][j] = 1;
    		}
    	}
    }
    
    /*输出有序顶点对,以及每个顶点的入度和出度*/
    void display_degree()
    {
    	cout << "输出有序顶点对:" << endl;
    	for (int i = 0; i < vernum; i++)
    	{
    		for (int j = 0; j < vernum; j++)
    		{
    			if (graphic[i][j] != 0)
    			{
    				cout << "<" << i << "," << j << ">" << "\t";
    			}
    		}
    	}
    	cout << "\n每个顶点的入度和出度如下:" << endl;
    	for (int i = 0; i < vernum; i++)
    	{
    		cout << "第" << i << "个顶点的入度和出度:";
    		int intoDegree = 0;  //入度
    		int outDegree = 0;   //出度
    		for (int j = 0; j < vernum; j++)
    		{
    			if (graphic[j][i] != 0&&i!=j)
    				intoDegree++;  
    			if (graphic[i][j] != 0&&i!=j)
    				outDegree++;
    		}
    		cout << intoDegree << "\t" << outDegree << endl;
    	}
    }
    
    /*矩阵乘法*/
    void matrix_multi(int A[][MAX],int B[][MAX])
    {
    	//乘法的最后结果保存再A矩阵中
    	int result[MAX][MAX];
    	memset(result, 0, sizeof(result));
    	for (int i = 0; i < vernum; i++)
    	{
    		for (int j = 0; j < vernum; j++)
    		{
    			for (int v = 0; v < vernum; v++)
    			{
    				result[i][j] += A[i][v] * B[v][j];
    			}
    		}
    	}
    	//拷贝到A中
    	for (int i = 0; i < vernum; i++)
    	{
    		for (int j = 0; j < vernum; j++)
    		{
    			A[i][j] = result[i][j];
    		}
    	}
    
    }
    
    /*求可达矩阵*/
    void rechable_matrix()
    {
    	int tmp_matrix[MAX][MAX];   //可到达矩阵的每一项比如A^i
    	for (int i = 0; i < vernum; i++)   //主对角线设置为1
    		graphic[i][i] = 1;
    	for (int i = 0; i < vernum; i++)
    	{
    		for (int j = 0; j < vernum; j++)
    		{
    			tmp_matrix[i][j] = graphic[i][j];
    			rech_matrix[i][j] = graphic[i][j];
    		}
    	}
    	for (int i = 1; i < vernum; i++)
    	{
    		for (int j = 0; j < i; j++)
    		{
    			matrix_multi(tmp_matrix, graphic);
    		}
    		//相加
    		for (int m = 0; m < vernum; m++)
    		{
    			for (int n = 0; n < vernum; n++)
    			{
    				rech_matrix[m][n] = rech_matrix[m][n] + tmp_matrix[m][n];
    			}
    		}
    	}
    	cout << "可达矩阵为:" << endl;
    	for (int i = 0; i < vernum; i++)
    	{
    		for (int j = 0; j < vernum; j++)
    		{
    			if (rech_matrix[i][j] != 0)
    				cout << "1" << "\t";
    			else
    				cout << "0" << "\t";
    		}
    		cout << endl;
    	}
    }
    
    int judge_connected_graph()
    {
    	int flag_connected = 0;  //强连通为0,单向连通为1,否则为-1
    	/*判断强连通和单向连通*/
    	for (int i = 0; i < vernum; i++)
    	{
    		for (int j = 0; j < vernum; j++)
    		{
    			if (rech_matrix[i][j] == 0)
    				flag_connected = 1;
    		}
    	}
    	if (flag_connected == 0)
    		return 0;
    	
    	for (int i = 0; i < vernum; i++)
    	{
    		for (int j = 0; j < vernum; j++)
    		{
    			if (rech_matrix[i][j] == 0 && rech_matrix[j][i] == 0)
    				return -1;
    		}
    	}
    	return 1;
    }
    
    /*判断是否是弱连通*/
    void judge_connected_weakgraph()
    {
    	for (int i = 0; i < vernum; i++)
    	{
    		for (int j = 0; j < vernum; j++)
    		{
    			if (graphic[i][j] != 0)
    			{
    				graphic[j][i] = graphic[i][j];
    			}
    		}
    	}
    	cout << "转化成无向图后的可达矩阵为:" << endl;
    	rechable_matrix();
    	if (judge_connected_graph() == 0)
    		cout << "可以发现原图是个弱连通图" << endl;
    	else
    		cout << "可以发现原图不是一个弱连通图" << endl;
    }
    

     

     

     

     

     

     

     

     

        

     

     

    展开全文
  • matlab求可达矩阵

    2018-05-01 10:59:27
    根据MATLAB编程,由邻接矩阵求可达矩阵。 根据MATLAB编程,由邻接矩阵求可达矩阵
  • 怎样用C语言表示邻接矩阵求可达矩阵,并且判断图的连通性,急,谢谢帮忙
  • 第二邻接矩阵的2次方,3次方,…,n-1次方 第三将各个矩阵对应元素的绝对值相加,若大于0则设置为1,若为0,则为0,求得改图的可达矩阵。 第四,输出可达矩阵,观察:若除了对角线元素外不存在0,则该图为强连通...

    题目要求
    分析:
    由已经学过的知识和编程基础知识分析该题:
    第一获取用户输入的邻接矩阵,判定是否输入错误(n*n平方阶的个数为正确输入)
    第二求该邻接矩阵的2次方,3次方,…,n-1次方
    第三将各个矩阵对应元素的绝对值相加,若大于0则设置为1,若为0,则为0,求得改图的可达矩阵。
    第四,输出可达矩阵,观察:若除了对角线元素外不存在0,则该图为强连通图,否则不是强连通图。
    对于第一个问题,可以利用数组来存。为了方便用户,我用了字符数组来存取,后期会将字符数组转变为对应的整型二维数组。
    第二个问题用矩阵相乘来解决。并另创建1个数组,存储对应元素的和,为后期做准备.
    第三问题,将上述数组转变成可达矩阵,并输出
    观察可达矩阵,并给出判定
    样例输入与输出如下:
    当我输入三个变量时:(输入错误)
    在这里插入图片描述
    当输入一个强连通图的邻接矩阵时:
    在这里插入图片描述
    当输入一个不是强连通图的邻接矩阵时:
    在这里插入图片描述

    附:源代码如下:
    /*****************
    **** 名称:离散数学实验作业:给出图的邻接矩阵判定此图是否为强连通图 
    **** 时间:2018/12/22
    **** 作者:知非0802
    ******************/ 
    #include <iostream>
    #include <iomanip>
    #include <cmath>
    #define Size 100
    using namespace std;
    int main(){
    	char ch[Size];
    	int i,j,k,h,n=1,count=0,elem=0;
    	cout<<"请输入该图形的邻接矩阵: (只输入数字即可)"<<endl;//获得用户输入的邻接矩阵 
    	gets(ch);
    	for(i=0;ch[i] != '\0';i++){
    		if(ch[i] !=' ')
    		count++;
    	}
    	do{
    		if(count == pow(n,2))
    			break;
    		else
    			n++;
    		if(n==10)
    			cout<<"你输入的数据有误,请重新输入!"<<endl;//邻接矩阵必须为 n*n 的形式,否则为输入错误! 
    	}while(1);
    	cout<<"该图形的邻接矩阵是:"<<endl;
    	for(i=0,count=0;ch[i]!='\0';i++){
    		if(ch[i] != ' '){
    			cout<<setw(4)<<ch[i];
    			count++;
    		}
    		if(count!=0&&count%n==0){
    			cout<<"\n";
    		}	
    	}
    	int ch1[n][n];//建立二维数组 
    	int ch2[n][n];
    	int ch3[n][n];
    	int ch4[n][n];
    	count = 0; 
    	for(i=0,j=0,k=0;ch[k]!='\0';k++,j++){//将刚刚的一维数组转换为二维数组 
    		ch1[i][j] =(int) (ch[k]-'0');
    		if(j == n-1){
    			i++;
    			j=-1;
    		}		
    	}
    	for(i=0;i<n;i++)
    		for(j=0;j<n;j++)
    			ch2[i][j]=ch1[i][j];//建立一个和 ch1 长得一样的二维数组 ch2
    	for(i=0;i<n;i++)
    		for(j=0;j<n;j++)
    			ch3[i][j]=ch1[i][j];//建立一个和 ch1 长得一样的二维数组 ch3 
    	for(h=1;h<n;h++){
    		for(i=0;i<n;i++){
    			for(j=0;j<n;j++){
    				elem = 0;
    				for(k=0;k<n;k++){
    					elem += ch3[i][k]*ch1[k][j];
    						if(k==n-1){
    							ch4[i][count] = elem;
    							ch2[i][count] += abs(elem);
    							count++;
    							if(count == n ){
    								count = 0;
    									}
    									}
    								}
    							}
    						}
    				for(i=0;i<n;i++)
    					for(j=0;j<n;j++)
    						ch3[i][j]=ch4[i][j];
    		}
    	for(i=0;i<n;i++)
    		for(j=0;j<n;j++){
    			if(ch2[i][j])
    				ch2[i][j]=1;
    			else
    				ch2[i][j]=0;
    			if(i==j)
    				ch2[i][j]=1;
    		}
    		cout<<"该图形的 可达 矩阵是:"<<endl;
    			for(i=0,count=0;count<n*n;i++)
    				for(j=0;j<n;j++){
    					cout<<setw(4)<<ch2[i][j];
    					count++;
    					
    					if(count!=0&&count%n==0)
    					cout<<"\n";
    					}
    		for(i=0;i<n;i++){
    			for(j=0;j<n;j++){
    				if(!ch2[i][j]){
    					cout<<"由此图的可达矩阵可知:\n   除了对角线上元素,还存在零元素在矩阵里面,因此判定: 此图为不是强连通图!";
    					return 0;
    					}
    			}
    	}
    	cout<<"由此图的可达矩阵可知:\n   不存在零元素在矩阵里面,因此判定:   此图为强连通图!" ;
    	return 0;
    }
    
    
    展开全文
  • ​ 树的结构体(一般使用链式): 前序遍历递归实现 递归实现树的高度 图的存储结构struct(邻接矩阵) 图的邻接表Struct,邻接:Adjacency 栈(stack)的基本操作 s.push(int x),s.pop( ): 队列基本操作 list: ...

     

     

    目录

    线性表结构体(“->”和“.”的区别);

    树的结构体

    前序遍历递归

    递归实现求树的高度

     

    图的邻接矩阵

    图的邻接表

    dfs判断顶点i 顶点 j是否可达

    队列

    list:

     


    线性表结构体(“->”和“.”的区别);


    1.顺序线性表 (也就是用数组实现的,在内存中有顺序排列,通过改变数组大小实现

    SqList:顺序存储的线性表;

    LinkList:链式存储线性表;

     

    typedef struct SqList
    {
     ememtype *elem  //指针数组
     int length;       
    }SqList;

     

    使用

    void demo(SqList &L){
    L.elem[i];
    L.length;
    }
    
    //对于指针数组构成的结构体使用:参数&L;调用只能是用“点 .”
    //若参数(LinkLIst *L)掉用:L->length;L->next;

    指针指向一维数组

    指针可以 指向任意。指针本身就是一个地址,

    上边的类似这个

    1. int array[5] = {1, 2, 3, 4, 5}; // 定义数组

    2. int *intptr = array; // 定义指向数组元素的指针

    3. cout<<intptr[1]<<endl;

    看下地址打印,指针仅仅只向数组的头部;数组是连续存储;


    2.链表 (不是用顺序实现的,用指针实现,在内存中不连续)

    ElemType在c中使用

    ElemType:在C语言数据结构中,关于数据元素的类型定义均用“ ElemType e;”来表示,其中e是表示数据元素的变量,而ElemType则是它的类型,ElemType的含义就是“数据元素的类型”,是一个抽象的概念,是表示我们所要使用的数据元素应有的类型。

    elemtype在VC中没有这种类型,所以在使用它之前对其定义如 typedef int ElemType将ElemType定义为整型的数据类型;

    在类C语言中直接使用ElemType

    结构体别名LNode和*LinkList区别;

    LNode就是结构体大小,由系统开辟空间;

    *LinkList 就是指针大小,指向LNode的地址;

    代码 :

    • *LinkList,LNode;:在使用是注意LinkList已经是指针不用在声明指针;  
    • LinkList作为整体,不在声明指针,直接使用:LinkList L;  LNode *p;

     

    #include <iostream>
    
    #include <stdlib.h>
    
    using namespace std;
    
    int prime(int n);
    
    typedef struct LNode {
    
    int data;
    
    LNode *next;
    
    }*LinkList,LNode;
    
    
    int main() {
    
    L1 l1;
    
    LinkList l2;
    
    l2=(L1 *)malloc(sizeof(L1));
    
    cout<<l1.data<<endl;
    
    cout<<sizeof(*l2)<<endl;
    
    return 0;
    
    }

     

     

    直接输出l1失败,因为这是结构体,直接输出结构体是不对,可以输出结构体数据

     

    我们可以看下他们的大小,指针大小就是8,分别是自己地址4和存储地址4,

    LNode就是结构体大小16 和*LinkList 就是指针大小8(但是这个指针类型是LNode,指向的是LNode);

     

    给l2分配空间,输出大小

     

    我们看l1 数据,这里 没分配是脏数据;这个要注意

    c++ new关键字;

    new关键字是c++有的,在c里面返回的是一个指针指向new的这个结构体;这个和java不同

     

    树的结构体

    (一般使用链式):

    typedef struct BiNode
    
    { int value;
    
    BiNode * left;
    
    BiNode * right;
    
    }*BiTree;

     

    前序遍历递归

    void preOrder(BiNode *node){
        if(node){
            cout<<node->value;
            preOrder(node->left);
            preOrder(node->right);
        }
    
    }

    递归实现求树的高度

    这里面关键在于 return (ab)?a+1:b+1;

    int GetHeight(Node A)
    
    {
    
    int a, b;
    
    if(A) {
    
    HL = GetHeight(A->Left);
    
    HR = GetHeight(A->Right);
    
    return (ab)?a+1:b+1;
    
    }
    
    return 0;
    
    }

     

    看图中每个阶段中ab值,你就理解递归了;

     

    图的邻接矩阵

    
    typedef struct {
        char info;        /* 顶点表信息(村庄名称)*/
        int no;               /*顶点编号(1或A)*/
    } VertexType;
    
    typedef struct {
        VertexType vexs[MAXVEX];        /* 顶点表 数组*/
        int edge[MAXVEX][MAXVEX];   /* 邻接矩阵 */
        int n, e;               /*定点的个数和边的个数*/
    } MGraph;
    //MGraph 中 M含义:矩阵 matrix;

     

     

    图的邻接表

    邻接:Adjacency 简称:adj

    
    #define MaxSize 10
    typedef struct EdgeNode
    {
    	int weight;
        int adjvex;  // 边节点 的 编号,同顶点编号
    	EdgeNode *next;
    }ArcNode;//表边节点   Arc:弧
    typedef struct VertexNode{
    	char data;
    	EdgeNode *first;
    }verNode;//表顶点
    
    typedef struct {
    	VertexNode adjList[MaxSize];
    	int v, e;
    }adjGraph;
    void creatAdjGraph(adjGraph *a);//创建邻接表
    void print(adjGraph *a);//遍历邻接表
    

    dfs判断顶点i 顶点 j是否可达

     

    s.pushint x),s.pop( )

    #include <iostream>
    #include <stack>
    
    using namespace std;
    int main() {
    	stack <int > q;
    	q.push(1);
    	q.push(2);
    	int a =q.top();
    	cout << "Hello, world!"<<a << endl;
    	return 0;
    }

    stack<int> s1;
    stack<string> s2;

    empty() 堆栈为空则返回真

    pop() 移除栈顶元素

    push() 在栈顶增加元素

    size() 返回栈中元素数目

    top() 返回栈顶元素

     

    typedef struct
    {
    SElemType *top;
    SElemType *base;
    SElemType stacksize;
    }SqStack;

    SqStack  s;

    s.IsEmpty;//判断空

    出栈操作。(若栈不为空,则删除栈顶元素,并用e2返回其值) s.Pop(SqStack s,SElemType e)

    压栈操作。 s.Push(SqStack s,SElemType e)

    队列

    EnQueue,Deueue;入队列,出队列(优先队列:按优先级别执行)

    //2.链循环队列(头结点为空)
    #include<stdio.h>
    #include<stdlib.h>
     
    typedef struct QNode{
        int data;
        struct QNode *next;
    }QNode,*LinkQueue;

     
    LinkQueue rear,head;//尾指针和头结点,这里没有用front而是head,因为这里的头结点不是动态的,而是固定的,用head以区分顺序循环队列的front
     
    int EnQueue(int e)//入队列 
    {
        LinkQueue p;
        p=(LinkQueue)malloc(sizeof(QNode));
        p->data=e;
        rear->next=p;
        rear=p;
        rear->next=head;     

    }

    queue<int> q1;
    queue<double> q2;

    queue 的基本操作有:

    #include <iostream>
    #include <queue>
    
    using namespace std;
    int main() {
    	queue <int > q;
    	q.push(1);
    	q.push(2);
    	cout <<q.back() << endl;
    	cout <<q.front() << endl;
    	cout << "Hello, world!" << endl;
    	return 0;
    }


    入队,如例:q.push(x); 将x 接到队列的末端。
    出队,如例:q.pop(); 弹出队列的第一个元素,注意,并不会返回被弹出元素的值。
    访问队首元素,如例:q.front(),即最早被压入队列的元素。
    访问队尾元素,如例:q.back(),即最后被压入队列的元素。
    判断队列空,如例:q.empty(),当队列空时,返回true。
    访问队列中的元素个数,如例:q.size()

    list:

    Lists将元素按顺序储存在链表中. 与 向量(vectors)相比, 它允许快速的插入和删除,但是随机访问却比较慢.

    #include <iostream>
    #include <list>
    
    using namespace std;
    int main() {
    	list <int > q;
    	q.push_back(1);
    	q.push_back(2);
    	int a =11;
    	q.insert(q.begin(),111); 
    	cout<<q.front();
    	return 0;
    }
    


    assign() 给list赋值 
    begin() 返回指向第一个元素的迭代器 
    clear() 删除所有元素 
    empty() 如果list是空的则返回true 
    end() 返回末尾的迭代器 
    erase() 删除一个元素 
    front() 返回第一个元素 ,back() 返回最后一个元素 
    insert() 插入一个元素到list中 
    max_size() 返回list能容纳的最大元素数量 
    merge() 合并两个list 


    pop_back() 删除最后一个元素 
    pop_front() 删除第一个元素 


    push_back() 在list的末尾添加一个元素 
    push_front() 在list的头部添加一个元素 


    rbegin() 返回指向第一个元素的逆向迭代器 
    remove() 从list删除元素 
    remove_if() 按指定条件删除元素 
    rend() 指向list末尾的逆向迭代器 
    resize() 改变list的大小 
    reverse() 把list的元素倒转 
    size() 返回list中的元素个数 
    sort() 给list排序 
    splice() 合并两个list 
    swap() 交换两个list 
    unique() 删除list中重复的元素

     

    栈和队列头文件:

    #include <stack>

    #include<queue>

    栈:

    stack<int>  curStack;  //栈定义

    操作:

    curStack.empty()      如果栈为空返回true,否则返回false;

    curStack.size()        返回栈内元素的大小;

    curStack.pop()       从栈顶弹出一个成员;

    curStack.push()       向栈内压入一个成员;

    curStack.top()         返回栈顶,但不删除成员;

    队列:

    queue<int> curQueue;    //队列定义

    操作:

    curQueue.empty()      如果队列为空返回true,否则返回false;

    curQueue.size()        返回队列内元素的大小;

    curQueue.pop()       从队列弹出一个成员;

    curQueue.push()       向队列压入一个成员;

    curQueue.front()       返回到队首,但不删除成员;

    curQueue.back()       返回到队尾,但不删除成员;

    堆、栈、队列之间的区别是?

    ①堆是在程序运行时,而不是在程序编译时,申请某个大小的内存空间。即动态分配内存,对其访问和对一般内存的访问没有区别。

    ②栈就是一个桶,后放进去的先拿出来,它下面本来有的东西要等它出来之后才能出来。(后进先出)

    ③队列只能在队头做删除操作,在队尾做插入操作.而栈只能在栈顶做插入和删除操作。(先进先出)

    展开全文
  • 来源:王海英. 图论算法及其MATLAB实现. 北京: 北京航天航空大学出版社,... (1) 出 (2) 将矩阵中不为0的元素改为1,为0的元素不变 (3) = 算法实现: 根据邻接计算有向图的可达矩阵的算法及其MATLAB实现funct...
  • C/C++ 根据有向图、无向图求邻接矩阵的通路、回路,和对应的可达矩阵
  • 邻接矩阵A 单位矩阵 I A+I 的表示 可达矩阵计算 程序代码为 n size(S,1; p S; for i 2:n p p+S^i; end p(p~ 0) 1; P 即为所可达矩阵
  • 图论学习笔记——可达矩阵

    千次阅读 2020-05-06 16:09:47
    一般地,设n阶有向图D的邻接矩阵为A,有A可得到图D的可达矩阵,不妨设为P,其步骤如下: 1、出 2、把矩阵中不为0的元素给为1,而为0的元素不变 这样所改换的矩阵就位图D的可达矩阵P。 (A表示图的邻...
  • 设A为n阶有向图的邻接矩阵出Bn=A+A2+⋅⋅⋅+An 然后把矩阵Bn的不为0的数变为1,为0的数不变 MATLAB实现 function P = dgraf(A) n = size(A,1); P = A; for i = 2 : n P = P + A^i; end P(P ~= 0) = 1; 测试 ...
  • ISM C语言精简版

    2010-09-11 23:31:17
    根据邻接矩阵求可达矩阵,再求可达结合和先行集合及交集。
  • Floyd-Warshall算法求矩阵的传递闭包

    千次阅读 2017-07-20 16:01:58
    有向图的传递闭包表示从邻接矩阵A出发,的所有节点间的路径可达情况int vis[N][N];//邻接矩阵,vis[i][j]=1表示i到j可达; void warshall(int x,int y) //warshall算法实现过程; { for(int i = 0; i ; i++) vis[x...
  • 提出了不确定状态转移系统的超图、超图的邻接矩阵和可达矩阵等概念,设计了用超图的邻接矩阵求不确定状态转移系统中状态之间可达关系的方法.利用不确定状态转移系统的超图、超图的邻接矩阵和状态之间的可达关系获得了...
  • ISM 解析机构模型

    2010-08-30 20:44:01
    ISM 以邻接矩阵求可达矩阵的全部过程,每个步骤的结果都输出来了,其中我犯的每个错误,都用注释解释其中的原因及如何改正的。希望对你有用!
  • 图的顶点可达闭包

    千次阅读 2018-11-13 21:32:34
    A的可达闭包矩阵A*,其元素定义为:若存在顶点i到顶点j的有向路径则A*[i,j]=1,若没有有向路径则A*[i,j]= 0。 输入 第1行顶点个数n 第2行开始的n行有向图的邻接矩阵,元素之间由空格分开 输出 有向图的可达...
  • 以非循环可达关系为基础, 定义矩阵的计算规则, 使用系统的邻接矩阵来计算可达矩阵。同时首次提出了循环可达关系的分类、二可达关系等, 并设计了循环可达关系的算法, 且以实例证明了算法的有效性和正确性。在不确定...
  • A的可达闭包矩阵A*,其元素定义为:若存在顶点i到顶点j的有向路径则A*[i,j]=1,若没有有向路径则A*[i,j]= 0。 输入 第1行顶点个数n 第2行开始的n行有向图的邻接矩阵,元素之间由空格分开 输出 有向图的可达闭包...
  • 思路离散数学里面学的嘛,可达矩阵的k次方就是走k步时的可达矩阵,然后就转化成计算A+A2...AmA+A^2...A^m 然后想到了POJ的那个经典题目,通过对m二分来,然后疯狂TLE= =(一个log都不能多吗。。。 最后想到了...
  • A的可达闭包矩阵A*,其元素定义为:若存在顶点i到顶点j的有向路径则A*[i,j]=1,若没有有向路径则A*[i,j]= 0。 输入 第1行顶点个数n 第2行开始的n行有向图的邻接矩阵,元素之间由空格分开 输出 有向图的可
  • Hdu 2254 奥运 (矩阵)

    2013-09-24 22:56:00
    题意:给出n条道路,k个询问,每个询问包括起点v1、终点v2、t1天、t2天 从v1到v2走了i天一共有多少走法(mod 2008)?...设图的可达矩阵为a,则答案为a^t1+a^(t1+1)……+a^t2。 本题数据范围太大,需要离散化
  • Washall算法

    2020-05-25 16:00:59
    问题引出:在一个图结构中,常常需要找两个节点之间有没有一条通路(通路长任意),也就是任意两点之间的可达情况,我们很自然会联想到用邻接矩阵求可达矩阵,从而得出两点之间的可达情况。 如: 在这个图中,...
  • cout原矩阵的可达矩阵为:"; for(i=1;i;i++){ for(j=1;j;j++){ if(c[i][j]!=0)c[i][j]=1; cout[i][j]; } cout; } } } } return 0; } void Warshall(){ for(int ii=1;ii;...
  • # M 代表两个顶点不可达 M = 1e20 def generate_matrix(node_cnt=0, array=[]) -> list: """ 根据输入生成带权邻接矩阵 :param node_cnt: 节点数 :param array: 输入数组,每个元素格式为(节点,节点,权重...
  • 顶点个数n,以及n*n的邻接矩阵,其中不可达使用9999代替 【输出形式】 每两个顶点之间的最短路径和经过的顶点 注意:顶点自身到自身的dist值为0,path则为该顶点的编号 【样例输入】 4 9999 4 11 9999 6 9999 2 9999...

空空如也

空空如也

1 2 3 4
收藏数 68
精华内容 27
关键字:

邻接矩阵求可达矩阵