精华内容
下载资源
问答
  • 掌握图的邻接矩阵和邻接表存储结构; 掌握图的深度优先遍历和广度优先遍历算法,复习栈和队列的应用; 掌握图的最小生成树、拓扑排序应用及算法思想。 实验内容 以邻接矩阵或邻接表方式建立无向图,并分别利用...

    实验目的

    1. 掌握图的邻接矩阵和邻接表存储结构;
    2. 掌握图的深度优先遍历和广度优先遍历算法,复习栈和队列的应用;
    3. 掌握图的最小生成树、拓扑排序等应用及算法思想。

    实验内容

    以邻接矩阵或邻接表方式建立有向图,并分别利用深度优先遍历和广度优先遍历方法输出各结点元素。

    下面代码是用邻接表建立的有向图

    Source Code

    #include<stdio.h>
    #include<malloc.h>
    #define MAXV 100				//顶点数目的最大值 
    
    int visited[MAXV];				//深度访问标记数组 
    int BFSvisited[MAXV];			//广度访问标记数组 
    
    typedef struct ANode
    {	
    	int adjNode;	//该边的邻接点编号
    	ANode *next;	//指向下一条边的指针
    }ArcNode;	//边结点类型
    
    typedef struct Vnode
    {
    	char data;		//顶点信息
    	ArcNode *first;	//指向第一个边结点
    }VNode,AdjList[MAXV];	//头结点类型
     
    typedef struct
    {
    	AdjList vertices;
    	int n,e;//顶点数n和边数e
    }ALGraph;	//图邻接表类型
     
    //创建有向图 
    void CreateGraph(ALGraph &g){
    	printf("请输入顶点数和边数:");
    	int n,e;
    	scanf("%d%d",&n,&e);
    	g.n=n;
    	g.e=e;
    	for(int i=0;i<g.n;i++){
    		g.vertices[i].data=i;
    		g.vertices[i].first=NULL; 
    	}
    	printf("请输入每条边的两个顶点(用空格隔开)\n");
    	int x,y;
    	for(i=0;i<g.e;i++){
    		scanf("%d%d",&x,&y);
    		ArcNode *p =(ArcNode*)malloc(sizeof(ArcNode));
    		p->adjNode=y;
    		p->next=g.vertices[x].first;
    		g.vertices[x].first=p;
    		ArcNode *q=(ArcNode*)malloc(sizeof(ArcNode));
    		q->adjNode=x;
    		q->next=g.vertices[y].first;
    		g.vertices[y].first=q;
    	
    	}
    } 
     
    //深度优先遍历图,从第v个顶点开始遍历 
    void DFS(ALGraph g,int v)
    {
    	visited[v]=true;
    	printf("%d  ",g.vertices[v].data); 
    	ArcNode *p=g.vertices[v].first;
    	int w;
    	while(p!=NULL){
    		w=p->adjNode;
    		if(!visited[w]){
    			DFS(g,w);		//递归深度遍历 
    		}
    		p=p->next;
    	}
    } 
    
    //广度优先遍历借助队列,从v开始遍历 
    void BFS(ALGraph g,int v)
    {
    	BFSvisited[v]=true;
    	ArcNode *p;
    	printf("%d  ",g.vertices[v].data);
    	int que[MAXV];
    	int front=0,rear=0;
    	rear=(rear+1)%MAXV;
    	que[rear]= v;
    	int j;
    	while(rear!=front)	//当队列不空的时候
    	{						 
    		front=(front+1)%MAXV;//出队 
    		j =que[front];
    		p =g.vertices[j].first;
    		while(p!=NULL)
    		{
    			if(!BFSvisited[p->adjNode])
    			{
    				printf("%d  ",g.vertices[p->adjNode].data);
    				BFSvisited[p->adjNode]=true;
    				rear=(rear+1)%MAXV;
    				que[rear]=p->adjNode; 
    			}
    			p=p->next;//用的是邻接表,用p-next就可访问同层的相邻结点 
    			
    		}	
    	}
    }
    
    int main()
    {
    	ALGraph g;
    	CreateGraph(g);
    	printf("深度优先遍历顺序:\n"); 
    	DFS(g,0); 
    	printf("\n");
    	printf("广度优先遍历顺序:\n"); 
    	BFS(g,0);
    	printf("\n");
    } 
    
    

    Computational Results

    在这里插入图片描述

    Hint

    此代码遍历过程是从初始点0开始遍历的,对应的图是
    在这里插入图片描述

    展开全文
  • 有向边对暴雨顶点进行关联,记录暴雨状态之间的关系、变化速度、方向动态信息.最后,综合时间序列模型和空间拓扑关系,设计基于图的暴雨事件组织模型,基于Neo4j图存储方式R-Tree空间索引存储暴雨矢量数据集,并...
  • 一、图的种类和定义 ...常见的存储结构有邻接矩阵、邻接表、邻接多重表、十字链表。 二、图的表示方法 2.1图的邻接矩阵表示方法: 转载于:https://www.cnblogs.com/xleer/p/5628211.html...

    一、图的种类和定义

    图由顶点集和边集组成。

    主要有4种类型:无向图、有向图、无向网和有向网、

    常见的存储结构有邻接矩阵、邻接表、邻接多重表、十字链表等。

    二、图的表示方法

    2.1图的邻接矩阵表示方法:

     

    转载于:https://www.cnblogs.com/xleer/p/5628211.html

    展开全文
  • 熟悉各种图的存储结构(邻接矩阵和邻接表)。 掌握图的深度优先和广度优先遍历算法。 掌握克鲁斯卡尔算法生成最小生成树的方法。 掌握狄克斯特拉算法计算最短路径和最短路径长度的方法。 二、实验内容(或实验原理...

    一、实验目的及要求

    1. 熟悉各种图的存储结构(邻接矩阵和邻接表)。
    2. 掌握图的深度优先和广度优先遍历算法。
    3. 掌握克鲁斯卡尔算法生成最小生成树的方法。
    4. 掌握狄克斯特拉算法计算最短路径和最短路径长度的方法。

    二、实验内容(或实验原理、实验拓扑)

    1. 编写一个程序,输出下面带权有向图的邻接表,并根据该邻接表,实现图的深度优先遍历算法,具体要求如下:
      (1)从顶点0开始的深度优先遍历序列(递归算法)
      (2)从顶点0开始的深度优先遍历序列(非递归算法)

    三、实验设计方案(包括实验步骤、设计思想、算法描述或开发流程等)

    (一)在graph.h中创建图的邻接表存储结构:
    1.首先定义邻接表类型中的边结点类型ArcNode;
    2.然后定义邻接表头结点类型VNode;
    3.接着定义完整的图邻接表类型AdjGraph。
    (二)在main.cpp中完成图的基本运算算法:
    1. 创建图的邻接表CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e);
    2. 输出邻接表G DispAdj(AdjGraph G);
    3. 销毁图的邻接表DestroyAdj(AdjGraph *&G);
    4.定义全局函数visited[MAXV];
    5. 递归深度优先算法(AdjGraph *G,int v);
    6. 非递归深度优先算法DFS1(AdjGraph *G,int v);
    5.主函数 main()根据问题依次调用基本操作函数并编写通俗易懂的语句输出。

    四、实验结果(包括设计效果、测试数据、运行结果等)

    运行结果如下:

    五、实验小结(包括收获、心得体会、注意事项、存在问题及解决办法、建议等)

    从给定图中任意指定的顶点(称为初始点)出发,按照某种搜索方法沿着图的边访问图中的所有顶点,使每个顶点仅被访问一次,这个过程为图的遍历。深度优先搜索遍历的过程是:从图中某个初始顶点v出发,首先访问初始顶点v。然后选择一个与顶点v相邻且没被访问过的顶点w为初始顶点,再从w出发进行深度优先搜索,直到图中与当前顶点v邻接的所有顶点都被访问过为止。

    六、附录(包括作品、流程图、源程序及命令清单等)

    graph.h:
    //图的邻接表存储结构
    #define INF 32767				//定义∞
    #define	MAXV 100				//最大顶点个数
    typedef char InfoType;
    //以下定义邻接表类型
    typedef struct ANode
    {	int adjvex;					//该边的邻接点编号
    	struct ANode *nextarc;		//指向下一条边的指针
    	int weight;					//该边的相关信息,如权值(用整型表示)
    } ArcNode;						//边结点类型
    typedef struct Vnode
    {	InfoType info;				//顶点其他信息
    	int count;					//存放顶点入度,仅仅用于拓扑排序
    	ArcNode *firstarc;			//指向第一条边
    } VNode;						//邻接表头结点类型
    typedef struct 
    {	VNode adjlist[MAXV];		//邻接表头结点数组
    	int n,e;					//图中顶点数n和边数e
    } AdjGraph;						//完整的图邻接表类型
    
    main.cpp:
    #include <stdio.h>
    #include <malloc.h>
    #include "graph.h"
    //----创建图的邻接表G----------------------------------
    void CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e) //创建图的邻接表
    {
    	int i,j;
    	ArcNode *p;
    	G=(AdjGraph *)malloc(sizeof(AdjGraph));
    	for (i=0;i<n;i++)								//给邻接表中所有头结点的指针域置初值
    		G->adjlist[i].firstarc=NULL;
    	for (i=0;i<n;i++)								//检查邻接矩阵中每个元素
    		for (j=n-1;j>=0;j--)
    			if (A[i][j]!=0 && A[i][j]!=INF)			//存在一条边
    			{	p=(ArcNode *)malloc(sizeof(ArcNode));	//创建一个结点p
    				p->adjvex=j;
    				p->weight=A[i][j];
    				p->nextarc=G->adjlist[i].firstarc;	//采用头插法插入结点p
    				G->adjlist[i].firstarc=p;
    			}
    	G->n=n; G->e=n;
    }
    //----输出邻接表G----------------------------------
    void DispAdj(AdjGraph *G)
    {
    	int i;
    	ArcNode *p;
    	for (i=0;i<G->n;i++)
    	{
    		p=G->adjlist[i].firstarc;
    		printf("%3d: ",i);
    		while (p!=NULL)
    		{
    			printf("%3d[%d]→",p->adjvex,p->weight);
    			p=p->nextarc;
    		}
    		printf("∧\n");
    	}
    }
    //----销毁图的邻接表----------------------------------
    void DestroyAdj(AdjGraph *&G)
    {	int i;
    	ArcNode *pre,*p;
    	for (i=0;i<G->n;i++)			//扫描所有的单链表
    	{	pre=G->adjlist[i].firstarc;	//p指向第i个单链表的首结点
    		if (pre!=NULL)
    		{	p=pre->nextarc;
    			while (p!=NULL)			//释放第i个单链表的所有边结点
    			{	free(pre);
    				pre=p; p=p->nextarc;
    			}
    			free(pre);
    		}
    	}
    	free(G);						//释放头结点数组
    }
    //----深度优先递归算法----------------------------------
    int visited[MAXV];						//全局数组
    void DFS(AdjGraph *G,int v)   //递归深度优先算法
    {
    	ArcNode *p;
    	visited[v]=1;                   	//置已访问标记
    	printf("%3d",v); 					//输出被访问顶点的编号
    	p=G->adjlist[v].firstarc;      		//p指向顶点v的第一条弧的弧头结点
    	while (p!=NULL)
    	{
    		if (visited[p->adjvex]==0)		//若p->adjvex顶点未访问,递归访问它
    			DFS(G,p->adjvex);
    		p=p->nextarc;              		//p指向顶点v的下一条弧的弧头结点
    	}
    }
    //----深度优先非递归算法----------------------------------
    void DFS1(AdjGraph *G,int v)   //非递归深度优先算法
    {
    	ArcNode *p;
    	ArcNode *St[MAXV];
    	int top=-1,w,i;
        for (i=0;i<G->n;i++)
    		visited[i]=0;		//顶点访问标志均置成0
    	printf("%3d",v);        //访问顶点v
    	visited[v]=1;
    	top++;                  //将顶点v的第一个相邻顶点进栈
    	St[top]=G->adjlist[v].firstarc;
    	while (top>-1)          //栈不空循环
    	{
    		p=St[top]; top--;   //出栈一个顶点作为当前顶点
    		while (p!=NULL)     //查找当前顶点的第一个未访问的顶点
    		{
    			w=p->adjvex;
    			if (visited[w]==0)
    			{
    				printf("%3d",w); //访问w
    				visited[w]=1;
    				top++;           //将顶点w的第一个顶点进栈
    				St[top]=G->adjlist[w].firstarc;
    				break;           //退出循环
    			}
    			p=p->nextarc;        //找下一个相邻顶点
    		}
    	}
    	printf("\n");
    }
    int main()
    {
    	AdjGraph *G;
    	int A[MAXV][MAXV]={
    		{0,5,INF,7,INF,INF},
    		{INF,0,4,INF,INF,INF},
    		{8,INF,0,INF,INF,9},
    		{INF,INF,5,0,INF,6},
    		{INF,INF,INF,5,0,INF},
    		{3,INF,INF,INF,1,0}};
    	int n=6, e=10;
    	CreateAdj(G,A,n,e);             //建立实验讲义中的邻接表
    	printf("图G的邻接表:\n");
    	DispAdj(G);                     //输出邻接表
    	printf("从顶点0开始的DFS(递归算法):\n");
    	DFS(G,0);printf("\n");
    	printf("从顶点0开始的DFS(非递归算法):\n");
    	DFS1(G,0);
    }
    
    展开全文
  • 图的存储结构主要邻接矩阵,邻接表,十字链表。笔者在这里主要介绍邻接矩阵和邻接表两种存储结构。并将分别采用两种存储方法去实现无向图的基本操作,包括加点,删点,加边,删边、深度优先遍历以及广度优先遍历...

    图的存储结构主要有邻接矩阵,邻接表,十字链表等。笔者在这里主要介绍邻接矩阵和邻接表两种存储结构。并将分别采用两种存储方法去实现无向图的基本操作,包括加点,删点,加边,删边、深度优先遍历以及广度优先遍历。(文末附完整代码)

    邻接矩阵部分

    主要包含如下函数
    void visit()
    该函数意在将标注数组初始化为false;(标志数组在dfs和bfs均有用到)
    void insert_node(char c) 加点函数
    void delete_node(char c) 删点函数
    insert_edge(char u, char v) 加边函数
    delete_edge(char u, char v) 删边函数
    bfs(int v) 广度优先遍历
    dfs(int u) 深度优先遍历
    每个函数的具体算法思想均在代码种给出注释
    以下为邻接矩阵的完整代码

    #include <iostream>
    #include <algorithm>
    #include <string.h> 
    #include <string>
    #include <cmath>
    #include <queue>
    #include <map>
    #include <vector>
    #include <cstdio>
    const int N = 100;
    
    using namespace std;
    
    int V, E;
    class matrix
    {
    private:
        int no, ed;
        char node[N];
        int edge[N][N];
        bool vis[N];
    
    public:
        matrix()
        {
            memset(edge, 0,sizeof(edge));
            for (int i = 0; i < N; ++i)
                node[i] = '#', vis[i] = false;
            no = ed = 0;
        }
        void visit()
        {
            for (int i = 0; i < N; ++i)
                vis[i] = false;
        }
        void insert_node(char c) //扩容
        /**
         * @description: 由于采用的是顺序表结构存储
         * 只需在设置一个记录结点个数的变量,每次新
         * 加入一个结点就顺序接在数组尾巴,然后记录
         * 结点个数的变量自增 1
         * @param {*char c}
         */
        {
            node[no++] = c;
        }
        void delete_node(char c)
        /**
         * @description: 顺序遍历存储结点的数组。直至找到该节点
         * 然后将该节点后面的数据全部往前移一个位置。同时记录边问题
         * 的数组也应将包含该节点边关系的对应数据行和列采取将后面的
         * 数据往前移动位置,以覆盖边数组种被删除结点的信息
         * @param {*char c}
         */
        {
            int i;
            for (i = 0; i < no; ++i)
                if (node[i] == c)
                    break;
            for (int j = i; j < no - 1; ++j)
                node[j] = node[j + 1];
            for (int k = 0; k < no; ++k)
                for (int j = i; j < no - 1; ++j)
                    edge[k][j] = edge[k][j + 1];
            for (int k = 0; k < no - 1; ++k)
                for (int j = i; j < no - 1; ++j)
                    edge[j][k] = edge[j + 1][k];
            no--;
        }
        void insert_edge(char u, char v)
        /**
         * @description: 通过设置两个变量x,y,顺序变量结点数组
         * 在找到相应结点后存储它的位置下标,然后在边数组中将其
         * 连接起来
         * @param {*char u, char v}
         */
        {
            int x = -1, y = -1; //不存在的情况
            for (int i = 0; i < no; ++i)
                if (node[i] == u)
                    x = i;
                else if (node[i] == v)
                    y = i;
            edge[x][y] = edge[y][x] = 1;
            ed++;
        }
        void delete_edge(char u, char v)
        /**
         * @description: 同加边操作,首先应找出两个结点对应的
         * 下标,然后在边数组中删除相应的边
         * @param {*char u, char v}
         */
        {
            int x = -1, y = -1; //不存在的情况
            for (int i = 0; i < no; ++i)
                if (node[i] == u)
                    x = i;
                else if (node[i] == v)
                    y = i;
            edge[x][y] = edge[y][x] = 0;
            ed--;
        }
        void bfs(int v)
        /**
         * @description: 广度优先遍历,借助队列来实现
         * 首先将开始结点V输出,同时将下标存入队列中,然后
         * 在队列不为空的情况下逐一出队队首元素,判断是否存在
         * 以该元素为起点的边,同时边的终点未被访问,若满足该
         * 两项条件则可以输出数据,并标记该节点已输出,然后将
         * 该结点入队,如此往复直至队列为空。
         * @param {*int v}
         */
        {
            queue<int> q;
            q.push(v);
            cout << node[v] << " ";
            vis[v] = true;
            while (!q.empty())
            {
                int u = q.front();
                q.pop();
                for (int i = 0; i < no; ++i)
                {
                    if (edge[u][i] == 1 && !vis[i])
                    {
                        cout << node[i] << " ";
                        vis[i] = true;
                        q.push(i);
                    }
                }
            }
        }
        void dfs(int u)
        /**
         * @description: 深度优先遍历。采用递归形式实现
         * 首先输出开始结点对应数据,然后顺序遍历以开始结点
         * 为起点的边,且边的终点尚未被访问过,则往下搜索,如此
         * 往复,直至输出全部结点
         * @param {*int u}
         */
        {
            cout << node[u] << " ";
            vis[u] = true;
            for (int i = 0; i < no; ++i)
                if (edge[u][i] == 1 && !vis[i])
                    dfs(i);
        }
        void display_node()
        /**
         * @description: 通过顺序遍历结点数组,以输出结点来进行展示
         */
        {
            for (int i = 0; i < no; ++i)
                cout << node[i] << " ";
            cout << endl;
        }
        void display_edge()
        /**
         * @description: 顺序遍历边数组,输出边信息来进行展示
         */
        {
            for (int i = 0; i < no; cout << endl, ++i)
                for (int j = 0; j < no; ++j)
                    cout << edge[i][j] << " ";
        }
    };
    void Matrix()
    {
        cout << "邻接矩阵:\n";
        matrix G;
        cout << "请输入点数,边数:\n";
        cin >> V >> E;
        cout << "请输入点\n";
        char cc, u, v;
        for (int i = 0; i < V; ++i)
        {
            cin >> cc;
            G.insert_node(cc);
        }
        cout << "请输入边\n";
        for (int i = 0; i < E; ++i)
        {
            cin >> u >> v;
            G.insert_edge(u, v);
        }
        G.display_node();
        G.display_edge();
        cout << "请输出宽搜结果\n";
        G.bfs(0);
        G.visit();
        cout << endl;
        cout << "请输出深搜结果\n";
        G.dfs(0);
        G.visit();
        cout << endl;
        cout << "请输入要删除的点的数及点\n";
        cin >> V;
        for (int i = 0; i < V; ++i)
        {
            cin >> cc;
            G.delete_node(cc);
        }
        cout << "请输入要删除的边的数及边\n";
        cin >> E;
        for (int i = 0; i < E; ++i)
        {
            cin >> u >> v;
            G.delete_edge(u, v);
        }
        G.display_node();
        G.display_edge();
    }
    int main()
    {
        int _ = 1;
        //sf(_);
        while (_--)
        {
            Matrix();
        }
    
        return 0;
    }
    

    邻接表部分

    主要实现思想同邻接矩阵,这里就不再赘述,直接放代码,代码中包含了详细注释

    #include <iostream>
    #include <algorithm>
    #include <string.h> 
    #include <string>
    #include <cmath>
    #include <queue>
    #include <map>
    #include <vector>
    #include <cstdio>
    const int N = 100;
    
    using namespace std;
    
    int V, E;
    typedef struct arcnode
    {
        struct arcnode *next;
        int vex;
        arcnode(const int &d) : vex(d), next(NULL) {}
    } arcnode;
    typedef struct node
    {
        char ve;
        arcnode *fir = new arcnode(0);
    } arclist[N];
    class arc
    {
    private:
        arclist ar;
        int no, ed;
        bool vis[N];
    
    public:
        arc()
        {
            no = ed = 0;
            for (int i = 0; i < 100; ++i)
                ar[i].ve = '#';
        }
        void visit()
        {
            for (int i = 0; i < 100; ++i)
                vis[i] = false;
        }
        void insert_node(char c)
        /**
         * @description: 由于采用的是顺序表结构存储
         * 只需在设置一个记录结点个数的变量,每次新
         * 加入一个结点就顺序接在数组尾巴,然后记录
         * 结点个数的变量自增 1
         * @param {*char c}
         */
        {
            ar[no++].ve = c;
        }
        void delete_node(char c)
        /**
         * @description: 首先在结点数组中找到要删除结点的下标,然后
         * 将该结点后面的数据均往前移动一个位置以覆盖数据,从而达到删除
         * 该结点目的。同时在邻接表中也要删除对应的边关系,首先将该节点
         * 的边关系的存储链表删除,然后遍历其他每一个结点的存储边关系的
         * 存储链表,找到其中包含该节点的下标的结点,将其删去,同时对大于
         * 该节点的其他数据,若存储下标大于它,则应自减 1
         * @param {*char c}
         */
        {
            int i;
            for (i = 0; i < no; ++i)
                if (ar[i].ve == c)
                    break;
            for (int j = i; j < no - 1; ++j)
                ar[j] = ar[j + 1];
            no--;
            for (int k = 0; k < no; ++k)
            {
                arcnode *T = ar[k].fir;
                while (T->next)
                {
                    if (T->next->vex == i)
                    {
                        if (T->next->next)
                            T->next = T->next->next;
                        else
                            T->next = NULL;
                        break;
                    }
                    else if (T->next->vex > i)
                    {
                        T->next->vex--;
                        T = T->next;
                    }
                    else
                        T = T->next;
                }
            }
        }
        void insert_edge(char u, char v)
        /**
         * @description: 首先应找到边对应两个结点的存储下标。然后分别
         * 在以u为起点的存储边关系的链表中连接v;然后在以v为起点的存储
         * 边关系的链表中连接u
         * @param {*char u, char v}
         */
        {
            int x = -1, y = -1;
            for (int i = 0; i < no; ++i)
                if (ar[i].ve == u)
                    x = i;
                else if (ar[i].ve == v)
                    y = i;
            arcnode *p = new arcnode(0);
            p->vex = y;
            arcnode *q = ar[x].fir;
            while (q->next)
                q = q->next;
            p->next = q->next;
            q->next = p;
    
            arcnode *r = new arcnode(0);
            r->vex = x;
            q = ar[y].fir;
            while (q->next)
                q = q->next;
            r->next = q->next;
            q->next = r;
    
            ed++;
        }
        void delete_edge(char u, char v)
        /**
         * @description: 
         * 删边操作同删点操作的思想
         * @param {*char u, char v}
         */
        {
            int x = -1, y = -1;
            for (int i = 0; i < no; ++i)
                if (ar[i].ve == u)
                    x = i;
                else if (ar[i].ve == v)
                    y = i;
            arcnode *T = ar[x].fir;
            while (T->next)
                if (T->next->vex != y)
                    T = T->next;
                else
                {
                    if (T->next->next)
                        T->next = T->next->next;
                    else
                        T->next = NULL;
                    break;
                }
    
            T = ar[y].fir;
            while (T->next)
                if (T->next->vex != y)
                    T = T->next;
                else
                {
                    if (T->next->next)
                        T->next = T->next->next;
                    else
                        T->next = NULL;
                    break;
                }
            ed--;
        }
    
        void bfs(int u)
        {
            queue<int> q;
            int v;
            cout << ar[u].ve << " ";
            q.push(u);
            vis[u] = true;
            while (!q.empty())
            {
                v = q.front();
                q.pop();
                arcnode *p = ar[v].fir;
                while (p->next)
                {
                    p = p->next;
                    if (!vis[p->vex])
                    {
                        cout << ar[p->vex].ve << " ";
                        vis[p->vex] = true;
                        q.push(p->vex);
                    }
                }
            }
        }
        void dfs(int u)
        {
            cout << ar[u].ve << " ";
            vis[u] = true;
            arcnode *p = ar[u].fir;
            while (p->next)
            {
                p=p->next;
                if (!vis[p->vex])
                    dfs(p->vex);
            }
        }
    
        void display_edge()
        {
            cout << "修改后的结果" << endl;
            for (int i = 0; i < no; cout << endl, ++i)
            {
                cout << ar[i].ve << "  :";
                arcnode *T = new arcnode(0);
                T = ar[i].fir->next;
                while (T)
                {
                    cout << T->vex << " ";
                    T = T->next;
                }
                delete T;
            }
        }
    };
    void Arc()
    {
        cout << "邻接表:\n";
        arc g;
        cout << "请输入点数,边数:\n";
        cin >> V >> E;
        cout << "请输入点\n";
        char cc, u, v;
        for (int i = 0; i < V; ++i)
        {
            cin >> cc;
            g.insert_node(cc);
        }
        cout << "请输入边\n";
        for (int i = 0; i < E; ++i)
        {
            cin >> u >> v;
            g.insert_edge(u, v);
        }
        g.display_edge();
        cout << "请输出宽搜结果\n";
        g.visit();
        g.bfs(0);
        cout << endl;
        cout << "请输出深搜结果\n";
        g.visit();
        g.dfs(0);
        cout << endl;
        cout << "请输入要删除的点的数及点\n";
        cin >> V;
        for (int i = 0; i < V; ++i)
        {
            cin >> cc;
            g.delete_node(cc);
        }
        g.display_edge();
        cout << "请输入要删除的边的数及边\n";
        cin >> E;
        for (int i = 0; i < E; ++i)
        {
            cin >> u >> v;
            g.delete_edge(u, v);
        }
        g.display_edge();
    }
    
    int main()
    {
        int _ = 1;
        //sf(_);
        while (_--)
        {
            Arc();
        }
    
        return 0;
    }
    
    展开全文
  • 1.问题描述: 创建一个至少有15个点的有向网表示的某个旅游景点的导游图。顶点代表景点,类型为字符串(例如,泰山导游图:“天地广场门”,“十八盘”,“冯玉祥墓”,“桃花峪门”,...(1)创建图的存储结构。...
  • 常用线性结构有:线性表,栈,队列,循环队列,数组。线性表中包括顺序表、链表,其中,栈和队列只是属于逻辑上概念,实际中不存在,仅仅是一种思想&#...
  • 概念:无向图、有向图、带权图、顶点、边、度、入度、出度; 图的两个主要的存储方式:邻接矩阵和邻接表。 接矩阵存储方法的缺点是比较浪费空间,但是优点是查询效率高,而且方便矩阵运算。邻接表存储方法中每个顶点...
  • 数据结构算法演示(Windows版) 使 用 手 册 一、 功能简介 本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可...图示窗口自上而下分别显示有向图的逻辑结构、存储结构和 Finished 数组在算法执行过程...
  • 数据结构与算法

    2020-07-02 15:41:55
    非线性结构:树、有向,无向) 存储结构是逻辑结构到物理存储空间映射,存储结构包含四类:顺序、链接、索引、散列。 散列:一种特殊索引结构。通多所要查关键码一个映射,能够在整个散列表里快速地找到...
  • 数据结构复习—1.1

    2019-04-06 23:49:00
    一、什么是数据结构 结构:实体+关系 数据结构: 1、按照逻辑关系组织起来的一批路径 ...2、按一定存储方法把他存储在计算机中 ... 图(有向图、无向图)  三、数据的存储结构 四类:顺序、链接、索...
  • 大话数据结构

    2019-01-10 16:35:22
    7.4图的存储结构 223 因为美国的黑夜就是中国的白天,利用互联网,他的员工白天上班就可以监控到美国仓库夜间的实际情况,如果发生了像火灾、偷盗这样的突发事件,及时电话到美国当地相关人员处理 7.4.1邻接矩阵 224...
  • 图是一种很常见的数据结构,对图的分析首先要从其...如图中aa,bb,cc,dd,ee均可为无穷(也可以是1)表示二者不通(通),而ab,ac根据图的信息进行赋值,本图为有向有权图,因此赋其权值。 另外一种方法是邻接
  • 3.5.4 字符数据在内存中的存储形式及使用方法 41 3.5.5 字符串常量 41 3.5.6 符号常量 42 3.6 变量赋初值 42 3.7 各类数值型数据之间的混合运算 43 3.8 算术运算符和算术表达式 44 3.8.1 C运算符简介 44 3.8.2 算术...
  • 大话数据结构 程杰

    2018-09-01 10:06:43
    7.4图的存储结构 223 因为美国的黑夜就是中国的白天,利用互联网,他的员工白天上班就可以监控到美国仓库夜间的实际情况,如果发生了像火灾、偷盗这样的突发事件,及时电话到美国当地相关人员处理 7.4.1邻接矩阵 224...
  • 数据结构演示软件

    2013-06-02 21:32:36
    (2)求有向图的强连通分量(Strong_comp) (3)有向无环图的两个算法  拓扑排序(Toposort)  关键路径(Critical_path) (4)求最小生成树  普里姆算法(Prim)  克鲁斯卡尔算法(Kruscal) (5)求关节点...
  • 5.5串的存储结构 128 感情上发生了问题,为了女友解释一下,我准备发一条短信,一共打了75个字。最后八个字是“我恨你是不可能的”,点发送。后来得知对方收到的,只有70个字,短信结尾是“……我恨你”。 5.5.1串...
  • 大话数据结构-程杰

    2014-07-13 23:45:52
    6.7 二叉树的存储结构 172 6.7.1 二叉树顺序存储结构 172 6.7.2 二叉链表 173 6.8 遍历二叉树 174 你人生的道路上,高考填志愿要面临哪个城市、哪所大学、具体专业选择,由于选择方式的不同,遍历的次序就完全...
  • pb文件保存方法 使用 tf.train.Saver 会保存运行 TensorFlow 程序所需要全部信息,然而有时并不需要某些...而且,将变量取值和计算图结构分成不同文件存储有时候也不方便,于是 TensorFlow 提供了 convert_var...
  • 7.4图的存储结构 223 因为美国的黑夜就是中国的白天,利用互联网,他的员工白天上班就可以监控到美国仓库夜间的实际情况,如果发生了像火灾、偷盗这样的突发事件,及时电话到美国当地相关人员处理 7.4.1邻接矩阵 224...
  • 7.2.1 各种图定义 214 7.2.2 图的顶点与边间关系 217 7.2.3 连通图相关术语 219 7.2.4 图的定义与术语总结 222 7.3 图的抽象数据类型 222 7.4 图的存储结构 223 因为美国的黑夜就是中国的白天,利用互联网,他的...
  • 10、说出ArrayList,Vector, LinkedList的存储性能和特性  ArrayList 和Vector都是使用数组方式存储数据,此数组元素数大于实际存储的数据以便增加和插入元素,它们都允许直接按序号索引元素,但是插入元素要涉及...
  • 数据结构

    2012-12-27 16:58:40
    8.有向图的邻接矩阵中,每列元素之和为该顶点的( ) A.度 B.入度 C.出度 D.权值 9.100个结点完全二叉树高度是( ) A.9 B.10 C.11 D.12 10.n个顶点的无向完全图中含有向边的数目最多为( ) A.n-1 B.n C.n(n-1)/2 D.n...
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    有向图 D.字符串 14.以下数据结构中,(A )是非线性数据结构【中山大学 1999 一、4】 A.树 B.字符串 C.队 D.栈 15. 下列数据中,(C )是非线性数据结构。【北京理工大学 2001 六、1(2分)】 A.栈 B. ...
  • 若一个有向图的邻接矩阵中,对角线以下元素均为0,则该图的拓扑有序序列必定存在。( ) 二叉树可以用0≤度≤2的有序树来表示。 非空双向循环链表中由q所指的结点后面插入一个由p指的结点的动作依次为:p->prior=q, p...
  • 7.2 图的存储结构 7.2.1 数组表示法 7.2.2 邻接表 7.2.3 十字链表 7.2.4 邻接多重表 7.3 图的遍历 7.3.1 深度优先搜索 7.3.2 广度优先搜索 7.4 图的连通性问题 7.4.1 无向图的连通分量和生成树 7.4.2 有向图的强连通...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    4、用邻接矩阵或邻接图实现一个有向图的存储,并实现单源最短路径算法的实现(这个类的一个成员函数),并能输出该图的关键路径。 注:1、要用面向对象的方法设计代码; 2、一个图是一个类的实例; 3、类...

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 238
精华内容 95
关键字:

有向图的存储结构有等方法