- 浏览: 735945 次
- 性别:
- 来自: 嘉兴
文章分类
- 全部博客 (386)
- Struts1.1 (2)
- Database (18)
- Core Java (15)
- Log4j (4)
- SSH (0)
- Dao (1)
- Architecture Design (1)
- References (2)
- Eclipse&MyEclipse (10)
- Hibernate (7)
- Spring (8)
- JavaMail (1)
- Data Structure And Algorithm (48)
- Struts 2 (2)
- SSI (1)
- SSL (2)
- JSTL (1)
- EJB3 (2)
- NET (2)
- XML (2)
- Components (2)
- Ant (3)
- Multi Thread (1)
- Performance Monitoring (1)
- Web Server (17)
- Oracle (1)
- jQuery (8)
- Regular Expression (1)
- Weblogic (1)
- Exception (1)
- Security (2)
- File Manipulation (1)
- JavaScript (12)
- JVM (2)
- HTML&DIV&CSS (4)
- Android (10)
- Beyond GFW (0)
- Business (0)
- SVN (6)
- 虚拟主机 (1)
- Virtual Host (3)
- My mentality (5)
- OS (15)
- ISPMP (3)
- Magento (5)
- Jsoup&HttpClient (7)
- LINUX (9)
- Database Design (0)
- Power Designer (1)
- TaobaoOpenPlatform (2)
- C/C++ (3)
- Maven (11)
- Quartz (1)
- Load Balance (1)
- Zabbix (4)
- Product&Business (1)
- Pay Interface (1)
- Tomcat (2)
- Redis (1)
- 集群 (1)
- Session (1)
- 共享Session (1)
- Jedis (1)
- jenkins (1)
- 持续集成 (1)
- Web前端 (1)
最新评论
-
aqq331325797:
特意注册账号上来说一句。牛逼!
swagger2.2.2 与 spring cloud feign冲突 -
KitGavinx:
跨顶级域名怎么保持sessionid一致?
Tomcat7集群共享Session 基于redis进行统一管理 -
jaychang:
dujianqiao 写道HI ,能否给一个完整的demo 啊 ...
淘宝订单同步方案 - 丢单终结者 -
GGGGeek:
找了一会儿,感觉mybatis应该没有这种操作,直到发现博主的 ...
mybatis collection list string -
dujianqiao:
HI ,能否给一个完整的demo 啊 ?
淘宝订单同步方案 - 丢单终结者
#include<iostream> #define MAX_VERTEX_NUM 50 using namespace std; typedef char VerType; typedef struct ArcNode //定义弧结点所在位置, { int adj; int info; ArcNode *next; }ArcNode; typedef struct VerNode //定义顶点(顶点数据,顶点所指向第一条弧的指针) { VerType data; ArcNode *first; }VerNode; typedef struct AdjList //图的定义 { VerNode VerNodes[MAX_VERTEX_NUM]; //顶点集 int verNum,arcNum; //顶点数,弧数 }AdjList; typedef struct Queue //FIFO队列 { int Item[MAX_VERTEX_NUM]; int front,rear; }Queue; int visited[MAX_VERTEX_NUM]; //顶点访问标志数组 //定位某一结点的位置,找不到返回0 int LocateGraph(AdjList *g,char data) { for(int i=1;i<=g->verNum;i++) { if(g->VerNodes[i].data==data) return i; } return 0; } //初始化队列 void InitQueue(Queue *Q) { for(int i=1;i<=MAX_VERTEX_NUM;i++) { Q->Item[i]=0; } Q->front=Q->rear=1; } //创建图的邻接表 void CreateAdjList(AdjList *g) { int s,d,weigth; char sChar,dChar; ArcNode *q=NULL; cout<<"输入图的顶点数,弧数\n"; cin>>g->verNum>>g->arcNum; cout<<"输入每个顶点的信息\n"; //初始化顶点 for(int i=1;i<=g->verNum;i++) { cin>>g->VerNodes[i].data; g->VerNodes[i].first=NULL; } //初始化弧 for(i=1;i<=g->arcNum;i++) { cout<<"输入第"<<i<<"条弧的起始,目的,弧的权值"<<endl; cin>>sChar>>dChar>>weigth; s=LocateGraph(g,sChar); d=LocateGraph(g,dChar); //定位该顶点的位置 q=(ArcNode *)malloc(sizeof(ArcNode)); q->adj=d;q->info=weigth; q->next=g->VerNodes[s].first; g->VerNodes[s].first=q; } } // void InitVisited(AdjList *g) { for(int i=1;i<=g->verNum;i++) { visited[i]=0; } } //访问顶点值 void visit(AdjList *g,int v) { cout<<g->VerNodes[v].data<<endl; } //深度遍历图 void DFSTransfer(AdjList *g,int v) { visit(g,v);visited[v]=1; ArcNode *q=NULL; q=g->VerNodes[v].first; while(q!=NULL) { if(!visited[q->adj]) { DFSTransfer(g,q->adj); q=q->next; } } } //广度遍历v顶点 void BFS(AdjList *g,int v) { ArcNode *q=NULL; Queue *Q=(Queue *)malloc(sizeof(Queue)); InitQueue(Q); Q->Item[Q->rear]=v;visit(g,v);visited[v]=1; Q->rear=(Q->rear+1)%MAX_VERTEX_NUM; while(Q->front!=Q->rear) { v=Q->Item[Q->front]; Q->front=(Q->front+1)%MAX_VERTEX_NUM; q=g->VerNodes[v].first; while(q!=NULL) { if(!visited[q->adj]) { visit(g,q->adj); visited[q->adj]=1; Q->Item[Q->rear]=q->adj; Q->rear=(Q->rear+1)%MAX_VERTEX_NUM; q=q->next; } } } } //广度遍历图 void BFSTransfer(AdjList *g) { InitVisited(g); for(int i=1;i<=g->verNum;i++) { if(!visited[i]) { BFS(g,i); } } cout<<endl; } int main() { AdjList *g=(AdjList*)malloc(sizeof(AdjList)); CreateAdjList(g); cout<<"---------------------广度优先搜索----------------------"<<endl; BFSTransfer(g); cout<<"---------------------深度优先搜索----------------------"<<endl; InitVisited(g); DFSTransfer(g,1); return 0; }
发表评论
-
【排序算法系列】希尔排序
2015-12-05 16:14 842希尔排序的概述: a[0]...a[n-1 ... -
归并排序
2015-06-20 15:28 898public class MergeSort { pub ... -
插入排序
2015-06-20 15:27 485/** * 插入排序1 容易理解 * * ... -
有序线性链表归并
2013-10-05 11:30 1564#include<stdio.h> #incl ... -
Trie树 应用 Phone List
2012-06-15 11:21 1180Phone List 时间限 ... -
Trie树 单词查找树 键树(JAVA版附分析说明)
2012-06-13 10:27 5181来源于英文“retrieval”. ... -
Trie树 单词查找树 键树
2012-06-12 08:59 1157转自:http://zh.wik ... -
数字金额转中文大写金额
2010-11-26 15:09 1429/** * 用来将数字金额转化成中文大写的金额 ... -
汉诺塔递归算法
2010-11-25 08:17 1355import java.util.Scanner; /* ... -
约瑟夫出圈
2010-11-24 20:45 1101#include<iostream> #incl ... -
SmartHashSet只是为了解释HashSet的原理
2010-07-26 11:11 1362写该类的目的只是为了 ... -
二叉树中序遍历非递归算法
2010-06-29 23:17 1724#include<iostream> usi ... -
二叉树的创建
2010-06-29 23:15 1135#include<iostream> usi ... -
哈弗曼树建立与哈弗曼编码
2010-06-29 23:12 1250#include<iostream> #de ... -
二叉排序树转双向链表(要求无任何新增节点)
2010-06-29 23:07 2494题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双 ... -
线索二叉树中插入结点
2010-06-29 23:05 1893#include<iostream> usi ... -
二叉排序树的递归与非递归查找
2010-06-29 22:58 2310#include<iostream> usi ... -
二叉树中序线索化及查找某一结点的前驱,后继结点
2010-06-29 22:54 2686#include<iostream> usi ... -
十字链表定义创建查找
2010-06-29 22:44 1323#include<iostream> #defi ... -
稀疏矩阵转置
2010-06-29 22:39 1667#include<iostream> #defi ...
相关推荐
基于邻接表存储的图的dfs与bfs遍历,对学习数据结构很有帮助
程序用交互方式完成图的邻接矩阵和邻接表的构造,并提供了DFS和BFS算法。
例如,文件"DFS_BFS"可能包含了针对邻接表存储的图进行DFS和BFS的具体代码实现,包括如何初始化邻接表、如何进行遍历、如何判断遍历结束以及如何处理节点的状态等细节。通过学习和理解这些代码,可以进一步加深对这...
7. **函数设计**:实验中定义了几个关键函数,如`BuildGraph`用于从文件构建图的邻接表,`Visit`用于访问一个顶点,`ClearVisited`清除访问标记,`BFS`和`DFS`分别实现了广度优先和深度优先遍历。这些函数的设计体现...
本文将深入探讨如何使用邻接矩阵和邻接表这两种方法来创建图,并实现深度优先搜索(DFS)和广度优先搜索(BFS)算法。 首先,我们来看邻接矩阵。邻接矩阵是一个二维数组,其中的元素代表图中节点之间的连接状态。...
本文将详细讲解如何使用C#语言实现有向图算法,包括邻接表、关键路径、深度优先搜索(DFS)和广度优先搜索(BFS),以及拓扑排序。 首先,我们要理解有向图的概念。有向图是由顶点(节点)和边组成的,边具有方向性...
- `8.4 邻接表迷宫.cpp`:可能涉及用邻接表来表示迷宫,并使用DFS或BFS找到从起点到终点的解。 4. 应用场景 DFS和BFS在各种实际问题中都有应用,例如网页爬虫、社交网络分析、文件系统遍历、游戏AI决策等。同时,...
本主题将深入探讨两种常见的图存储方式——邻接矩阵和邻接表,以及如何在这两种存储方式下实现深度优先遍历(DFS)和广度优先遍历(BFS)。 首先,邻接矩阵是一种直观的图表示方法,它使用二维数组来存储图中每个...
通常,这些代码会定义图的数据结构,如邻接矩阵或邻接表,然后分别实现DFS和BFS的函数,调用这些函数对图进行遍历。 总结,DFS和BFS是图论中的基础算法,它们各有优缺点。DFS适用于解决深度优先的问题,如查找图中...
04邻接表深度和广度遍历DFS_BFS.c
数据结构实验报告主要探讨了如何使用邻接表作为存储结构来实现图的深度优先遍历(DFS)和广度优先遍历(BFS)。在计算机科学中,图是一种表示对象间关系的数据结构,邻接表是高效存储无向图或有向图的一种方式,它...
在计算机科学中,图是一种非常重要的数据结构,用于表示对象之间的关系。图由顶点(也称为节点)和边(连接顶点的线)组成,可以...通过熟练掌握邻接矩阵和邻接表,以及DFS和BFS,我们可以更有效地解决与图相关的问题。
在这个例子中,`adjcreate`函数用于创建邻接表,`create`函数用于构建整个图,`dfs`和`bfs`分别实现了深度优先和广度优先遍历。在`main`函数中,我们先构建图,然后进行两种遍历。 总的来说,理解和实现DFS与BFS...
根据给定文件中的标题“DFS \BFS生成树”、描述以及部分代码内容,我们可以提炼出以下几个关键知识点:邻接表、深度优先搜索(Depth-First Search, DFS)、广度优先搜索(Breadth-First Search, BFS)以及如何利用这...
通常,我们可以使用邻接矩阵或邻接表来表示无向图。邻接矩阵是一个二维数组,其中的元素表示图中节点之间的连接关系;邻接表则是用链表或数组来存储每个节点的所有邻居节点。在C++中,可以使用`std::vector`来实现这...
在编程中,可以使用邻接矩阵或邻接表来表示图。邻接矩阵是一个二维数组,表示每个节点之间是否有边相连;邻接表则是一个节点集合,每个节点包含一个邻接节点列表。添加节点通常意味着在数据结构中增加一个新的节点...
本主题主要涵盖了三种关键概念:邻接矩阵、邻接表以及图的两种遍历方法——深度优先搜索(DFS)和广度优先搜索(BFS)。 首先,邻接矩阵是一种表示图的数据结构,它是一个二维数组,其中的每个元素代表图中对应节点...
本篇将深入探讨图的邻接表存储结构以及如何对无向图进行深度优先遍历(DFS)和广度优先遍历(BFS)。 首先,让我们理解什么是邻接表。邻接表是图的一种高效存储方式,特别适合于稀疏图(边的数量远小于节点数量的...
在C语言中,实现DFS和BFS时,可以使用数组或链表来表示图,邻接矩阵或邻接表是常用的存储方式。邻接矩阵用二维数组表示,邻接表则用一维数组和链表组合。对于图的遍历,通常需要一个辅助数据结构,如栈(DFS)或队列...
邻接表是一种用于表示图的存储结构,适用于稀疏图(即边的数量远小于顶点数量的平方)。它通过一系列链表来表示图中的各个顶点及其相邻的顶点,对于每个顶点,都有一个链表用来存储与之相连的所有顶点。 ### 二、头...