精华内容
下载资源
问答
  • 关联矩阵

    2021-04-24 14:09:17
    一、题目:算法训练 关联矩阵 问题描述  有一个n个结点m条边的有向图,请输出他的关联矩阵。 输入格式 第一行两个整数n、m,表示图中结点和边的数目。n<=100,m<=1000。 接下来m行,每行两个整数a、b,表示...

    一、题目:算法训练 关联矩阵

    • 问题描述
        有一个n个结点m条边的有向图,请输出他的关联矩阵。

    输入格式

    第一行两个整数n、m,表示图中结点和边的数目。n<=100,m<=1000。

    接下来m行,每行两个整数a、b,表示图中有(a,b)边。

    注意图中可能含有重边,但不会有自环。

    输出格式

    输出该图的关联矩阵,注意请勿改变边和结点的顺序。

    样例输入

    5 9

    1 2

    3 1

    1 5

    2 5

    2 3

    2 3

    3 2

    4 3

    5 4

    样例输出

    1 -1 1 0 0 0 0 0 0

    -1 0 0 1 1 1 -1 0 0

    0 1 0 0 -1 -1 1 -1 0

    0 0 0 0 0 0 0 1 -1

    0 0 -1 -1 0 0 0 0 1

    二、代码与思路

    1、代码

    /*关联矩阵*/
    import java.util.Scanner;
    /**
     * @author GBL
     *
     */
    public class Main{
    	public static void main(String[] args) {
    		Scanner input=new Scanner(System.in);   //创建一个输入流
    		int n=input.nextInt();//从键盘中输入有向图的总的点数
    		int m=input.nextInt();//从键盘中输入有向图的总的边数
    		int str[][]=new int[m][2];//创建一个二维数组用于村存储有向图的边
    		for(int i=0;i<m;i++)//有for循环输入有向图的边
    			for(int j=0;j<2;j++)
    				str[i][j]=input.nextInt();
    		input.close();//关闭输入流
    		
    		/****两重循环外层表示行,内层表示列***/
    		for(int i=0;i<n;i++) {
    			for(int j=0;j<m;j++)
    			{	
    				/****如果当前点与某一条边有联系则输出1或-1***/
    				/****如果当前点与某一条边没有联系则输出0*****/
    				if(i+1==str[j][0])
    					System.out.print(" 1");
    				else if(i+1==str[j][1])
    					System.out.print(" -1");
    				else 
    					System.out.print(" 0");
    			}
    			System.out.println();//每行结束也就是内层循环结束输出回车,从新的一行开始输出
    		}			
    	}
    }
    

    2、思路

    • 输入部分就输入顶点数和边的的数量,并将组合成每条边的两个顶点存储在二维数组中,通过循环判断每个顶点与边的关系,最输出他的关联矩阵。

    三、个人总结

    • 首先了解到了什么是关联矩阵:关联矩阵,虽然经过对比输出的数据和正确答案一摸一样,但在蓝桥的测试系统中一直无法通过。
    展开全文
  • //关联矩阵 int A1[30][30] = { 0 };//输出矩阵 int A2[30][30] = { 0 };//输入矩阵 //可达图节点 typedef struct Node { int m[30] = { 0 };//标识 int flag = 0;//新0,旧1,端点2 int isfirable[30] = { 0 };...

    会产生状态空间爆炸,后续需要约减。

    #include <stdio.h>
    #include "tinyxml.h"
    #include <iostream>
    #include <cstring>
    #include<string>
    #include<vector>
    #include <stdlib.h>
    #include<fstream>
    using namespace std;
    
    struct Arc {
    	string id;
    	string source;
    	string target;
    	int sourceNum = 0;
    	int sourceP = 0;//源节点是库所,则sourceP为1
    	int sourceT = 0;
    	int targetNum = 0;
    };
    
    //库所顶点表
    typedef struct Place
    {
    	string name;
    	int num = 0;
    	int initialMarking = 0;
    };
    
    //变迁顶点表
    typedef struct Transition
    {
    	string name;
    	int num = 0;
    };
    int m = 0;
    int n = 0;
    int arcnum = 0;
    Place place[30];
    Transition transition[30];
    Arc arc[1000];
    int A[30][30] = { 0 };//关联矩阵
    int A1[30][30] = { 0 };//输出矩阵
    int A2[30][30] = { 0 };//输入矩阵
    
    //可达图节点
    typedef struct Node {
    	int m[30] = { 0 };//标识
    	int flag = 0;//新0,旧1,端点2
    	int isfirable[30] = { 0 };//存储可以发生的变迁名字
    	struct Node *parent;//该节点的父节点
    	int t = 0;//存储生成这个节点所发生的变迁名字
    };
    
    void readPNML() {
    	TiXmlDocument mydoc("E:\\1model.pnml");
    	bool loadOK = mydoc.LoadFile();
    	if (!loadOK) {
    		cout << "could not load the test file" << endl;
    		exit(1);
    	}
    	TiXmlElement *pnmlElement = mydoc.RootElement();
    	TiXmlElement *netElement = pnmlElement->FirstChildElement();
    	TiXmlElement *pageElement = netElement->FirstChildElement("page");
    	for (TiXmlElement *petriElement = pageElement->FirstChildElement();//第一个子元素
    		petriElement;
    		petriElement = petriElement->NextSiblingElement())
    	{
    		if (petriElement->ValueTStr() == "place") {
    			place[m].num = m;
    			if (petriElement->FirstChildElement("initialMarking")) {
    				TiXmlElement *initialMarkingElement = petriElement->FirstChildElement("initialMarking")->FirstChildElement("text");
    				place[m].initialMarking = atoi(initialMarkingElement->GetText());
    			}
    			TiXmlElement *nameElement = petriElement->FirstChildElement("name")->FirstChildElement("text");
    			place[m].name = nameElement->GetText();
    			m++;
    		}
    		if (petriElement->ValueTStr() == "transition") {
    			transition[n].num = n;
    			TiXmlElement *tnameElement = petriElement->FirstChildElement("name")->FirstChildElement("text");
    			transition[n].name = tnameElement->GetText();
    			n++;
    		}
    		if (petriElement->ValueTStr() == "arc") {
    			TiXmlAttribute *arcAttr = petriElement->FirstAttribute();
    			arc[arcnum].id = arcAttr->Value();
    			arcAttr = arcAttr->Next();
    			arc[arcnum].source = arcAttr->Value();
    			arcAttr = arcAttr->Next();
    			arc[arcnum].target = arcAttr->Value();
    			arcnum++;
    		}
    	}
    	for (int i = 0; i < arcnum; i++) {//对于每一条弧
    		for (int j = 0; j < n; j++) {//和变迁比
    			if (arc[i].source.compare(transition[j].name) == 0) {
    				arc[i].sourceT = 1;
    				arc[i].sourceNum = transition[j].num;
    			}
    			if (arc[i].target.compare(transition[j].name) == 0) {
    				arc[i].targetNum = j;
    			}
    		}
    		for (int k = 0; k < m; k++) {//和库所比
    			if (arc[i].source.compare(place[k].name) == 0) {
    				arc[i].sourceP = 1;
    				arc[i].sourceNum = place[k].num;
    			}
    			if (arc[i].target.compare(place[k].name) == 0) {
    				arc[i].targetNum = k;
    			}
    		}
    	}
    }
    
    void getA() {
    	for (int i = 0; i < arcnum; i++) {
    		if (arc[i].sourceP == 1) {
    			A[arc[i].targetNum][arc[i].sourceNum]--;
    			A2[arc[i].targetNum][arc[i].sourceNum]++;//输入矩阵
    		}
    
    		if (arc[i].sourceT == 1) {
    			A[arc[i].sourceNum][arc[i].targetNum]++;
    			A1[arc[i].sourceNum][arc[i].targetNum]++;//输出矩阵
    		}
    	}
    }
    
    void printA() {
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++) {
    			cout << A[i][j] << "  ";
    		}
    		cout << endl;
    	}
    }
    
    void printA1() {
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++) {
    			cout << A1[i][j] << "  ";
    		}
    		cout << endl;
    	}
    }
    
    void printA2() {
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++) {
    			cout << A2[i][j] << "  ";
    		}
    		cout << endl;
    	}
    }
    
    //可达图中的边表
    typedef struct RGEdge {
    	int t;//有向边代表的发生的变迁编号
    	int target;//该有向边目标节点的状态编号
    	struct RGEdge *nextedge = NULL;//该边指向的下一条边
    }RGEdge, *PRGEdge;
    
    //可达图中的顶点表
    typedef struct RGNode {
    	int m[100];//该状态存储的标识信息
    	int flag = 0;//新0,旧1
    	int isfirable[100] = { 0 };//从该标识出发可以发生的变迁名字
    	int enableNum = 0;//该标识可以发生的变迁数目
    	int t = 0;//存储生成这个节点所发生的变迁名字
    	PRGEdge firstEdge;
    }RGNode, *PRGNode;
    
    //可达图
    typedef struct RG {
    	int node = 0;
    	int edge = 0;
    	RGNode rgnode[300];//假设有300个标识
    }RG, *PRG;
    
    int M0[100] = { 0 };
    int M1[100] = { 0 };
    int M[100] = { 0 };
    void ReachabilityTree() {
    	RG graph;
    	//新建一个可达图,初始状态,可达图中节点个数为0
    	graph.node = 0;
    	//可达图的第一个节点(一个节点:初始标识)
    	for (int i = 0; i < m; i++) {
    		M0[i] = place[i].initialMarking;
    		graph.rgnode[0].m[i] = M0[i];
    	}
    	graph.node++;
    	//判断结点列表中还存在没有标记的节点
    	int newNode;
    	int exist;
    	while (1) {
    		for (int i = 0; i < graph.node; i++) {
    			exist = 0;
    			if (graph.rgnode[i].flag == 0) {//找到标识为新的节点
    				exist = 1;
    				newNode = i;
    				break;
    			}
    		}
    		if (exist != 1) {//不存在标识为新的节点
    			break;
    		}
    		//任选标识为新的节点newNode,设为M
    		for (int i = 0; i < m; i++) {
    			M[i] = graph.rgnode[newNode].m[i];
    		}
    		//标记这个节点
    		graph.rgnode[newNode].flag = 1;
    
    		//if 在M下所有变迁都不能发生
    		int enable;
    		int enableNumber = 0;
    		for (int i = 0; i < n; i++) {//对于所有的变迁
    			enable = -1;
    			for (int j = 0; j < m; j++) {
    				if (M[j] < A2[i][j]) {//变迁ti不能发生
    					enable = 0;
    					break;
    				}
    			}
    			//变迁从t0开始编号
    			if (enable == -1) {//变迁ti可以发生
    				graph.rgnode[newNode].isfirable[enableNumber] = i;
    				graph.rgnode[newNode].enableNum++;
    				enableNumber++;
    			}
    		}
    		if (graph.rgnode[newNode].enableNum == 0) {//如果变迁不能发生则跳出本次循环
    			continue;
    		}
    		//对于每个在M下可发生的变迁
    		for (int i = 0; i < graph.rgnode[newNode].enableNum; i++) {
    			//可发生变迁ti的编号i为hang
    			//计算M1
    			for (int j = 0; j < m; j++) {
    				int hang = graph.rgnode[newNode].isfirable[i];
    				M1[j] = M[j] + A[hang][j];
    			}
    			//if结点列表中出现过M1
    			int repeated;
    			int ii;
    			int exist = 0;
    			for (ii = 0; ii < graph.node; ii++) {
    				repeated = 1;
    				for (int jj = 0; jj < m; jj++) {
    					if (M1[jj] != graph.rgnode[ii].m[jj]) {
    						repeated = 0;
    						break;
    					}
    				}
    				//若结点列表出现过M1
    				if (repeated == 1) {
    					exist = 1;
    					//ii是重复的节点的序号
    					PRGEdge pEdge;
    					pEdge = new RGEdge;
    					pEdge->nextedge = NULL;
    					pEdge->t = graph.rgnode[newNode].isfirable[i];
    					pEdge->target = ii;
    					RGNode *p;
    					p = &graph.rgnode[newNode];
    					pEdge->nextedge = p->firstEdge;
    					p->firstEdge = pEdge;
    					break;
    				}
    			}
    			//若M1是没有出现过的新状态
    			if (exist == 0) {
    				//则引入新节点rgnode[graph.node],即M1。
    				for (int i = 0; i < m; i++) {
    					graph.rgnode[graph.node].m[i] = M1[i];
    				}
    				graph.rgnode[graph.node].flag = 0;
    				graph.rgnode[graph.node].t = graph.rgnode[newNode].isfirable[i];
    				//并把新节点加到邻接表边表上
    				//bug这部分的连接有问题
    				RGNode *p;
    				PRGEdge pEdge;
    				pEdge = new RGEdge;
    				pEdge->nextedge = NULL;
    				pEdge->t = graph.rgnode[newNode].isfirable[i];
    				pEdge->target = graph.node;
    				p = &graph.rgnode[newNode];
    				pEdge->nextedge = p->firstEdge;
    				p->firstEdge = pEdge;
    				graph.node++;
    			}
    		}
    	}
    	//打印可达图
    	cout << "可达图节点个数" << graph.node << endl;
    	for (int i = 0; i < graph.node; i++) {
    		cout << "M[" << i << "]" << "(";
    		for (int j = 0; j < m; j++) {
    			cout << graph.rgnode[i].m[j] << " ";
    		}
    		cout << ")";
    		PRGEdge p;
    		p = graph.rgnode[i].firstEdge;
    		for (int k = 0; k < graph.rgnode[i].enableNum; k++) {
    			cout << "[t";
    			cout << p->t;
    			cout << "M";
    			cout << p->target;
    			cout << ",";
    			p = p->nextedge;
    		}
    		cout << endl;
    	}
    
    	
    }
    
    
    int main() {
    	readPNML();//读取pnml文档信息
    	getA();//生成关联矩阵
    	printA();//打印关联矩阵
    //	printA1();//打印输出矩阵
    //	printA2();//打印输入矩阵
    	
    	ReachabilityTree();//生成可达树
    //	cout << "生成的可达树为" << endl;
    	//	PrintReachabilityTree();//打印可达树
    	system("pause");
    	return 0;
    }

    最后祝妈妈生日快乐啦~~~~啦啦啦~~~

    展开全文
  • 卷积可以通过im2col转化为矩阵乘。 而矩阵乘法,结果矩阵中的每个元素是等长度的一行与一列向量乘再累加求结果。 因此核心的矩阵算法如下: float test(float* a, float* b, int n) { float c = 0; for(int i=...

    卷积可以通过im2col转化为矩阵乘。

    而矩阵乘法,结果矩阵中的每个元素是等长度的一行与一列向量乘再累加求结果。

    因此核心的矩阵算法如下:

    float test(float* a, float* b, int n)
    {
    	float c = 0;
    	for(int i=0; i<n; i++)
    	{
    		c += (*a++) * (*b++);
    	}
    	return c;
    }

    这段代码,如果手工优化,无非是循环展开等等...不过现代编译器的优化了得,在使用-ffast-math-ftree-vectorize优化选项后,编译器也能做到循环展开和向量化(使用SIMD)指令,如下是上述代码用g++ -S 生成的汇编代码

    _Z4testPfS_i:
    	subs	w8, w2, #1  // w8 = n-1, if w8 < 0, return 0
    	b.lt	.LBB0_3
    
    	add	x8, x8, #1 // x8+1 
    	cmp		x8, #7 
    	fmov	s0, wzr
    	b.hi	.LBB0_4 // 如果数量超过8个,走循环
    
    	mov	 w8, wzr
    	b	.LBB0_8 // 跳转到尾巴处, 处理尾巴
    	
    .LBB0_3:
    	mov	 w0, wzr
    	ret
    	
    .LBB0_4:
    	and	w9, w2, #0x7    // w9 = w2 & 0x7, 循环展开
    	sub	x8, x8, x9 // 计算i的下标
    	cbz	x8, .LBB0_8
    	
    	lsl	x13, x8, #2 // 根据i的下标计算偏移量,x13存放的是float的地址偏移量 左移2位,因为float是4B
    	add	x10, x1, #16 // x1是b的地址, 不明白+16是何用意,x10是本次首地址
    	add	x11, x0, #16 // x0是a的地址, 不明白+16是何用意,x11是本次首地址
    	movi v0.2d, #0000000000000000 // 2个long等于4个float,赋值为0
    	
    	mov	 x12, x8
    	
    	add	 x0, x0, x13 // a的下一个地址
    	add	 x1, x1, x13 // b的下一个地址
    	movi v1.2d, #0000000000000000 // 2个long等于4个float,赋值为0
    	
    .LBB0_6:
    	ldp	q2, q3, [x11, #-16] // 从x11-16的地址取8个float,放在q2和q3 中
    	ldp	q4, q5, [x10, #-16] // 从x11-16的地址取8个float,放在q2和q3 中
    	
    	add	x10, x10, #32           // =32 // x10向上走8个float
    	sub	x12, x12, #8            // =8 // 下标i减8
    	add	x11, x11, #32           // =32 // x11向上走8个float
    	fmla	v0.4s, v2.4s, v4.4s // 0 = 2 + 4 + 0,向量累加
    	fmla	v1.4s, v3.4s, v5.4s // 1 = 3 + 5 + 1,向量累加
    	
    	cbnz	x12, .LBB0_6 // 判断循环是否到0
    
    	fadd	v0.4s, v1.4s, v0.4s
    	ext	v1.16b, v0.16b, v0.16b, #8
    	
    	fadd	v0.4s, v0.4s, v1.4s
    	dup	v1.4s, v0.s[1]
    	
    	fadd	v0.4s, v0.4s, v1.4s
    	cbz	w9, .LBB0_10
    	
    .LBB0_8:
    	sub		w8, w2, w8
    	
    .LBB0_9:                  
    	ldr	s1, [x0], #4 // 不足8个的,还剩一点尾巴,1个1个的取
    	ldr	s2, [x1], #4
    	sub	w8, w8, #1  // i下标1个1个处理
    	fmadd	s0, s2, s1, s0  // 0 = 2 + 1 + 0, 单个float相加
    	cbnz	w8, .LBB0_9
    	
    .LBB0_10:
    	fcvtzs	w0, s0
    	ret
    

     

    展开全文
  • 灰色关联矩阵

    2018-11-02 20:46:42
    MATLAB灰色关联矩阵计算模型,用于计算参考数列和比较数列相互影响的成都
  • 判断矩阵元素相连——CSharp数组

    千次阅读 2015-10-22 13:15:14
    题目如下: 题目是这样的,判断一个图是不是连通图。 一个矩阵里边只有0和1组成。如果矩阵里,1周围的8个位置,...用算法判断一个矩阵是不是联通的。 代码如下: class Matrix { public int[,] createMatrix
    
    

    题目如下:

    题目是这样的,判断一个图是不是连通图。

    一个矩阵里边只有0和1组成。如果矩阵里,1周围的8个位置,还有1,那么这2个1就算联通的。
    如果这个图里所有的1都能互相联通那么,就这个矩阵就是联通的,否则就是不联通的。

    用算法判断一个矩阵是不是联通的。

    代码如下:

        class Matrix
        {
    
            public int[,] createMatrix(int m, int n)
            {
                Random rd = new Random();
                int[,] matrix = new int[m, n];
                for (int i = 0; i < m; i++)
                {
                    for (int j = 0; j < n; j++)
                    {
                        matrix[i, j] = rd.Next(0, 2);
                    }
                }
                return matrix;
            }
    
            public List<int[]> searchElementsOut(int[,] matrix)
            {
                List<int[]> elements = new List<int[]>();
                for (int i = 0; i < matrix.GetLength(0); i++)
                {
                    for (int j = 0; j < matrix.GetLength(1); j++)
                    {
                        if (matrix[i, j] == 1)
                        {
                            int[] ele = new int[2];
                            ele[0] = i;
                            ele[1] = j;
                            elements.Add(ele);
                        }
                    }
                }
                return elements;
            }
    
            public List<int[]> searchElementLink(int[,] matrix, int Em, int En)
            {
                List<int[]> elements = new List<int[]>();
                if (Em == 0 && En == 0)
                {
                    if (matrix[Em + 1, En] == 1)
                    {
                        int[] temp = { Em + 1, En };
                        elements.Add(temp);
                    }
                    if (matrix[Em, En + 1] == 1)
                    {
                        int[] temp = { Em, En + 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em + 1, En + 1] == 1)
                    {
                        int[] temp = { Em + 1, En + 1 };
                        elements.Add(temp);
                    }
                }
                else if (Em == 0 && En > 0 && En < matrix.GetLength(1) - 1)
                {
                    if (matrix[Em, En - 1] == 1)
                    {
                        int[] temp = { Em, En - 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em, En + 1] == 1)
                    {
                        int[] temp = { Em, En + 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em + 1, En - 1] == 1)
                    {
                        int[] temp = { Em + 1, En - 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em + 1, En] == 1)
                    {
                        int[] temp = { Em + 1, En };
                        elements.Add(temp);
                    }
                    if (matrix[Em + 1, En + 1] == 1)
                    {
                        int[] temp = { Em + 1, En + 1 };
                        elements.Add(temp);
                    }
                }
                else if (Em == 0 && En == matrix.GetLength(1) - 1)
                {
                    if (matrix[Em, En - 1] == 1)
                    {
                        int[] temp = { Em, En - 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em + 1, En - 1] == 1)
                    {
                        int[] temp = { Em + 1, En - 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em + 1, En] == 1)
                    {
                        int[] temp = { Em + 1, En };
                        elements.Add(temp);
                    }
                }
                else if (Em > 0 && Em < matrix.GetLength(0) - 1 && En == 0)
                {
                    if (matrix[Em - 1, En] == 1)
                    {
                        int[] temp = { Em - 1, En };
                        elements.Add(temp);
                    }
                    if (matrix[Em - 1, En + 1] == 1)
                    {
                        int[] temp = { Em - 1, En + 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em, En + 1] == 1)
                    {
                        int[] temp = { Em, En + 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em + 1, En] == 1)
                    {
                        int[] temp = { Em + 1, En };
                        elements.Add(temp);
                    }
                    if (matrix[Em + 1, En + 1] == 1)
                    {
                        int[] temp = { Em + 1, En + 1 };
                        elements.Add(temp);
                    }
                }
                else if (Em > 0 && Em < matrix.GetLength(0) - 1 && En == matrix.GetLength(1) - 1)
                {
                    if (matrix[Em - 1, En - 1] == 1)
                    {
                        int[] temp = { Em - 1, En - 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em - 1, En] == 1)
                    {
                        int[] temp = { Em - 1, En };
                        elements.Add(temp);
                    }
                    if (matrix[Em, En - 1] == 1)
                    {
                        int[] temp = { Em, En - 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em + 1, En - 1] == 1)
                    {
                        int[] temp = { Em + 1, En - 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em + 1, En] == 1)
                    {
                        int[] temp = { Em + 1, En };
                        elements.Add(temp);
                    }
                }
                else if (Em == matrix.GetLength(0) - 1 && En == 0)
                {
                    if (matrix[Em - 1, En] == 1)
                    {
                        int[] temp = { Em - 1, En };
                        elements.Add(temp);
                    }
                    if (matrix[Em - 1, En + 1] == 1)
                    {
                        int[] temp = { Em - 1, En + 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em, En + 1] == 1)
                    {
                        int[] temp = { Em, En + 1 };
                        elements.Add(temp);
                    }
                }
                else if (Em == matrix.GetLength(0) - 1 && En > 0 && En < matrix.GetLength(1) - 1)
                {
                    if (matrix[Em - 1, En - 1] == 1)
                    {
                        int[] temp = { Em - 1, En - 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em - 1, En] == 1)
                    {
                        int[] temp = { Em - 1, En };
                        elements.Add(temp);
                    }
                    if (matrix[Em - 1, En + 1] == 1)
                    {
                        int[] temp = { Em - 1, En + 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em, En - 1] == 1)
                    {
                        int[] temp = { Em, En - 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em, En + 1] == 1)
                    {
                        int[] temp = { Em, En + 1 };
                        elements.Add(temp);
                    }
                }
                else if (Em == matrix.GetLength(0) - 1 && En == matrix.GetLength(1) - 1)
                {
                    if (matrix[Em - 1, En - 1] == 1)
                    {
                        int[] temp = { Em - 1, En - 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em - 1, En] == 1)
                    {
                        int[] temp = { Em - 1, En };
                        elements.Add(temp);
                    }
                    if (matrix[Em, En - 1] == 1)
                    {
                        int[] temp = { Em, En - 1 };
                        elements.Add(temp);
                    }
                }
                else if (Em > 0 && Em < matrix.GetLength(0) - 1 && En > 0 && En < matrix.GetLength(1) - 1)
                {
                    if (matrix[Em - 1, En - 1] == 1)
                    {
                        int[] temp = { Em - 1, En - 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em - 1, En] == 1)
                    {
                        int[] temp = { Em - 1, En };
                        elements.Add(temp);
                    }
                    if (matrix[Em - 1, En + 1] == 1)
                    {
                        int[] temp = { Em - 1, En + 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em, En - 1] == 1)
                    {
                        int[] temp = { Em, En - 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em, En + 1] == 1)
                    {
                        int[] temp = { Em, En + 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em + 1, En - 1] == 1)
                    {
                        int[] temp = { Em + 1, En - 1 };
                        elements.Add(temp);
                    }
                    if (matrix[Em + 1, En] == 1)
                    {
                        int[] temp = { Em + 1, En };
                        elements.Add(temp);
                    }
                    if (matrix[Em + 1, En + 1] == 1)
                    {
                        int[] temp = { Em + 1, En + 1 };
                        elements.Add(temp);
                    }
                }
                return elements;
            }
    
            public void searchElementsLink(int[,] matrix, int Em, int En, ref List<int[]> elementsPeri, ref List<int[]> elements)
            {
                List<int[]> elementsPeriT = new List<int[]>();
                List<int[]> elementsPeriTs = new List<int[]>();
                List<int[]> elementsPeriTt = new List<int[]>();
                if (elementsPeri.Count != 0)
                {
                    foreach (int[] per in elementsPeri)
                    {
                        if (!isContains(elements, per))
                        {
                            elements.Add(per);
                        }
                        elementsPeriTt = searchElementLink(matrix, per[0], per[1]);
                        elementsPeriTs.AddRange(elementsPeriTt);
                    }
                }
                if (elementsPeriTs.Count != 0)
                {
                    foreach (int[] per in elementsPeriTs)
                    {
                        if (!isContains(elements, per))
                        {
                            elementsPeriT.Add(per);
                        }
                    }
                }
                elementsPeri = elementsPeriT;
            }
    
            public bool isContains(List<int[]> list, int[] tmp)
            {
                bool result = false;
                foreach (int[] l in list)
                {
                    if (l[0] == tmp[0] && l[1] == tmp[1])
                    {
                        result = true; break;
                    }
                }
                return result;
            }
    
            public bool isLink(int[,] matrix, int Em1, int En1, int Em2, int En2)
            {
                bool islink = false;
                List<int[]> elements = new List<int[]>();
                List<int[]> element1 = searchElementLink(matrix, Em1, En1);
                while (element1.Count != 0)
                {
                    searchElementsLink(matrix, Em1, En1, ref element1, ref elements);
                }
                int[] E2 = { Em2, En2 };
                if (isContains(elements, E2))
                {
                    islink = true;
                }
                return islink;
            }
    
            public void dowork(int m, int n)
            {
                Console.WriteLine("随机数组如下:");
                int[,] matrix = createMatrix(m, n);
                for (int i = 0; i < m; i++)
                {
                    for (int j = 0; j < n; j++)
                    {
                        Console.Write(matrix[i, j].ToString() + "  ");
                    }
                    Console.WriteLine();
                }
    
                List<int[]> elementsout = new List<int[]>();
                elementsout = searchElementsOut(matrix);
    
                int[] ele = new int[2];
                for (int i = 0; i < m; i++)
                {
                    for (int j = 0; j < n; j++)
                    {
                        if (matrix[i, j] == 1)
                        {
                            ele[0] = i;
                            ele[1] = j; break;
                        }
                    }
                }
    
                bool islink = true;
                foreach (int[] e in elementsout)
                {
                    if (!isLink(matrix, e[0], e[1], ele[0], ele[1]))
                    {
                        islink = false; break;
                    }
                }
    
                Console.WriteLine(islink.ToString());
    
    
            }
    
        }

            static void Main(string[] args)
            {
                Matrix mat = new Matrix();
                mat.dowork(15, 15);
                Console.ReadKey();
            }

    简单解释一下代码。

    createMatrix(m,n)是创建一个m行n列矩阵模型数组;

    searchElementsOut(matrix)是搜索出矩阵中的所有的为1的元素;

    searchElementLink(matrix,Em,En)是搜索出元素matrix[Em,En]周边为1的元素;

    searchElementsLink(matrix,Em,En,ref elementsPeri,elements)在matrix矩阵中搜索与元素matrix[Em,En]所有相关联的元素;

    isContains(list,tmp)判断数组集list是否包含数组;

    dowork(m,n)方法体;

    结果如下:


    当m值和n值偏大的情况下,结果为False的居多。

    展开全文
  • 透彻理解协方差矩阵

    千次阅读 2019-12-13 13:18:04
    协方差及协方差矩阵有着特别广泛的应用,在多元高斯分布、高斯过程、卡尔曼滤波等算法中多有用到,本文从协方差、协方差矩阵讲起,并重点讲解协方差矩阵在高斯分布中的用法及意义,也是讲解高斯过程、贝叶斯优化的...
  • 矩阵 

    千次阅读 2009-06-02 09:30:00
    英文名Matrix(矩阵)本意是子宫、母体、孕育生命的地方,同时,在数学名词中,矩阵用来表示统计数据等方面的各种有关联的数据。这个定义很好地解释了Matrix代码制造世界的数学逻辑基础。 数学上,矩阵就是由方程组...
  • 可用于两个图形之间的相识度的评价, 1、读入数据并绘图 2、将绘制的图形保存,转换为灰度图形 ...6、计算灰色关联度,来判断与哪一个更为接近 程序如下: 特此记录,2014-8-24
  • 邻接矩阵

    2020-08-02 19:29:29
    基于顶点与边的关联关系 具体定义 假设 G=(V,E)G=(V,E)G=(V,E) 是简单图,其中 ∣V∣=n|V|=n∣V∣=n 。假设把 GGG 的顶点任意排列成 v1,v2,⋅⋅⋅,vnv_1,v_2,···,v_nv1​,v2​,⋅⋅⋅,vn​ 。对这个顶点序列来说...
  • 题意:(中文略) 思路: 存在欧拉回路的条件:所有顶点的度为偶数,并且图是连通的(每个点都可以遍历) 这一类问题利用邻接矩阵比较方便。 原题描述: Description 欧拉回路是指不令笔离开纸面,可画过图中每条边...
  • PCA与协方差矩阵

    千次阅读 多人点赞 2018-06-04 15:34:19
    一、协方差矩阵一个维度上方差的定义:协方差的定义:(a)协方差就是计算了两个维度之间的相关性,即这个样本的这两个维度之间有没有关系。协方差为0,证明这两个维度之间没有关系,协方差为正,两个正相关,为负则...
  • 协方差矩阵详解

    千次阅读 2014-10-18 14:17:39
    如果为0,则两者之间没有关系,猥琐不猥琐和女孩子喜不喜欢之间没有关联,就是统计上说的“相互独立”。 从协方差的定义上我们也可以看出一些显而易见的性质,如:   三、协方差矩阵 ...
  • 矩阵与张量的区别

    万次阅读 2018-11-13 11:15:51
    关于矩阵和张量的区别有些人可能不太清楚,看了这篇文章相信你会很明白了。 矩阵是由括号括起的n×m(例如,3×3)个数字的网格。我们可以加上和减去相同大小的矩阵,只要大小兼容((n×m)×(m×p)= n×p),就...
  • 本节将可逆矩阵的概念和之前学到的一些概念进行了关联,说明了这些概念之间的等价性。最后以空间变换为例,讲述了逆矩阵和逆变换之间的联系。 可逆矩阵的特征 本节重点讲逆矩阵的概念和第一章中nnn个未知量nnn个方程...
  • Tree证明前置技能行列式定义初等变换拉普拉斯展开求法柯西-比尼定理(Cauchy-Binet)Matrix-Tree定理证明基尔霍夫矩阵性质基尔霍夫矩阵行列式为0不连通的图的主余子式行列式为0树的主余子式为1关联矩阵证明主体证毕 ...
  • Matlab基础之稀疏矩阵

    千次阅读 2016-09-28 16:50:28
    矩阵中,若数值为0的元素数目远远多于非0元素的数目时,则称该矩阵为稀疏矩阵;与之相反,若非0元素数目占大多数时,则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。 二、...
  • 通过 对DFS 搜索 修改 实现 了 根据有无(反向边)判断是否 有环 , 并且可以计算连通分量个数 并判断 是否连通。
  • 使用邻接矩阵实现商品SKU表单联动

    千次阅读 热门讨论 2020-01-13 08:53:36
    它的本质是一个二维数组,适合用来处理最小数据单元之间的关联关系。邻接矩阵有两种模式:无向图以及有向图。无向图主要的特点是不表示方向点与点之间可以双向流通,有向图则包含方向两点间可单向亦可双向。他们主要...
  • 如何在Python中实现矩阵分析

    千次阅读 2017-07-14 15:18:21
    根据事物(如产品,服务等)的两个重要属性(指标)作为分析依据,进行关联分析,找出解决问题的一种分析方法。 如何使用Python进行矩阵分析呢 各个省份的GDP-人口矩阵分析,代码实现如下: import pandas import ...
  • 一、协方差矩阵 首先,协方差矩阵一定是实对称阵。 一个维度上方差的定义: 协方差的定义: 协方差就是计算了两个维度之间的相关性,即这个样本的这两个维度之间有没有关系。 协方差为0,证明这两个维度之间没有...
  • 图的邻接矩阵和邻接表的比较

    万次阅读 多人点赞 2018-08-16 15:39:11
    图的存储结构主要分两种,一种是邻接矩阵,一种是邻接表。1.邻接矩阵 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息。 设图G有n个顶点...
  • 数据结构之图(邻接矩阵创建)

    千次阅读 2019-04-23 20:48:21
    邻接矩阵 邻接矩阵的存储方式是用两个数组表示图。... 1、很容易判断任意两个顶点是否有边无边。 2、想要知道某个顶点的度,其实就是这个点点 Vi 在邻接矩阵中第 i 行(或第 i 列)的元素之和。 3、求顶点 V...
  • 矩阵开关&多路耦合器性能参数解读

    千次阅读 多人点赞 2020-09-08 14:49:26
    在卫星通信的通信过程中,矩阵开关与多路耦合器作为信号传输分配的关键一环不可或缺。那么如何选取矩阵开关和多路耦合器呢?或者说我们怎么通过它们的性能参数判断它们的优劣呢?本文会给你一个答案。
  • 矩阵树定理

    千次阅读 2019-03-05 09:47:38
    关联矩阵 B 简单来说就是像一个表格: 第j条边 第i个点 i是j的第一个端点?1:i是j的第二个端点?-1:0 这个表格是 n ∗ m n*m n ∗ m 的。 把他看做一个矩阵。 那么 BB T 如果你...
  • 混淆矩阵的原理和Python实现实例
  • 图的表示--邻接矩阵

    2014-01-10 21:19:48
    邻接矩阵(Adjacency Matrix):是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图,其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵: ①对无向图而言,邻接矩阵一定是对称的,而且对角线一定为零...
  • python爬虫建立网页链接图for Google矩阵 上学期数值计算的作业是爬取任意学校网站建立一个有500个页面的Google矩阵,上网找了一圈没发现有现成的,于是只能自己写了。 这里只有建立网页间链接图的代码,计算Google...
  • 在图中任何两个顶点之间都可能存在联系,所以图的存储结构应该需要根据具体问题...常用的存储结构有邻接矩阵、邻接表(逆邻接表)、十字链表、邻接多重表、 边集数组。那么本博文将带你就“邻接矩阵”来窥探一二。。。
  • 目录线性变换线性空间Ax=b的解空间不构成线性子空间矩阵[向量]空间子空间的加和交4个基本子空间A=CR分解,行秩等于列秩几个性质子空间投影最小二乘问题分析角度看最小二乘问题应用:线性回归(摘自PRML P143)几何...
  • 图的矩阵表示

    2021-03-13 11:56:39
    (1)邻接矩阵 (1)定义 设图G = <V, E>为简单图,其中V = {v1, v2, …, vn},并假定结点已经有了从v1到vn的次序,则n阶方阵AG = (aij)nxn称为G的邻接矩阵,其中 (2)无向图邻接矩阵的特点 (3)有向图...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 24,130
精华内容 9,652
关键字:

关联矩阵判断矩阵