精华内容
下载资源
问答
  • 无向图以邻接矩阵存储,请算法描述深度优先遍历该图的非递归算法。哪位大神可以帮忙具体点用栈怎么实现?谢谢了!![图片说明](http://forum.csdn.net/PointForum/ui/scripts/csdn/Plugin/001/face/1.gif)
  • 内容:(1)请参照图的邻接矩阵模板类原型,设计并逐步完善图的邻接矩阵ADT。(由于该环境目前仅支持单文件的编译,故将所有内容都集中在一个源文件内。在实际的设计中,推荐将抽象类及对应的派生类分别放在单独的

    问题描述 :

    目的:使用C++模板设计并逐步完善图的邻接矩阵抽象数据类型(ADT)。

    内容:(1)请参照图的邻接矩阵模板类原型,设计并逐步完善图的邻接矩阵ADT。(由于该环境目前仅支持单文件的编译,故将所有内容都集中在一个源文件内。在实际的设计中,推荐将抽象类及对应的派生类分别放在单独的头文件中。)

    (2)设计并实现一个算法,对于给定图中的任意两个顶点,检查它们之间是否有路径存在。如路径存在,返回true;否则返回false。图的存储结构采用邻接矩阵。将其加入到ADT中。

    提示:可以通过深度优先搜索(DFS)来实现。从起点开始深度优先搜索。在搜索过程中如遇到终点,则返回true。如果遍历了所有的路径都没有遇到终点,则返回false。

    注意:DG(有向图), DN(有向网), UDG(无向图), UDN(无向网)

    参考函数原型:

    //检查两个结点之间是否有路径存在(外壳部分,公有成员函数) 
    
    template<class TypeOfVer, class TypeOfEdge>
    
    bool adjmatrix_graph<TypeOfVer, TypeOfEdge>::CheckRoute(int u, int v);
    
    
    
    //检查两个结点之间是否有路径存在(递归部分,私有成员函数) 
    
    template<class TypeOfVer, class TypeOfEdge>
    
    bool adjmatrix_graph<TypeOfVer, TypeOfEdge>::CheckRoute(int u, int v, int visited[]);
    

    输入说明 :

    第一行:图的类型

    第二行:结点数

    第三行:结点集

    第四行:边数

    第五行:边集

    第六行:起点u

    第七行:终点v

    输出说明 :

    第一行:顶点集

    空行

    第二行:邻接矩阵

    空行

    第三行:true(路径存在)/false(路径不存在)

    输入范例 :

    DG
    4
    A B C D
    4
    0 1
    0 2
    2 3
    3 1
    1
    0
    

    输出范例 :

    A B C D
    
    0 1 1 0 
    0 0 0 0 
    0 0 0 1 
    0 1 0 0 
    
    false
    

    思路分析

    • 基本上实在深度遍历上进行修改的
    • 深度遍历的每次递归的执行操作是输出,本函数中就是判定当前节点是否等于目标节点
    • 深度函数唯一返回条件就是访问完所有的与初始结点联通的结点之后自动结束程序,退出,返回false
    • 但是搜索找到目标就直接返回,中断函数,不需要再继续进行遍历

    在这里插入图片描述

    • 这里要直接退出

    实现伪码

    /*
        描述:检查两个结点之间是否有路径存在(外壳部分,公有成员函数)
    */
    bool CheckRoute(int u, int v){
    
         //初始化记录是否访问的路径数组
        int visited[Vers] = {0},num = 0;
    
        //判定传入的值是否符合规定
        CheckRoute(u,v,visited);
    
    
    }
    
    /*
        描述:检查两个结点之间是否有路径存在(递归部分,私有成员函数)
    */
    bool CheckRoute(int u, int v, int visited[]){
    
        //找到了目标的结点,就返回真
        if(u == v)    return true;
    
        //判定过就修改是否访问的标记
        visited[u] = 1;
    
        //如果没有找到并且所有节点都已经访问过了,就是没找到
        bool flag = false//找第一个邻接结点
        int nextGoal = GetFirst(u,nextGoal);
    
        //只要找到了,先去判定
        while(nextGoal != -1){
    
            //判定是否被访问过
            if(visited[nextGoal] == 0){
               flag = CheckRoute(nextGoal,v,visited);
               //如果找到了直接返回true,退出循环,结束函数
               if(flag)
                    return true;
            }
            //如果访问过了,再找下一个子节点
            nextGoal = GetNext(u,nextGoal,nextGoal);
        }
        return flag;
        //全部都访问了,直接返回
    }
    

    事故现场

    在这里插入图片描述

    • 有两个终止条件要处理好
    • 一个是所有的点都被遍历过之后,已经没有可遍历的点,就退出》》这个条件是递归的最终的返回结果,不需要添加
    • 另一个是找到目标,直接退出,不再进行下一步的遍历》》这里要注意

    分析总结

    • 看着群里的大佬参加各种比赛,计算机应用大赛。。。。我却什么都不会,深感惭愧,只能在这里写一些基本的数据结构基本的实验,不知道意义在哪里。但是确实转过来有点吃力,基本的专业课都没有怎么学完。心有余而力不足。。。。

    但是不管怎么只能继续写了,如有不妥请留言,或者加本人的扣扣651378276,虽然我很菜,但是还是可以商量一下,一块进步的

    展开全文
  • 最近复习考研遇到了图的问题,发现自己对这一块的数据结构不怎么熟悉,于是自己全部手写了一遍。我的可能和一些官方标准不太一样(毕竟教材上也没有非常明确的官方标准),但基本思路是一样的,自己测试的一些数据也...

           最近复习考研遇到了图的问题,发现自己对这一块的数据结构不怎么熟悉,于是自己全部手写了一遍。我写的可能和一些官方标准不太一样(毕竟教材上也没有非常明确的官方标准),但基本思路是一样的,自己测试的一些数据也没有问题,如果谁发现了问题欢迎指出。

           图一共有四个基本存储结构,分别是邻接矩阵,邻接表,十字链表,邻接多重表。它们各有各自的特点,我将这四个存储结构全部实现了一遍,并针对每个结构都实现了以下11个基本功能:

    1. 初始化
    2. 插入顶点
    3. 删除顶点
    4. 插入边(弧)
    5. 删除边(弧)
    6. 判断a,b两点是否联通
    7. 列出所有与顶点a邻接的边
    8. 返回顶点a的第一个邻接点的顶点号
    9. 假设顶点b是顶点a的一个邻接点,返回除b之外顶点a的下一个邻接点的顶点号
    10. 获取边(a,b)或弧<a,b>的权值
    11. 设置边(a,b)或弧<a,b>的权值

    邻接矩阵(有向)

    struct AdjacencyMatrix//邻接矩阵
    {
    	int inf = 0x3f3f3f3f;//设一个无穷大用来表示不连通的弧的权值
    	int V_num;//顶点数量
    	int V_max;//顶点最大ID
    	bool V[105];//V[i]表示顶点i是否存在
    	int MA[105][105];//图矩阵
    	void init()//初始化
    	{
    		V_num = 0;
    		V_max = 0;
    		memset(V, false, sizeof(V));
    		memset(MA, 0x3f, sizeof(MA));
    	}
    	void insert_vertex(int a)//插入顶点
    	{
    		if (a > V_max)
    			V_max = a;
    		if (!V[a])
    		{
    			V[a] = true;
    			V_num++;
    		}
    	}
    	void delete_vertex(int a)//删除顶点
    	{
    		if (!V[a])
    			return;
    		for (int i = 0; i <= V_max; i++)//同时将该顶点的弧删除,即权值设为无穷大
    		{
    			MA[i][a] = inf;
    			MA[a][i] = inf;
    		}
    		if (a == V_max)
    		{
    			for (int i = V_max - 1; i >= 0; i--)
    				if (V[i])
    				{
    					V_max = i;
    					break;
    				}
    			if (V_max == a)
    				V_max = 0;
    		}
    		V[a] = false;
    		V_num--;
    	}
    	void add_edge(int a, int b, int weight)//插入弧
    	{
    		insert_vertex(a);
    		insert_vertex(b);
    		MA[a][b] = weight;
    	}
    	void remove_edge(int a, int b)//删除弧
    	{
    		MA[a][b] = inf;
    	}
    	bool adjacent(int a, int b)//判断a,b是否连通
    	{
    		if (MA[a][b] < inf)
    			return true;
    		else
    			return false;
    	}
    	void neighbors(int a)//列出所有与a邻接的弧
    	{
    		for (int i = 0; i <= V_max; i++)
    			if (adjacent(a,i))
    				printf("%d---%d\n", a, i);
    	}
    	int first_neighbor(int a)//返回顶点a的第一个邻接点,没有则返回-1
    	{
    		for (int i = 0; i <= V_max; i++)
    			if (adjacent(a, i))
    				return i;
    		return -1;
    	}
    	int next_neighbor(int a, int b)//返回顶点a的在b之后的下一个邻接点,没有则返回-1
    	{
    		for (int i = b+1; i <= V_max; i++)
    			if (adjacent(a, i))
    				return i;
    		return -1;
    	}
    	int get_edge_value(int a, int b)//获取a到b的弧的权值
    	{
    		return MA[a][b];
    	}
    	void set_edge_value(int a, int b, int v)//设定a到b的弧的权值
    	{
    		MA[a][b] = v;
    	}
    };

    邻接表(有向)

    struct AdjacencyArcNode//邻接表的弧结点
    {
    	int weight;//该弧的权重
    	int destination;//该弧的弧头
    	struct AdjacencyArcNode* next;//指向下一条邻接弧
    };
    
    struct AdjacencyVNode//邻接表的顶点表
    {
    	bool exist;//表示顶点是否存在
    	struct AdjacencyArcNode* first;//弧表头指针
    	void delete_edge(int a)//删除该顶点对应的边表中到点a的弧
    	{
    		struct AdjacencyArcNode* last;
    		struct AdjacencyArcNode* p = first;
    		if (p->destination == a)
    		{
    			first = p->next;
    			free(p);
    		}
    		last = p;
    		p = p->next;
    		while (p->destination!=a)
    		{
    			last = p;
    			p = p->next;
    			if (p == NULL)
    				return;
    		}
    		last->next = p->next;
    		free(p);
    	}
    	void clear(struct AdjacencyArcNode* p)//清空该顶点的弧表
    	{
    		if (p->next != NULL)
    			clear(p->next);
    		free(p);
    	}
    	void append_edge(int a,int v)//给该顶点添加一条弧
    	{
    		struct AdjacencyArcNode* n = (AdjacencyArcNode*)malloc(sizeof(AdjacencyArcNode));
    		struct AdjacencyArcNode* p = first;
    		n->destination = a;
    		n->next = NULL;
    		n->weight = v;
    		if (p == NULL)
    		{
    			first = n;
    			return;
    		}
    		while (p->next != NULL)
    			p = p->next;
    		p->next = n;
    	}
    };
    
    struct AdjacencyList
    {
    	int V_num;//顶点数量
    	int V_max;//顶点最大ID
    	AdjacencyVNode V[105];//顶点表
    	void init()//初始化
    	{
    		V_num = 0;
    		V_max = 0;
    		for (int i = 0; i < 105; i++)
    		{
    			V[i].exist = false;
    			V[i].first = NULL;
    		}
    	}
    	void insert_vertex(int a)//插入顶点
    	{
    		if (a > V_max)
    			V_max = a;
    		if (!V[a].exist)
    		{
    			V[a].exist = true;
    			V_num++;
    		}
    	}
    	void delete_vertex(int a)//删除顶点
    	{
    		if (!V[a].exist)
    			return;
    		AdjacencyArcNode* p, *p1, *p2;
    		p = V[a].first;
    		while (p!=NULL)//删除别的顶点中包含该顶点的弧
    		{
    			V[p->destination].delete_edge(a);
    			p = p->next;
    		}
    		V[a].clear(V[a].first);//删除该顶点自己的弧
    		V[a].exist = false;
    		if (a == V_max)
    		{
    			for (int i = V_max - 1; i >= 0; i--)
    				if (V[i].exist)
    				{
    					V_max = i;
    					break;
    				}
    			if (V_max == a)
    				V_max = 0;
    		}
    		V[a].exist = false;
    		V_num--;
    	}
    	void add_edge(int a, int b, int weight)//插入弧
    	{
    		insert_vertex(a);
    		insert_vertex(b);
    		V[a].append_edge(b, weight);
    	}
    	void remove_edge(int a, int b)//删除弧
    	{
    		V[a].delete_edge(b);
    	}
    	bool adjacent(int a, int b)//判断a,b是否联通
    	{
    		AdjacencyArcNode* p = V[a].first;
    		while (p!=NULL)
    		{
    			if (p->destination == b)
    				return true;
    			p = p->next;
    		}
    		return false;
    	}
    	void neighbors(int a)//列出所有与a邻接的弧
    	{
    		for (int i = 0; i <= V_max; i++)
    			if (adjacent(a, i))
    				printf("%d---%d\n", a, i);
    	}
    	int first_neighbor(int a)//返回顶点a的第一个邻接点,没有则返回-1
    	{
    		for (int i = 0; i <= V_max; i++)
    			if (adjacent(a, i))
    				return i;
    		return -1;
    	}
    	int next_neighbor(int a, int b)//返回顶点a的在b之后的下一个邻接点,没有则返回-1
    	{
    		for (int i = b + 1; i <= V_max; i++)
    			if (adjacent(a, i))
    				return i;
    		return -1;
    	}
    	int get_edge_value(int a, int b)//获取a到b的弧的权值
    	{
    		AdjacencyArcNode* p = V[a].first;
    		while (p != NULL)
    		{
    			if (p->destination == b)
    				return p->weight;
    			p = p->next;
    		}
    		return -1;
    	}
    	void set_edge_value(int a, int b, int v)//设定a到b的弧的权值
    	{
    		AdjacencyArcNode* p = V[a].first;
    		while (p != NULL)
    		{
    			if (p->destination == b)
    			{
    				p->weight = v;
    				break;
    			}
    			p = p->next;
    		}
    	}
    };

    十字链表(有向)

    struct OrthogonalArcNode//十字链表的弧结点
    {
    	int weight;//该弧的权重
    	int tailvex;//该弧的尾部
    	int headvex;//该弧的头部
    	struct OrthogonalArcNode* tailnext;//下一个尾部与该弧尾部相同的弧
    	struct OrthogonalArcNode* headnext;//下一个头部与该弧头部相同的弧
    };
    
    struct OrthogonalVNode//十字链表的顶点结点
    {
    	bool exist;//该顶点是否存在
    	struct OrthogonalArcNode* tailfirst;//以该点为尾的弧
    	struct OrthogonalArcNode* headfirst;//以该点为头的弧
    	void delete_edge_to(int a)//删除从该点到a点的弧
    	{
    		struct OrthogonalArcNode* last;
    		struct OrthogonalArcNode* p = tailfirst;
    		if (p->headvex == a)
    		{
    			tailfirst = p->tailnext;
    			return;
    		}
    		last = p;
    		p = p->tailnext;
    		while (p->headvex != a)
    		{
    			last = p;
    			p = p->tailnext;
    			if (p == NULL)
    				return;
    		}
    		last->tailnext = p->tailnext;
    	}
    	void delete_edge_from(int a)//删除从a点到该点的弧
    	{
    		struct OrthogonalArcNode* last;
    		struct OrthogonalArcNode* p = headfirst;
    		if (p->tailvex == a)
    		{
    			headfirst = p->headnext;
    			return;
    		}
    		last = p;
    		p = p->headnext;
    		while (p->tailvex != a)
    		{
    			last = p;
    			p = p->headnext;
    			if (p == NULL)
    				return;
    		}
    		last->headnext = p->headnext;
    	}
    	void append_to(OrthogonalArcNode* a)//增加从该点到a点的弧
    	{
    		OrthogonalArcNode* p = tailfirst;
    		if (p == NULL)
    		{
    			tailfirst = a;
    			return;
    		}
    		while (p->tailnext!=NULL)
    			p = p->tailnext;
    		p->tailnext = a;
    		return;
    	}
    	void append_from(OrthogonalArcNode* a)//增加从a点到该点的弧
    	{
    		OrthogonalArcNode* p = headfirst;
    		if (p == NULL)
    		{
    			headfirst = a;
    			return;
    		}
    		while (p->headnext != NULL)
    			p = p->headnext;
    		p->headnext = a;
    		return;
    	}
    };
    
    struct OrthogonalList//十字链表
    {
    	int V_num;//顶点数目
    	int V_max;//顶点最大ID
    	OrthogonalVNode V[105];//顶点表
    	void init()//初始化
    	{
    		V_num = 0;
    		V_max = 0;
    		for (int i = 0; i < 105; i++)
    		{
    			V[i].exist = false;
    			V[i].headfirst = NULL;
    			V[i].tailfirst = NULL;
    		}
    	}
    	void insert_vertex(int a)//插入顶点
    	{
    		if (a > V_max)
    			V_max = a;
    		if (!V[a].exist)
    		{
    			V[a].exist = true;
    			V_num++;
    		}
    	}
    	void delete_vertex(int a)//删除顶点
    	{
    		if (!V[a].exist)
    			return;
    		OrthogonalArcNode* p;
    		p = V[a].tailfirst;
    		while (p != NULL)//删除以该点为弧尾的弧
    		{
    			V[p->headvex].delete_edge_from(a);
    			V[a].delete_edge_to(p->headvex);
    			p = p->tailnext;
    		}
    		p = V[a].headfirst;
    		while (p != NULL)//删除以该点为弧头的弧
    		{
    			V[p->tailvex].delete_edge_to(a);
    			V[a].delete_edge_from(p->tailvex);
    			p = p->headnext;
    		}
    		V[a].exist = false;
    		if (a == V_max)
    		{
    			for (int i = V_max - 1; i >= 0; i--)
    				if (V[i].exist)
    				{
    					V_max = i;
    					break;
    				}
    			if (V_max == a)
    				V_max = 0;
    		}
    		V[a].exist = false;
    		V_num--;
    	}
    	void add_edge(int a, int b, int weight)//插入弧
    	{
    		insert_vertex(a);
    		insert_vertex(b);
    		OrthogonalArcNode* p = (OrthogonalArcNode*)malloc(sizeof(OrthogonalArcNode));
    		p->tailvex = a;
    		p->headvex = b;
    		p->weight = weight;
    		p->headnext = NULL;
    		p->tailnext = NULL;
    		V[a].append_to(p);
    		V[b].append_from(p);
    	}
    	void remove_edge(int a, int b)//删除弧
    	{
    		V[a].delete_edge_to(b);
    		V[b].delete_edge_from(a);
    	}
    	bool adjacent(int a, int b)//判断a,b是否联通
    	{
    		OrthogonalArcNode* p = V[a].tailfirst;
    		while (p != NULL)
    		{
    			if (p->headvex == b)
    				return true;
    			p = p->tailnext;
    		}
    		return false;
    	}
    	void neighbors(int a)//列出所有与a邻接的弧
    	{
    		for (int i = 0; i <= V_max; i++)
    			if (adjacent(a, i))
    				printf("%d---%d\n", a, i);
    	}
    	int first_neighbor(int a)//返回顶点a的第一个邻接点,没有则返回-1
    	{
    		for (int i = 0; i <= V_max; i++)
    			if (adjacent(a, i))
    				return i;
    		return -1;
    	}
    	int next_neighbor(int a, int b)//返回顶点a的在b之后的下一个邻接点,没有则返回-1
    	{
    		for (int i = b + 1; i <= V_max; i++)
    			if (adjacent(a, i))
    				return i;
    		return -1;
    	}
    	int get_edge_value(int a, int b)//获取a到b的弧的权值
    	{
    		OrthogonalArcNode* p = V[a].tailfirst;
    		while (p != NULL)
    		{
    			if (p->headvex == b)
    				return p->weight;
    			p = p->tailnext;
    		}
    		return -1;
    	}
    	void set_edge_value(int a, int b, int v)//设定a到b的弧的权值
    	{
    		OrthogonalArcNode* p = V[a].tailfirst;
    		while (p != NULL)
    		{
    			if (p->headvex == b)
    			{
    				p->weight = v;
    				break;
    			}
    			p = p->tailnext;
    		}
    	}
    };

    邻接多重表(无向)

    struct AdjacencyMultilistArcNode//邻接多重表的边结点
    {
    	bool mark;//标志域
    	int weight;//该边的权重
    	int Avex;//该边依附的一个顶点A
    	int Bvex;//该边依附的另一个顶点B
    	struct AdjacencyMultilistArcNode* Anext;//指向下一条依附于顶点A的边
    	struct AdjacencyMultilistArcNode* Bnext;//指向下一条依附于顶点B的边
    };
    
    struct AdjacencyMultilistVNode//邻接多重表的顶点结点
    {
    	int id;//该顶点的编号
    	bool exist;//该顶点是否存在
    	struct AdjacencyMultilistArcNode* first;//该顶点的边表
    	void delete_edge(int a)//从该顶点的边表中删除与a相连的边
    	{
    		bool lastvex;//Avex:true Bvex:false
    		struct AdjacencyMultilistArcNode* last;
    		struct AdjacencyMultilistArcNode* p = first;
    		if (p->Avex == id)
    		{
    			if (p->Bvex == a)
    			{
    				first = p->Anext;
    				return;
    			}
    			lastvex = true;
    			last = p;
    			p = p->Anext;
    		}
    		else
    		{
    			if (p->Avex == a)
    			{
    				first = p->Bnext;
    				return;
    			}
    			lastvex = false;
    			last = p;
    			p = p->Bnext;
    		}
    		while (p != NULL)
    		{
    			if (p->Bvex != a && p->Avex == id)
    			{
    				last = p;
    				lastvex = true;
    				p = p->Anext;
    			}
    			else if (p->Avex != a && p->Bvex == id)
    			{
    				last = p;
    				lastvex = false;
    				p = p->Bnext;
    			}
    			else if (p->Avex == a && p->Bvex == id)
    			{
    				if (lastvex)
    					last->Anext = p->Bnext;
    				else
    					last->Bnext = p->Bnext;
    				return;
    			}
    			else if (p->Bvex == a && p->Avex == id)
    			{
    				if (lastvex)
    					last->Anext = p->Anext;
    				else
    					last->Bnext = p->Anext;
    				return;
    			}
    		}
    	}
    	void append(AdjacencyMultilistArcNode* a)//添加该点与点a的一条边
    	{
    		struct AdjacencyMultilistArcNode* p = first;
    		if (p == NULL)
    		{
    			first = a;
    			return;
    		}
    		while (p!=NULL)
    		{
    			if (p->Avex == id)
    			{
    				if (p->Anext == NULL)
    				{
    					p->Anext = a;
    					return;
    				}
    				p = p->Anext;
    			}
    			else
    			{
    				if (p->Bnext == NULL)
    				{
    					p->Bnext = a;
    					return;
    				}
    				p = p->Bnext;
    			}
    		}
    	}
    };
    
    struct AdjacencyMultilist//邻接多重表
    {
    	int V_num;//顶点数目
    	int V_max;//顶点最大ID
    	AdjacencyMultilistVNode V[105];//顶点表
    	void init()//初始化
    	{
    		V_num = 0;
    		V_max = 0;
    		for (int i = 0; i < 105; i++)
    		{
    			V[i].exist = false;
    			V[i].first = NULL;
    			V[i].id = i;
    		}
    	}
    	void insert_vertex(int a)//插入顶点
    	{
    		if (a > V_max)
    			V_max = a;
    		if (!V[a].exist)
    		{
    			V[a].exist = true;
    			V_num++;
    		}
    	}
    	void delete_vertex(int a)//删除顶点
    	{
    		if (!V[a].exist)
    			return;
    		AdjacencyMultilistArcNode* p;
    		p = V[a].first;
    		while (p != NULL)
    		{
    			if (p->Avex == a)
    			{
    				V[a].delete_edge(p->Bvex);
    				V[p->Bvex].delete_edge(a);
    				p = p->Anext;
    			}
    			else
    			{
    				V[a].delete_edge(p->Avex);
    				V[p->Avex].delete_edge(a);
    				p = p->Bnext;
    			}
    		}
    		V[a].exist = false;
    		if (a == V_max)
    		{
    			for (int i = V_max - 1; i >= 0; i--)
    				if (V[i].exist)
    				{
    					V_max = i;
    					break;
    				}
    			if (V_max == a)
    				V_max = 0;
    		}
    		V[a].exist = false;
    		V_num--;
    	}
    	void add_edge(int a, int b, int weight)//插入一条边
    	{
    		insert_vertex(a);
    		insert_vertex(b);
    		AdjacencyMultilistArcNode* p = (AdjacencyMultilistArcNode*)malloc(sizeof(AdjacencyMultilistArcNode));
    		p->Avex = a;
    		p->Bvex = b;
    		p->weight = weight;
    		p->Anext = NULL;
    		p->Bnext = NULL;
    		V[a].append(p);
    		V[b].append(p);
    	}
    	void remove_edge(int a, int b)//删除一条边
    	{
    		V[a].delete_edge(b);
    		V[b].delete_edge(a);
    	}
    	bool adjacent(int a, int b)//判断a,b是否联通
    	{
    		if (a == b)
    			return false;
    		AdjacencyMultilistArcNode* p = V[a].first;
    		while (p != NULL)
    		{
    			if (p->Avex == b || p->Bvex == b)
    				return true;
    			if (p->Avex == a)
    				p = p->Anext;
    			else
    				p = p->Bnext;
    		}
    		return false;
    	}
    	void neighbors(int a)//列出所有与a邻接的边
    	{
    		for (int i = 0; i <= V_max; i++)
    			if (adjacent(a, i))
    				printf("%d---%d\n", a, i);
    	}
    	int first_neighbor(int a)//返回顶点a的第一个邻接点,没有则返回-1
    	{
    		for (int i = 0; i <= V_max; i++)
    			if (adjacent(a, i))
    				return i;
    		return -1;
    	}
    	int next_neighbor(int a, int b)//返回顶点a的在b之后的下一个邻接点,没有则返回-1
    	{
    		for (int i = b + 1; i <= V_max; i++)
    			if (adjacent(a, i))
    				return i;
    		return -1;
    	}
    	int get_edge_value(int a, int b)//获取边(a,b)的权值
    	{
    		AdjacencyMultilistArcNode* p = V[a].first;
    		while (p != NULL)
    		{
    			if (p->Avex == b || p->Bvex == b)
    				return p->weight;
    			if (p->Avex == a)
    				p = p->Anext;
    			else
    				p = p->Bnext;
    		}
    		return -1;
    	}
    	void set_edge_value(int a, int b, int v)//设定边(a,b)的权值
    	{
    		AdjacencyMultilistArcNode* p = V[a].first;
    		while (p != NULL)
    		{
    			if (p->Avex == b || p->Bvex == b)
    			{
    				p->weight = v;
    				break;
    			}
    			if (p->Avex == a)
    				p = p->Anext;
    			else
    				p = p->Bnext;
    		}
    	}
    };
    

     

    展开全文
  • 出入度 邻接表邻接矩阵 拓扑排序 DFS Kahn算法出入度一般指是在有向(DAG)中,某个顶点,箭头指向它为入度...邻接表、邻接矩阵邻接表这个东西也可以看【1】中是怎么写这个邻接矩阵的,我更推荐是看【2】中鱼c

    转载请注明出处:http://blog.csdn.net/c602273091/article/details/55511145

    出入度

    图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。

    各种图的概念请看:【6】

    无向边:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边(Edge),用无序偶(Vi,Vj)来表示。
    有向边:若从顶点Vi到Vj的边有方向,则称这条边为有向边,也成为弧(Arc),用有序偶< Vi,Vj>来表示,Vi称为弧尾,Vj称为弧头。
    简单图:在图结构中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图。
    无向完全图:在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。含有n个顶点的无向完全图有n*(n-1)/2条边。
    有向完全图:在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。含有n个顶点的有向完全图有n*(n-1)条边。
    稀疏图和稠密图:这里的稀疏和稠密是模糊的概念,都是相对而言的,通常认为边或弧数小于n*logn(n是顶点的个数)的图称为稀疏图,反之称为稠密图。
    有些图的边或弧带有与它相关的数字,这种与图的边或弧相关的数叫做权(Weight),带权的图通常称为网(Network)。

    然后介绍度,以顶点V为头的弧的数目称为V的入度(InDegree),记为ID(V),以V为尾的弧的数目称为V的出度(OutDegree),记为OD(V),因此顶点V的度为TD(V)=ID(V)+OD(V)。一般指的是在有向图(DAG)中,某个顶点,箭头指向它的为入度,从这个顶点出发,指向别的顶点的边就是出度。有几条这样的边,度就是多大。看【7】中的图有详细的介绍。

    如果一个有向图恰有一个顶点入度为0,其余顶点的入度均为1,则是一棵有向树。

    可以参考【1】中生成出入度的代码。不过【1】中是认为无向图中一条边既是入度、也是出度。所以这里的计算会有些许不同。

    邻接表、邻接矩阵

    邻接表这个东西也可以看【1】中是怎么写这个邻接矩阵的,我更推荐的是看【2】中鱼c的文章。写得非常好。

    其实邻接表和邻接矩阵是离散数学的必修内容,现在就是对它进行一个复习。

    首先邻接矩阵的纵轴坐标就是各个边的初始顶点,横坐标就是各个边的箭头的的位置。如果存在i->j这条边,那么就使矩阵M(i, j) = 1,否则为0。

    邻接表是另外一种记录图的数据结构。因为图是稀疏的话,那么邻接矩阵就会使得存储很浪费,使用邻接表存储更加节约空间。如果图是稠密的话,使用邻接表是一种不错的方式。

    在这里强烈推荐这个博客,写得非常好,非常简单易懂【3】【8】。

    在图的存储结构中,还有十字链表、邻接多重表、边集数组。
    边集数组:边集数组是由两个一维数组构成,一个是存储顶点的信息,另一个是存储边的信息,这个边数组每个数据元素由一条边的起点下标(begin)、终点下标(end)和权(weight)组成【9】。

    另外在【11】中,对图的表示举了比较简单的例子。

    拓扑排序

    拓扑排序我觉得就是一个有向无环图的问题。有向无环这就是拓扑图的充要条件。

    在计算拓扑图方面,有DFS和Kahn算法。这里我主要是参考了【4】

    DFS

    从wiki上获取它的伪代码为:

    L ← Empty list that will contain the sorted nodes
    S ← Set of all nodes with no outgoing edges
    for each node n in S do
        visit(n)
    
    function visit(node n)
        if n has not been visited yet then
            mark n as visited
            for each node m with an edge from m to n do
                visit(m)
            add n to L

    具体的代码实现为:

    public class DirectedDepthFirstOrder
    {
        // visited数组,DFS实现需要用到
        private boolean[] visited;
        // 使用栈来保存最后的结果
        private Stack<Integer> reversePost;
    
        /**
         * Topological Sorting Constructor
         */
        public DirectedDepthFirstOrder(Digraph di, boolean detectCycle)
        {
            // 这里的DirectedDepthFirstCycleDetection是一个用于检测有向图中是否存在环路的类
            DirectedDepthFirstCycleDetection detect = new DirectedDepthFirstCycleDetection(
                    di);
    
            if (detectCycle && detect.hasCycle())
                throw new IllegalArgumentException("Has cycle");
    
            this.visited = new boolean[di.getV()];
            this.reversePost = new Stack<Integer>();
    
            for (int i = 0; i < di.getV(); i++)
            {
                if (!visited[i])
                {
                    dfs(di, i);
                }
            }
        }
    
        private void dfs(Digraph di, int v)
        {
            visited[v] = true;
    
            for (int w : di.adj(v))
            {
                if (!visited[w])
                {
                    dfs(di, w);
                }
            }
    
            // 在即将退出dfs方法的时候,将当前顶点添加到结果集中
            reversePost.push(v);
        }
    
        public Iterable<Integer> getReversePost()
        {
            return reversePost;
        }
    }

    Kahn算法

    Kahn的伪代码为:

    L← Empty list that will contain the sorted elements
    S ← Set of all nodes with no incoming edges
    while S is non-empty do
        remove a node n from S
        insert n into L
        foreach node m with an edge e from nto m do
            remove edge e from thegraph
            ifm has no other incoming edges then
                insert m into S
    if graph has edges then
        return error (graph has at least onecycle)
    else 
        return L (a topologically sortedorder)

    它的具体实现为:

    public class KahnTopological
    {
        private List<Integer> result;   // 用来存储结果集
        private Queue<Integer> setOfZeroIndegree;  // 用来存储入度为0的顶点
        private int[] indegrees;  // 记录每个顶点当前的入度
        private int edges;
        private Digraph di;
    
        public KahnTopological(Digraph di)
        {
            this.di = di;
            this.edges = di.getE();
            this.indegrees = new int[di.getV()];
            this.result = new ArrayList<Integer>();
            this.setOfZeroIndegree = new LinkedList<Integer>();
    
            // 对入度为0的集合进行初始化
            Iterable<Integer>[] adjs = di.getAdj();
            for(int i = 0; i < adjs.length; i++)
            {
                // 对每一条边 v -> w 
                for(int w : adjs[i])
                {
                    indegrees[w]++;
                }
            }
    
            for(int i = 0; i < indegrees.length; i++)
            {
                if(0 == indegrees[i])
                {
                    setOfZeroIndegree.enqueue(i);
                }
            }
            process();
        }
    
        private void process()
        {
            while(!setOfZeroIndegree.isEmpty())
            {
                int v = setOfZeroIndegree.dequeue();
    
                // 将当前顶点添加到结果集中
                result.add(v);
    
                // 遍历由v引出的所有边
                for(int w : di.adj(v))
                {
                    // 将该边从图中移除,通过减少边的数量来表示
                    edges--;
                    if(0 == --indegrees[w])   // 如果入度为0,那么加入入度为0的集合
                    {
                        setOfZeroIndegree.enqueue(w);
                    }
                }
            }
            // 如果此时图中还存在边,那么说明图中含有环路
            if(0 != edges)
            {
                throw new IllegalArgumentException("Has Cycle !");
            }
        }
    
        public Iterable<Integer> getResult()
        {
            return result;
        }
    }

    在【4】中还涉及了哈密顿路径,可以看看,写得不错。作者总结了其中DFS和Kahn的算法不同点以及前提条件。DFS是要先证明不存在环才可以使用,Kahn不需要。

    DFS的检测闭环和拓扑排序写在一起就是:

    public class DirectedDepthFirstTopoWithCircleDetection
    {
        private boolean[] visited;
        // 用于记录dfs方法的调用栈,用于环路检测
        private boolean[] onStack;
        // 用于当环路存在时构造之
        private int[] edgeTo;
        private Stack<Integer> reversePost;
        private Stack<Integer> cycle;
    
        /**
         * Topological Sorting Constructor
         */
        public DirectedDepthFirstTopoWithCircleDetection(Digraph di)
        {
            this.visited = new boolean[di.getV()];
            this.onStack = new boolean[di.getV()];
            this.edgeTo = new int[di.getV()];
            this.reversePost = new Stack<Integer>();
    
            for (int i = 0; i < di.getV(); i++)
            {
                if (!visited[i])
                {
                    dfs(di, i);
                }
            }
        }
    
        private void dfs(Digraph di, int v)
        {
            visited[v] = true;
            // 在调用dfs方法时,将当前顶点记录到调用栈中
            onStack[v] = true;
    
            for (int w : di.adj(v))
            {
                if(hasCycle())
                {
                    return;
                }
                if (!visited[w])
                {
                    edgeTo[w] = v;
                    dfs(di, w);
                }
                else if(onStack[w])
                {
                    // 当w已经被访问,同时w也存在于调用栈中时,即存在环路
                    cycle = new Stack<Integer>();
                    cycle.push(w);
                    for(int start = v; start != w; start = edgeTo[start])
                    {
                        cycle.push(v);
                    }
                    cycle.push(w);
                }
            }
    
            // 在即将退出dfs方法时,将顶点添加到拓扑排序结果集中,同时从调用栈中退出
            reversePost.push(v);
            onStack[v] = false;
        }
    
        private boolean hasCycle() 
        {
            return (null != cycle);
        }
    
        public Iterable<Integer> getReversePost()
        {
            if(!hasCycle())
            {
                return reversePost;
            }
            else 
            {
                throw new IllegalArgumentException("Has Cycle: " + getCycle());
            }
        }
    
        public Iterable<Integer> getCycle() 
        {
            return cycle;
        }
    }

    这两种方法的复杂度都是O(E+V)。

    最后推荐程序员必须会的10种算法这篇文章:【5】

    207. Course Schedule

    题目描述

    There are a total of n courses you have to take, labeled from 0 to n - 1.

    Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

    Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

    For example:

    2, [[1,0]]

    There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

    2, [[1,0],[0,1]]

    There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

    Note:
    The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
    You may assume that there are no duplicate edges in the input prerequisites.

    代码实现

    class Solution {
    public:
        int findPos(vector<int> rem, int num) {
            int remsz = rem.size();
            for(int i = 0; i < remsz; i++) 
                if(rem[i] == num) return i;
            return - 1;    
        }
    
        bool canFinish(int numCourses, vector<pair<int, int>>& pre) {
            int num[10000] = {0}, nump = pre.size();
            queue<int> stt;
            vector<int> rem;
            for(int i = 0; i < nump; i++)  { 
                if(num[pre[i].second] == 0) num[pre[i].second] = -1;
                if(num[pre[i].first] == -1 || num[pre[i].first] == 0)  num[pre[i].first] = 1;
                else  num[pre[i].first]++; 
            }    
            for(int i = 0; i < numCourses; i++) {  
                if(num[i] == -1)  stt.push(i); 
                else if(num[i] > 0) rem.push_back(i); 
            }    
            while(!stt.empty()) {
                int remsz = rem.size();
                if(!remsz) break;            
                int tp = stt.front();
                stt.pop();
                for(int i = 0; i < nump; i++) {
                    if(pre[i].second == tp) { 
                        num[pre[i].first]--;
                        if(!num[pre[i].first]) {
                            stt.push(pre[i].first);
                            rem.erase(rem.begin() + findPos(rem, pre[i].first));
                        }    
                    }
                }
            }
    
            return rem.empty();
        }
    };

    上面使用的就是Kahn算法实现的课程调度。

    在【10】里面,提出了BFS和DFS的实现。

    BFS:

    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
            vector<int> degrees = compute_indegree(graph);
            for (int i = 0; i < numCourses; i++) {
                int j = 0;
                for (; j < numCourses; j++)
                    if (!degrees[j]) break;
                if (j == numCourses) return false;
                degrees[j] = -1;
                for (int neigh : graph[j])
                    degrees[neigh]--;
            }
            return true;
        }
    private:
        vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<unordered_set<int>> graph(numCourses);
            for (auto pre : prerequisites)
                graph[pre.second].insert(pre.first);
            return graph;
        }
        vector<int> compute_indegree(vector<unordered_set<int>>& graph) {
            vector<int> degrees(graph.size(), 0);
            for (auto neighbors : graph)
                for (int neigh : neighbors)
                    degrees[neigh]++;
            return degrees;
        }
    }; 

    DFS:

    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
            vector<bool> onpath(numCourses, false), visited(numCourses, false);
            for (int i = 0; i < numCourses; i++)
                if (!visited[i] && dfs_cycle(graph, i, onpath, visited))
                    return false;
            return true;
        }
    private:
        vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<unordered_set<int>> graph(numCourses);
            for (auto pre : prerequisites)
                graph[pre.second].insert(pre.first);
            return graph;
        } 
        bool dfs_cycle(vector<unordered_set<int>>& graph, int node, vector<bool>& onpath, vector<bool>& visited) {
            if (visited[node]) return false;
            onpath[node] = visited[node] = true; 
            for (int neigh : graph[node])
                if (onpath[neigh] || dfs_cycle(graph, neigh, onpath, visited))
                    return true;
            return onpath[node] = false;
        }
    };

    参考链接:
    对于各种算法的一个总结:

    【1】图的邻接矩阵及出入度的计算方法:http://m.blog.csdn.net/article/details?id=9078919
    【2】邻接表和邻接矩阵:http://blog.fishc.com/2523.html
    【3】学习数据结构不错的网站:http://blog.fishc.com/category/structure
    【4】拓扑排序的介绍:http://m.blog.csdn.net/article/details?id=7714519
    【5】程序员十大算法:http://www.wtoutiao.com/p/1c2pI1k.html
    【6】图的入门:http://blog.fishc.com/2485.html
    【7】图的介绍:http://blog.fishc.com/2499.html
    【8】邻接矩阵:http://blog.fishc.com/2514.html
    【9】图的特殊的存储结构:http://blog.fishc.com/2535.html
    【10】BFS/DFS的课程调度实现:https://discuss.leetcode.com/topic/17273/18-22-lines-c-bfs-dfs-solutions
    【11】图的表示:https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs

    展开全文
  • 今天在写图的算法时,想到如果要实现了求一个节点相邻的节点,该怎么写:稀疏图是邻接表实现的:稠密图是邻接矩阵实现的:问题:得到g这个变量进行操作,保持g变量的私有特性,而又让外部能遍历到这个数据?...

    今天在写图的算法时,想到如果要实现了求一个节点相邻的节点,该怎么写:

    稀疏图是邻接表实现的:


    稠密图是邻接矩阵实现的:



    问题:

    得到g这个变量进行操作,保持g变量的私有特性,而又让外部能遍历到这个数据?

    用模板方法来统一接口,这样外部调用统一的接口就可以访问这个点所有相邻点的集合了。

    邻接矩阵:
    // 返回图中一个顶点的所有邻边
        public Iterable<Integer> adj(int v) {
            assert v >= 0 && v < n;
            Vector<Integer> adjV = new Vector<Integer>();
            for(int i = 0 ; i < n ; i ++ )
                if( g[v][i] )
                    adjV.add(i);
            return adjV;
        }
    邻接表:
    // 返回图中一个顶点的所有邻边
        public Iterable<Integer> adj(int v) {
            assert v >= 0 && v < n;
            return g[v];
        }

    这样,在统一调用时,就无需知道内部是什么,也不需要稀疏图和稠密图分开调用了,调用统一接口就可以了:

     public static void main(String[] args) {
    
            // 使用两种图的存储方式读取testG1.txt文件
            String filename = "F:\\Algorithm-Base\\src\\wang\\Graph\\testG1.txt";
            SparseGraph g1 = new SparseGraph(13, false);
            ReadGraph readGraph1 = new ReadGraph(g1, filename);
            for(int i = 0; i < g1.V(); i ++){
                Iterator<Integer> iter = g1.adj(i).iterator();
                System.out.print("第" + i + "个顶点所相邻的结点:");
                while(iter.hasNext()){
                    System.out.print(iter.next() + " ");
                }
                System.out.println();
            }
    }

    test1的数据是:

      

    输出的结果:



    总结: 有时候写代码时,应该多想想这个代码的整体性,是不是可以多个相同的方法可以写成一个模板,提供一个统一的接口是调用~

    展开全文
  • 图的基本存储的基本方式四

    千次阅读 2016-04-05 19:49:10
    题目着用邻接矩阵,实际上用前向星或邻接表来过,弱还不会前向星,只会邻接表。。。。 图的基本存储的基本方式四 Time Limit: 2500MS Memory limit: 10000K 题目描述 解决图论问题,...
  • 数据结构算法之

    2013-12-09 22:22:03
    这次数据结构的实验是建立一个无向非连通图的邻接表存储结构 。 让同学发了一个代码给我赖得打字了。。这二货的是邻接矩阵。。 还得自己 先说一下,还有一种图是邻接矩阵。是通过存储各顶点之间的邻接关系而形成...
  • 虽然用邻接矩阵表示非常简单,但它也有些不可忽视缺点。比如 矩阵大小不好提前预知,动态数组话又不好实现。 如果是稀疏话,也造成空间浪费。 邻接表就要好很多。实现数据结构要怎么设计?先试着去一下...
  • 这道题我第一次接触时候还不怎么了解并查集,所以那时候第一想法就是用邻接表或者邻接矩阵实现,but自己太菜了邻接矩阵和邻接表也不好,由于就去网上找了模板直接使用 在后来我学习了并查集后,也没有回忆起...
  • 编程实现如下功能:输入有向图的顶点数、边数及各条边的...建立用邻接矩阵表示的有向图。报告中要先画出有向图,然后根据你画的有向图编程。 怎么写,要求自己画有向图 急求 大神,救命啊</p>
  • 用c语言实现基本数据结构(

    千次阅读 2019-03-08 11:43:12
    c语言实现基本数据结构() ...邻接矩阵表示法 邻接表表示法 十字链表表示法 临界多重表表示法 我只了邻接表表示法和十字链表表示法。第一个很简单,最后一个不经常用。 下面是邻接表表示法结构体 ...
  • 一个编号在1000内m条边的图,求从s到t恰好经过D...没有重边,提示我们构造邻接矩阵,最短路可以用floyd求出,但怎么用Floyd来“限边”??? 在原邻接矩阵,即“走一步最短路”中,以原邻接矩阵为路径,floyd走一...
  • 今天终于学会了匈牙利算法,手撕代码时候却出了问题,难受。链式前向星这种东西大家怎么都知道,就我菜不知道,...如果说邻接表是不好但效率好,邻接矩阵是好但效率低话,前向星。前向星固然好些,但效率并不
  • 作业记录之Floyed 其实是个数据结构作业啦!干脆在这里,加深印象(干脆之后就不复习了吧(不 妈妈这人怎么这么懒呀 为什么老师布置作业要用Floyed...因为老师主要检验有向图,所以的程序是有向图的邻接矩阵 ...
  • 十字链表及其C++实现

    千次阅读 多人点赞 2018-05-13 01:10:30
    十字链表理解大概一共有4中存储方式:邻接矩阵,邻接表,边集数组,十字链表。其实前三种数据结构都十分得好理解,尤其是邻接矩阵。大概所有人都是从这个数据结构开始入门图论。他也确实...
  • 待起飞の集训8.5

    2017-08-05 21:09:50
    看懂了prim算法,今天做了两个这种题目类型,就是讲n个点用一条线连起来,这条线要最短,即最小生成树问题,一个题是求最短路径中最长一段,两一个是求最小路径长度,首先邻接矩阵,lowcost[],v[],从第一个...
  • [Rqnoj-192]梦幻大PK

    2012-01-06 17:38:33
    二分最大匹配问题,用邻接矩阵就足够了,但我写的邻接表,那个back指针的用法很有趣,还有就是sap算法里面,回溯时,要栈顶的指针弹出来,刚开始调试怎么也没注意到这一点,后来看了一下以前的代码,瞬间AC~ ...
  • POJ 2728 Desert King

    2016-01-18 20:41:39
    最优比例生成树。...于是果断弃疗用邻接矩阵。 由于懒得学Dinkelbach算法,于是就用二分来水一水。 不妨设F(L)=sigma(h[i]-l[i]*L)*x[i],假如F(L)最小值大于0,即无论x[i]怎么取(要按照基本法来),都
  • POJ2396 Budget

    2018-12-11 09:58:00
    嘟嘟嘟 上下界网络流之可行流。 对于这种矩阵题,做过就应该知道怎么...建图虽然不难,但起来比较麻烦,因为数据较小,推荐邻接矩阵存每一条边最小最大容量,这样方便更新取最紧限制。 刚开始我WA了是为了...
  • 大话数据结构

    2018-12-14 16:02:18
    7.4.1邻接矩阵 224 7.4.2邻接表 228 7.4.3十字链表 232 7.4.4邻接多重表 234 7.4.5边集数组 236 7.5图的遍历 237 我有一天早晨准备出门,发现钥匙不见了。一定是我儿子拿着玩,不知道丢到哪个犄角旮旯去了,...
  • 设G是有向向图的邻接矩阵,若 边,j> 不存在,则G[i][j]=Maxint S[v]为真当且仅当v属于S,即已求得从v1到v的最短路经 */ void Dijkstra(MGraph G,int v1,int n) { int D2[MVNum],P2[MVNum]; int v,i,w,min; ...

空空如也

空空如也

1 2
收藏数 22
精华内容 8
关键字:

图的邻接矩阵怎么写