当前位置：首页 > article >正文

PTA数据结构作业四

article 2025/1/4 6:25:40

7-10 判断两点之间是否存在路径

本题要求输出两个顶点之间是否存在路径

输入格式:

输入包括两部分，第一部分是邻接矩阵表示方法中对应1的两个顶点，用0 0 表示结束
第二部分是两个顶点，例如 Vi和Vj

输出格式:

如果Vi和Vj存在路径，输出1；否则输出0

输入样例:

输出样例:

#include <stdio.h>
#include <stdlib.h>
#define NOT 0

typedef struct GRAPHMATRIX_STRU{
    int size;
    int **graph;
}GraphMatrix;

//创建邻接矩阵并对邻接矩阵初始化 
GraphMatrix* InitGraph(int num){
	int i,j;
    GraphMatrix *graphMatrix=(GraphMatrix*)malloc(sizeof(GraphMatrix));
    graphMatrix->size=num;
    graphMatrix->graph=(int**)malloc(sizeof(int*)*graphMatrix->size);
    for(i=0;i<graphMatrix->size;i++){
    	graphMatrix->graph[i]=(int*)malloc(sizeof(int)*graphMatrix->size);
	} 
    for(i=0;i<graphMatrix->size;i++){
		for(j=0;j<graphMatrix->size;j++){
			graphMatrix->graph[i][j]=NOT;
		} 
    }
    return graphMatrix;
}
//存入邻接矩阵信息 
void ReadMatrix(GraphMatrix*graphMatrix){
    int vex1,vex2;
    scanf("%d%d",&vex1,&vex2);
    while(vex1!=0||vex2!=0){//如果输入都是0，则停止存入 
        graphMatrix->graph[vex1][vex2]=1;
        scanf("%d%d",&vex1,&vex2);
    }
}
//使用递归对邻接矩阵进行访问 
void IsOrNot(GraphMatrix *graphMatrix,int *visited,int source){
    int j;
    visited[source]=1;//若i节点被访问到，visited[i]=1
    for(j=0;j<graphMatrix->size;j++){
        if(graphMatrix->graph[source][j]!=NOT&&!visited[j]){
        	IsOrNot(graphMatrix,visited,j);
		} 
    }
}
int main(){
    int num=7;//节点个数可以自己定义，可以改为输入的方式
    int *visited=(int*)malloc(sizeof(int)*num);
    //需要对存储访问的变量初始化
    for(int i=0;i<num;i++){
    	visited[i] = 0;
	}
	int head,tail;
    GraphMatrix *graphMatrix;
    graphMatrix=InitGraph(num);
    ReadMatrix(graphMatrix);
    scanf("%d%d",&head,&tail);//判断head节点和tail节点是否来连通
    IsOrNot(graphMatrix,visited,head);
    //printf("%d\n",graphMatrix->graph[3][2]);
    if(visited[tail]==1){//若head节点和tail节点连通，则输出1，否则输出0；
    	printf("1");
	}
    else{
    	printf("0");
	}
    return 0;
}

7-11 判断一个有向图是否存在回路

本题要求编程判断一个有向图是否存在回路

输入格式:

输入是有向图的邻接矩阵表示中的1的相邻顶点，以-1 -1 结束

输出格式:

如果存在回路，输出1，否则输出0

输入样例:

输出样例:

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10

typedef struct{
	int vexs[MAXSIZE];
	int arc[MAXSIZE][MAXSIZE];
	int numVertexes;
}MGraph;

typedef struct EdgeNode{
	int adjVex;
	int weight;
	struct EdgeNode* next;
}EdgeNode;

typedef struct VertexNode{
	int in;
	int data;
	EdgeNode* firstEdge;
}VertexNode,AdjList[MAXSIZE];

typedef struct GraphAdjList{
	AdjList adjList;
	int vertexNums,edgeNums;
}GraphAdjList;
//构建图 
void CreateMGraph(MGraph *G){
	G->numVertexes = MAXSIZE;
	for(int i=0;i<G->numVertexes;i++){
		G->vexs[i] = i;
	}
	int vex1,vex2;
    scanf("%d%d",&vex1,&vex2);
    while(vex1!=-1||vex2!=-1){//如果输入都是0，则停止存入 
        G->arc[vex1][vex2] = 1;
        scanf("%d%d",&vex1,&vex2);
    }
}

// 利用邻接矩阵构建邻接表
void InitGraphADjList(MGraph *G, GraphAdjList *GL)
{
    GL->vertexNums = G->numVertexes;
    //GL->edgeNums = G->numEdges;

    for (int i = 0; i < G->numVertexes; i++) /* 读入顶点信息，建立顶点表 */
    {
        GL->adjList[i].in = 0;
        GL->adjList[i].data = G->vexs[i];
        GL->adjList[i].firstEdge = NULL; /* 将边表置为空表 */
    }

    for (int i = 0; i < G->numVertexes; i++) /* 建立边表 */
    {
        for (int j = 0; j < G->numVertexes; j++)
        {
            if (G->arc[i][j] == 1)
            {
                EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode));
                e->adjVex = j;                      /* 邻接序号为j  */
                e->next = GL->adjList[i].firstEdge; /* 将当前顶点上的指向的结点指针赋值给e */
                GL->adjList[i].firstEdge = e;       /* 将当前顶点的指针指向e  */
                GL->adjList[j].in++;
            }
        }
    }
}

int TopologicalSort(GraphAdjList *GL)
{
    int count = 0; // 用于统计输出顶点的个数
    // 用于存放入度为0的顶点
    int *stack = (int *)malloc(sizeof(int) * GL->vertexNums);
    int top = 0;
    // 入度为0的顶点入栈
    for (int i = 0; i < GL->vertexNums; i++)
    {
        if (GL->adjList[i].in == 0)
        {
            stack[++top] = i;

查看全文

http://www.kler.cn/a/460420.html