用可达性矩阵判断图的连通性用c语言

发布网友发布时间：2023-02-04 01:57

共1个回答

热心网友时间：2024-11-30 14:39

这些是c++的代码不知是否满足你的要求。1、邻接表表示的图中分别用DFS和BFS遍历#include#include#includeusingnamespacestd;/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////Description:图的邻接表的结点structEdge{intdest;//目标结点下标//intvalue;//路径长度Edge*link;//下一个结点};/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////Description:为图添加一条边//Input:edge-欲加边的结点;dest-目的结点//Output:edge-加边后的结点//Tags:voidAddEdge(Edge*&edge,intdest){//简单的链表操作if(!edge){edge=newEdge;edge->dest=dest;edge->link=0;}else{Edge*tail=edge;while(tail->link)tail=tail->link;tail->link=newEdge;tail=tail->link;tail->dest=dest;tail->link=0;}}/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////Description:Console下输入图的边//Input:Graph-图;n-图的结点的个数;EdgeNumber-添加边的个数;//Output:Graph-添加边后的图//Tags:用户输入点对(a,b),表示添加a->b的路径voidInput(Edge**&graph,intn,intEdgeNumber){inti=0,a,b;for(i=0;ib的边}}/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////Description:深度优先搜索并输出//Input:Graph-图;n-图的结点的个数;StartEdge—开始的结点;//Output:Console下输出遍历的顺序//Tags:递归调用_dfs过程、回溯算法void_dfs(Edge**&graph,bool*visited,intn,intindex);voidDFS(Edge**&graph,intn,intStartEdge){bool*visited=newbool[n];//标记每个结点是否已访问memset(visited,(int)false,sizeof(bool)*n);visited[StartEdge]=true;printf("startedge:%d\n",StartEdge);_dfs(graph,visited,n,StartEdge);visited[StartEdge]=false;}//_dfs过程：//Input:Graph-图;n-图的结点的个数;index-当前的下标,visited-记录结点是否已访问//Output:Console下输出遍历的顺序void_dfs(Edge**&graph,bool*visited,intn,intindex){intnIndex;//下一个结点下标Edge*edge=graph[index];//遍历用结点while(edge)//遍历所有的邻接结点{nIndex=edge->dest;if(!visited[nIndex]){visited[nIndex]=true;printf("%d\t",nIndex);_dfs(graph,visited,n,nIndex);}edge=edge->link;}}/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////Description:广度优先搜索并输出//Input:Graph-图;n-图的结点的个数;StartEdge-开始的结点//Output:Console下输出遍历的顺序//Tags:需要一个队列记录所有的灰色结点voidBFS(Edge**&graph,intn,intStartEdge){bool*visited=newbool[n];//记录结点是否已访问memset(visited,(int)false,sizeof(bool)*n);queueQ;//记录准备访问的结点Edge*edge;//记录当前遍历的结点intnIndex;//记录下标visited[StartEdge]=true;printf("startedge:%d\n",StartEdge);Q.push(StartEdge);while(!Q.empty()){edge=graph[Q.front()];while(edge){nIndex=edge->dest;if(!visited[nIndex]){visited[nIndex]=true;printf("%d\t",nIndex);Q.push(nIndex);}edge=edge->link;}Q.pop();}}intmain(){constintNODE_NUMBER=7;//10结点constintEDGE_NUMBER=11;//10边Edge**graph=newEdge*[NODE_NUMBER];//图memset(graph,0,sizeof(Edge*)*NODE_NUMBER);//一开始没边Input(graph,NODE_NUMBER,EDGE_NUMBER);//输入边printf("DFS:\n");DFS(graph,NODE_NUMBER,0);//深度优先printf("\n");printf("BFS:\n");BFS(graph,NODE_NUMBER,0);//广度优先printf("\n");return0;}2、邻接矩阵表示的图中利用bellman-ford算法获得单点最短路#include#includeusingnamespacestd;#defineINTEGER_INF0xffff//表示无穷大路径/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////Description:邻接矩阵表示的图structGraph{int**value;//权值intnumber;//结点个数};/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////Description:初始化图//Input:number-结点个数//Output:graph-图voidInitGraph(Graph&graph,intnumber){inti,j;graph.value=newint*[number];for(i=0;iv[i]+graph.value[i][j])//松弛v[j]=v[i]+graph.value[i][j];//判断是否存在边权和为负的环路for(i=0;iv[i]+graph.value[i][j])returnfalse;//输出for(t=1;t