Python+OpenCV计算机视觉

如何用c语言来判断邻接矩阵是否连通的代码 判断所给的图是否为连通图。 实验用例：邻接矩阵A1=0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0

如何用邻接矩阵判断无向图的连通性？ 要Java或者C#的实现思路，最好有代码。

怎样用C语言表示邻接矩阵求可达矩阵，并且判断图的连通性，急，谢谢帮忙

已知无向图如图所示，给出它的邻接矩阵 B E / \ / \ A D G \ / \ / C F

``` #define maxvex 10 #include <iostream> #include <stack> using namespace std; int visit[maxvex]; typedef char vertextype;//结点数据 typedef struct { vertextype vexs[maxvex];//顶点表 int arc[maxvex][maxvex];//邻接矩阵 int numnodes,numedges,direction;//顶点数，边数，方向 }graph; void creatematrix(graph *g)//邻接矩阵 { int i,j; vertextype e1,e2; cout<<"输入顶点和边数"<<endl; cin>>g->numnodes>>g->numedges; cout<<"是否为有向图？有向图输入1，无向图输入0"<<endl; cin>>g->direction; cout<<"输入各个顶点数据"<<endl; for(i=0;i<g->numnodes;i++) cin>>g->vexs[i];//输入每个节点的字符数据到顶点表 vexs[0]=A for(i=0;i<g->numnodes;i++) { for(int j=0;j<g->numnodes;j++) g->arc[i][j]=0; }//邻接矩阵初始化 cout<<"请输入每条边的两个顶点结点"<<endl; for(int k=0;k<g->numedges;k++)//输入边数 { cin>>e1>>e2; for(i=0;i<g->numnodes;i++)//根据顶点表查找第一个结点 { if(g->vexs[i]==e1) break; } for(j=0;j<g->numnodes;j++)//根据顶点表查找第二个结点 { if(g->vexs[j]==e2) break; } g->arc[i][j]=1; if(g->direction==0) g->arc[j][i]=g->arc[i][j];//无向图的邻接矩阵对称 } cout<<"邻接矩阵建立完成"<<endl; cout<<"邻接矩阵如下"<<endl; for(i=0;i<g->numnodes;i++) { for(j=0;j<g->numnodes;j++) cout<<g->arc[i][j]; cout<<endl; } } void matrixoutput(graph g) { cout<<"邻接矩阵如下"<<endl; for(int i=0;i<g.numnodes;i++) { for(int j=0;j<g.numnodes;j++) cout<<g.arc[i][j]; cout<<endl; } } void DFS1(graph g,int i) { visit[i]=true; cout<<g.vexs[i]<<" ";//打印顶点 for(int j=0;j<g.numnodes;j++)//一个连通分量的遍历 if(g.arc[i][j]==1 && !visit[j]) DFS1(g,j); } //邻接矩阵的深度遍历 void DFS(graph g) { for(int i=0;i<g.numnodes;i++) visit[i]=0;//初始所有顶点状态都是未访问过状态 for(int i=0;i<g.numnodes;i++)//若是连通图，只会执行一次 if(!visit[i])//对未访问过的顶点调用DFS DFS1(g,i); } void output(stack<int> s)//打印栈内元素 { stack<int> out; int e; while(!s.empty()) { e=s.top(); s.pop(); out.push(e); } while(!out.empty()) { char b=char(out.top())+65; cout<<b<<" "; out.pop(); } cout<<endl; } void way(graph g,vertextype e1,vertextype e2) { int visit[g.numnodes]; for(int i=0;i<g.numnodes;i++) visit[i]=0; stack<int> s;//栈内为顶点数据的整型 int a=int(e1)-65;//起点 int b=int(e2)-65;//终点 s.push(a); while(s.top()!=b){ for(int i=0;i<g.numnodes;i++){ if(visit[i]=0 && g.arc[s.top()][i]==1){ s.push(i); } } } output(s); while(!s.empty()){ int temp1=s.top(); s.pop(); for(int i=0;i<g.numnodes;i++){ if(visit[i]=0 && g.arc[s.top()][i]==1){ s.push(i); } } if(s.top()==b) output(s); visit[temp1]=0; } } main() { graph g; vertextype e1,e2; creatematrix(&g); cout<<"对邻接矩阵进行深度优先遍历"<<endl; DFS(g); cout<<endl; cout<<"请输入起点和终点"<<endl; cin>>e1>>e2; way(g,e1,e2); system("pause"); } ``` 

无向图以邻接矩阵存储，请算法描述深度优先遍历该图的非递归算法。哪位大神可以帮忙写具体点用栈怎么实现？谢谢了！

假设用邻接矩阵存储无向图，设计算法，求出度数最大的顶点编号 急急急紧急急急急急急急急急急急急急急急急急急急急急急

背景：连通性分析，判断当前邻接矩阵W可以划分成几个互不联通的子图 如果图可以划分成2个互不联通的子图，那么其邻接矩阵W通过行列交换变换以后应该可以划分为[A,0;0,B]这种形式,其两个互不联通的子图的邻接矩阵为A，B 类似的，划分成2个互不联通的子图，其邻接矩阵通过行列交换变换以后应为[A,0,0;0,B,0;0,0,C]的形式，其三个互不联通的子图的邻接矩阵为A，B，C -->求大佬们帮助的问题是，给出一个邻接矩阵W，我想知道其可以划分为几个互不联通的子图？划分出来的子图的邻接矩阵分别是什么?

``` #include<iostream> using namespace std; const int MaxSize=10;//图中的最多顶点个数 template <class T> classMGraph { public: MGraph(T a[],int n,int e);//构造函数，建立具有n个顶点e条边的图 ~MGraph(){} //析构函数为空 void DFSTraverse(int v); //深度优先遍历图 void BFSTraverse(int v); //广度优先遍历图 void Setvisited(); // private: T vertex[MaxSize]; //存放图中顶点的数组 int arc[MaxSize][MaxSize]; //存放图中边的数组 int vertexNum,arcNum; //图的顶点数和边数 int visited[MaxSize]; // }; template<class T> void MGraph<T>::Setvisited() { for(int i=0;i<vertexNum;i++) visited[i]=0; } template<class T> MGraph<T>::MGraph(T a[],int n,int e) { int i,j,k; vertexNum=n;arcNum=e; for(i=0;i<vertexNum;i++) vertex[i]=a[i]; for(i=0;i<vertexNum;i++) //初始化邻阶矩阵 for(j=0;j<vertexNum;j++) arc[i][j]=0; for(k=0;k<arcNum;k++) //依次输入每一条边 { cout<<"putin bianhao"; cin>>i>>j; //输入边依附的两个顶点的编号 arc[i][j]=1;arc[j][i]=1;//置有边标志 } } template<class T> void MGraph<T>::DFSTraverse(int v) { int j; cout<<vertex[v];visited[v]=1; for(j=0;j<vertexNum;j++) if(arc[v][j]==1&&visited[j]==0) DFSTraverse(j); } template<class T> void MGraph<T>::BFSTraverse(int v) { int j,front,rear; int Q[MaxSize]; front=rear=-1;//初始化队列，假设队列采用顺序存储且不会发溢出 cout<<vertex[v];visited[v]=1;Q[++rear]=v;//当访问顶点入队 while(front!=rear) //当队列非空时 { v=Q[++front]; for(j=0;j<vertexNum;j++) //将队头元素出队并送到v中 if(arc[v][j]==1&&visited[j]==0) { cout<<vertex[j];visited[j]=1;Q[++rear]=j; } } } int main() { int n,e; cout <<"putin dian:"; cin>>n; cout<<"putin edge:"; cin>>e; char a[MaxSize]; cin>>a; MGraph<char> m(a,n,e); m.Setvisited(); cout<<"DFST:"; m.DFSTraverse(1); cout<<endl; m.Setvisited(); cout<<"BFST:"; m.BFSTraverse(1); cout<<endl; return 0; } ```

在数据结构教程里，有一章是实现广度优先遍历非联通图，然后把遍历的图的节点 存在树的结构里，树的储存方式是孩子兄弟表示法。当我运行代码后，输入 了图的节点和节点之间的关系： 13,13 1 2 3 4 5 6 7 8 9 10 11 12 13 1,2 1,3 1,6 1,12 2,13 4,5 7,8 7,10 7,9 8,10 11,12 11,13 12,13 该有的结果应该是： 1 2 13 3 6 12 11 4 5 7 8 9 10 可我运行的结果是123 \n 456，也就是说function BFSForest根本没有被执行。 哪位大神可以帮我看看问题出在哪，谢谢！ 以下是我的代码。 ``` #include <stdio.h> #include <stdlib.h> #define MAX_VER_NUM 20 //图的最大节点数 #define VRTYPE int //弧的类型 #define VertexType int //节点类型 typedef enum {false,true} bool; bool visited[MAX_VER_NUM]; typedef struct { VRTYPE adj; }adjMatrix[MAX_VER_NUM][MAX_VER_NUM];//图的邻接矩阵 typedef struct { VertexType ver[MAX_VER_NUM]; adjMatrix arcs; int num_vex,num_arcs; }MGraph;//图的结构体 typedef struct { VertexType data; struct gNode* lchild; struct gNode* nextsibling; }gNode;//生成树的节点，用孩子兄弟表示法 typedef struct { struct QueueCell *next; gNode *node; }QueueCell;//队列的节点 typedef struct { QueueCell *top; QueueCell *tail; }Queue;//定义队列的结构体 void initQueue(Queue **q) { if(!*q) { *q=(Queue*)malloc(sizeof(Queue)); (*q)->top=(QueueCell*)malloc(sizeof(QueueCell)); (*q)->top->next=NULL; (*q)->top->node=NULL; (*q)->tail=(*q)->top;//空队列头和尾巴在一起 } } int isEmpty(Queue *q) { if(q->tail==q->top)//空队列头和尾巴在一起 { return 1; } return 0;//如果判定结果为错，必须返回0，而不能是-1 } void EnQueue(Queue **q,gNode *g) { if(isEmpty(*q))//当队列为空时，头指针的next指针指向进队的节点 { QueueCell *c=(*q)->top->next; c->node=g; (*q)->tail=c; } else//如果队列不为空，头指针不变，更新尾巴 { QueueCell *c=(*q)->tail->next; c->node=g; (*q)->tail=c; } } gNode* DeQueue(Queue **q) { QueueCell *c=(*q)->top->next; (*q)->top->next= c->next; if(!(c->next))//出队后，队列为空时，尾巴重新指向头结点 { (*q)->tail=(*q)->top; } return c->node; } int locateVex(MGraph *G,VertexType v) { for(int i=0;i<G->num_vex;i++) { if(G->ver[i]==v) { return i; } } return -1; } void createGraph(MGraph *G) { scanf("%d,%d",&(G->num_vex),&(G->num_arcs));//输入图的节点数和弧的数量 for(int i=0;i<G->num_vex;i++) { scanf("%d",&(G->ver[i]));//输入图每个节点的值 } for(int i=0;i<G->num_vex;i++)//初始化邻接矩阵 { for(int j=0;j<G->num_vex;j++) { G->arcs[i][j].adj=0; } } for(int i=0;i<G->num_arcs;i++)//更新邻接矩阵 { VertexType v1,v2; scanf("%d,%d",&v1,&v2); int n1=locateVex(G,v1); int n2=locateVex(G,v2); if(n1==-1||n2==-1) { printf("no such vertex"); exit(-1); } G->arcs[n1][n2].adj=1; G->arcs[n2][n1].adj=1; } } int firstAdjVex(MGraph *G,int v)//找到指定节点第一个相邻节点 { for(int i=0;i<G->num_vex;i++) { if(G->arcs[v][i].adj) { return i; } } return -1; } int nextAdjVex(MGraph *G, int v,int w)//找到指定节点下一个相邻节点 { for(int i=w+1;i<G->num_vex;i++) { if(G->arcs[v][i].adj) { return i; }dang } return -1; } void visit(gNode *g) { printf("%d ",g->data); } void BFSTree(MGraph *G,gNode **g) { printf("BFSTree"); gNode *node=NULL; Queue *q=NULL; initQueue(&q); EnQueue(&q,*g); int p=locateVex(G,(*g)->data); visited[p]=true; while(!isEmpty(q)) { bool first =true; gNode* n=DeQueue(&q); node=n; int v=locateVex(G,node->data); for(int i=firstAdjVex(G,v);i>=0;i=nextAdjVex(G,v,i)) { if(!visited[i]) { gNode *gnode=(gNode*)malloc(sizeof(gNode)); gnode->data=G->ver[i]; gnode->lchild=NULL; gnode->nextsibling=NULL; visited[i]=true; EnQueue(&q,gnode); if(first) { node->lchild=gnode; first=false; } else { node->nextsibling=gnode; } node=gnode; } } } } void BFSForest(MGraph *G,gNode **g) { (*g)=NULL; for(int i=0;i<G->num_vex;i++) { visited[i]=false; }dang gNode *node=NULL; int v = locateVex(G,(*g)->data); visited[v]=true; for(int i=0;i<G->num_vex;i++) { if(!visited[i]) { gNode *n=(gNode*)malloc(sizeof(gNode)); n->data=G->ver[i]; n->lchild=NULL; n->nextsibling=NULL; if(!(*g)) { *g=n; } else { node->nextsibling=n;dang } node=n; BFSTree(G,&n); } } } void preOrderTraverse(gNode *g) { visit(g); preOrderTraverse(g->lchild); preOrderTraverse(g->nextsibling); } int main(void) { MGraph G; createGraph(&G); printf("123\n"); gNode *g; printf("456\n"); BFSForest(&G,&g); printf("789\n"); preOrderTraverse(g); return 0; } ```

对于下面的有向图，请给出该图的(1) 强连通分量，(2) 每个顶点的入度和出度。  第1小题，涉及“连通分量”概念，特别注意是一个图的每个连通量是不相交的子图

无向图的可达矩阵是怎么写的啊？有向图的两结点可达就为1，不可达就为0，很好写。但是无向图如果没有孤立结点，岂不是整个可达矩阵内全为1？可达矩阵是不是这么回事啊？

怎样去判断一个有向图中是否存在一条经过所有点的简单路径？能否把这个问题转化成哈密顿回路问题？

Problem Description 欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？ Input 测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数N ( 1 < N < 1000 )和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。当N为0时输入结 束。 Output 每个测试用例的输出占一行，若欧拉回路存在则输出1，否则输出0。 Sample Input 3 3 1 2 1 3 2 3 3 2 1 2 2 3 0 Sample Output 1 0

写了一段不带权无向网邻接表的代码，用算法实现最小生成树，但是Kruskal和Prim两个算法得出的是不一样的，Kruskal是正确的，求解

该程序运用邻接矩阵创建图，运行后没有出现图的广度优先遍历的结果的打印。。。请大神帮忙看看我写的广度优先遍历算法哪里出现了问题，万分感激！ #include "stdafx.h" #include <iostream.h> #include <conio.h> #include <stdio.h> #include <queue> using namespace std; void EnQueue_Sq( queue<int> &Q , int v ) { Q.push( v ); } int DeQueue_SQ( queue<int> &Q ) { int i = Q.front(); Q.pop(); return i; } //1、邻接矩阵 #define VexType char #define EdgeType int #define INFINITY INT_MAX // 最大值∞ #define Max_Vertex_Num 10 // 最大顶点个数 bool visited[ Max_Vertex_Num ];//辅助数组--遍历使用 struct MGraph{ VexType vexs[ Max_Vertex_Num ]; //顶点数组 EdgeType edges[ Max_Vertex_Num ][ Max_Vertex_Num ];//邻接矩阵 int vexnum; //当前顶点数 int edgenum; //当前边数 //GraphKind kind;//图的种类标志,本练习假定图为无向带权图（即 无向网） }; void DSF_MG( const MGraph &G , int v ); void BFS_MG( const MGraph &G , int v ); /////////////////////////////算法实现///////////////////////////////////// //一、邻接矩阵操作的实现 //1、 创建图 void CreateGraph_MG( MGraph &G )//构造一个具有n个顶点,e条边的无向网(注意:输入必须准确,算法中没有判断非法输入!) { cout<<"请分别输入顶点数目和边的数目:"; cin>>G.vexnum>>G.edgenum; int n = G.vexnum; int e = G.edgenum; int i , j; for (i = 0 ; i < n ; i ++ ) { cout<<"请输入第"<<i<<"个顶点的信息:"; cin>>G.vexs[ i ]; } //初始化邻接矩阵 for ( i = 0 ; i < n ; i ++ ) for ( j = 0 ; j < n ; j ++ ) { G.edges[i][j] = INFINITY; } for ( i = 0 ; i < e ; i ++ ) { int beginNode , endNode; cout<<"请输入第"<<i<<"条边的第一个顶点的编号(从0开始):"; cin>>beginNode; cout<<"请输入第"<<i<<"条边的第二个顶点的编号(从0开始):"; cin>>endNode; cout<<"请输入第"<<i<<"条边的权值(注意为非0值):"; cin>>G.edges[beginNode][endNode]; G.edges[endNode][beginNode] = G.edges[beginNode][endNode]; } //输出图的信息 cout<<"输入完毕!"<<endl; cout<<"顶点数组:["; for (i = 0 ; i < n ; i ++ ) { cout<<G.vexs[ i ]<<" "; } cout<<"]"<<endl; cout<<"邻接矩阵:"<<endl; for ( i = 0 ; i < n ; i ++ ) { for ( j = 0 ; j < n ; j ++ ) { if( G.edges[ i ][ j ] != INFINITY ) printf( "%5d" , G.edges[i][j] ); else printf( "%5c" , '-'); //cout<<G.edges[i][j]<<" "; } //cout<<endl; printf( "\n" ); } } //2、求邻接结点及其度 void Dsp_ArjNodes_MG( const MGraph &G , int v )//输出第v个顶点的所有邻接点信息以及该结点的度(注意i不在取值范围内应提示错误信息) { if(v>=G.vexnum) cout<<"ERROR"<<endl; int count = 0; for(int i=0;i<G.vexnum;i++) { if(G.edges[v-1][i]!=INFINITY){ cout<<"临界结点有"<<i<<endl; count++; } } cout<<"该点的度为"<<count<<endl; } //3、找邻接点 int FirstAdjVex( const MGraph &G , int v )//找到顶点v（v为顶点的index）的第一个邻接点并返回该邻接点的index,如果不存在邻接点,则返回-1 { int j,p=-1,found=1; for(j=0;((j<G.vexnum)&&(found==1));j++) if(G.edges[v][j]!=INFINITY) { p=j; found=0; } return p; } //4、找下一个邻接点 int NextAdjVex( const MGraph &G , int v , int w )//v是G的某个顶点,w是v的一个邻接点,返回v（相对于w）的下一个邻接点(邻接点的index),如果w已经是最后一个邻接点,则返回-1 { int j,p=-1,found=1; for(j=w+1;((j<G.vexnum)&&(found==1));j++) if(G.edges[v][j]!=INFINITY) { p=j; found=0; } return p; } //5、广度优先遍历(主调)--例子 void BFSTraverse_MG( const MGraph &G )//广度优先遍历图 { int v; for (v=0; v<G.vexnum; ++v) visited[v] = false; //初始化访问标志 //开始遍历过程： for ( v=0; v<G.vexnum; ++v ) if ( !visited[v]) BFS_MG( G , v ); } //6、以v为起点广度优先遍历(核心函数) void BFS_MG( const MGraph &G , int v )//以v为起点进行广度优先遍历 { queue<int> Q;//定义完队列Q（不需要执行InitQueue_SQ） EnQueue_Sq(Q, v); // v入队列 visited[v] = true; cout<<G.vexs[v]<<" "; while(!Q.empty ()) { int s = DeQueue_SQ( Q );// 队头元素出队 for(int w=FirstAdjVex(G,s);w!=INFINITY;w=NextAdjVex(G,s,w)) if ( !visited[w] ) { visited[w]=true; cout<<G.vexs[w]<<" "; EnQueue_Sq(Q, w); // 访问的顶点w入队列 } // if }//while } void main() { MGraph MG; CreateGraph_MG( MG ); // 打印顶点a的所有邻接点 Dsp_ArjNodes_MG( MG ,3); cout<<"输出广度优先遍历结果："<<endl; BFSTraverse_MG( MG ); getch(); }

无向图的广度遍历序列一般会有多种广度遍历序列。 要求：1对于给定的无向图，输出所有的正确的广度遍历序列 2对任何给定的存储为邻接矩阵的图都能够处理 3 给定起点 提示：采用树来存储多个广度遍历序列 求解答~~~~~

#include <stdio.h> #include <stdlib.h> #define Max 100 #define Wu 0 typedef struct { int vexs[Max]; int arcs[Max][Max]; int vexnum; }MGraph; int visited[Max]; void CreateGraph(MGraph *G,int n) { int i,j,e,u,v,value; for(i=0;i<n;i++) { printf("输入第%d个顶点信息:",i+1); scanf("%d",&G->vexs[i]); for(j=0;j<n;j++) G->arcs[i][j]=Wu; } for(i=0;i<n;i++) G->arcs[i][j]=0; printf("请输入边的个数:"); scanf("%d",&e); for(i=0;i<e;i++) { printf("输入边所依附的两个顶点和值:<u,v,value>:"); scanf("%d%d%d",&u,&v,&value); G->arcs[u][v]=value; G->arcs[v][u]=value; } printf("邻接矩阵结构为:\n"); for(i=0;i<n;i++) printf("%4d",G->vexs[i]); printf("\n"); for(i=0;i<n;i++) { for(j=0;j<n;j++) printf("%4d",G->arcs[i][j]); printf("\n"); } } int GetFirstVex(MGraph G,int v) { int col; if(v<0||v>G.vexnum) { printf("参数v越界出错!\n"); exit(1); } for(col=0;col<=G.vexnum;col++) if(G.arcs[v][col]>0&&G.arcs[v][col]<Wu) return col; return -1; } int GetNextVex(MGraph G,int v1,int v2) { int col; if(v1<0||v1>G.vexnum||v2<0||v2>G.vexnum) { printf("参数v1或v2越界出错!\n"); exit(1); } for(col=v2+1;col<=G.vexnum;col++) if(G.arcs[v1][col]>0&&G.arcs[v1][col]<Wu) return col; return -1; } void DFS(MGraph G,int v) { int w; printf("%4c",G.vexs[v]); visited[v]=1; w=GetFirstVex(G,v); while(w!=-1) { if( !visited[w]) DFS(G,w); w=GetNextVex(G,v,w); } } void DFST(MGraph G) { int i; for(i=0;i<G.vexnum;i++) visited[i]=0; for(i=0;i<G.vexnum;i++) if(!visited[i]) DFS(G,i); } void main() { MGraph G; int n; printf("输入顶点数:"); scanf("%d",&n); CreateGraph(&G,n); printf("深度优先遍历为:"); DFST(G); printf("\n"); }

设G(V,E)是一个无向连通图，s,t是它的两个不同的结点。 G(V,E)的每个结点或者着红色，或者着兰色。试设计一个求从s到t经过兰色结点数最少的路经的算法。

2019 Python开发者日-培训

150讲轻松搞定Python网络爬虫

设计模式（JAVA语言实现）--20种设计模式附带源码

YOLOv3目标检测实战：训练自己的数据集

java后台+微信小程序 实现完整的点餐系统

三个项目玩转深度学习（附1G源码）

初级玩转Linux+Ubuntu(嵌入式开发基础课程)

2019 AI开发者大会

玩转Linux：常用命令实例指南

一学即懂的计算机视觉（第一季）

4小时玩转微信小程序——基础入门与微信支付实战

Git 实用技巧

Python数据清洗实战入门

使用TensorFlow+keras快速构建图像分类模型

实用主义学Python（小白也容易上手的Python实用案例）

程序员的算法通关课：知己知彼（第一季）

MySQL数据库从入门到实战应用

机器学习初学者必会的案例精讲

手把手实现Java图书管理系统（附源码）

极简JAVA学习营第四期（报名以后加助教微信：eduxy-1）

.net core快速开发框架

玩转Python-Python3基础入门

Python数据挖掘简易入门

微信公众平台开发入门

程序员的兼职技能课

Windows版YOLOv4目标检测实战：训练自己的数据集

HoloLens2开发入门教程

微信小程序开发实战

Java8零基础入门视频教程