- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
假设我创建一个名为graph-file.txt的文件,其中包含一个
的数据有向图如下:
7
{5, 2, 3}, {1,5}, {}, { }, {3}, { }, { }
文件的第一行显示顶点数(在本例中为 7)。第二行描述每个顶点的邻居 N+(v)。例如,从顶点 1 开始,边被定向到顶点 5,2 和 3,而对于顶点 7,没有边被定向到该图中的任何其他顶点。
我想问一下如何从该文件中读取BFS算法所需的边信息(如上所述)?
我使用以下函数进行 BFS:
#define SIZE 40
struct queue {
int items[SIZE];
int front;
int rear;
};
struct queue* createQueue();
void enqueue(struct queue* q, int);
int dequeue(struct queue* q);
void display(struct queue* q);
int isEmpty(struct queue* q);
void printQueue(struct queue* q);
struct node
{
int vertex;
struct node* next;
};
struct node* createNode(int);
struct Graph
{
int numVertices;
struct node** adjLists;
int* visited;
};
struct Graph* createGraph(int vertices);
void addEdge(struct Graph* graph, int src, int dest);
void printGraph(struct Graph* graph);
void bfs(struct Graph* graph, int startVertex);
void bfs(struct Graph* graph, int startVertex) {
struct queue* q = createQueue();
graph->visited[startVertex] = 1;
enqueue(q, startVertex);
while(!isEmpty(q)){
printQueue(q);
int currentVertex = dequeue(q);
printf("Visited %d\n", currentVertex);
struct node* temp = graph->adjLists[currentVertex];
while(temp) {
int adjVertex = temp->vertex;
if(graph->visited[adjVertex] == 0){
graph->visited[adjVertex] = 1;
enqueue(q, adjVertex);
}
temp = temp->next;
}
}
}
struct node* createNode(int v)
{
struct node* newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
struct Graph* createGraph(int vertices)
{
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(struct node*));
graph->visited = malloc(vertices * sizeof(int));
int i;
for (i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
void addEdge(struct Graph* graph, int src, int dest)
{
// Add edge from src to dest
struct node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
// Add edge from dest to src
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
struct queue* createQueue() {
struct queue* q = malloc(sizeof(struct queue));
q->front = -1;
q->rear = -1;
return q;
}
int isEmpty(struct queue* q) {
if(q->rear == -1)
return 1;
else
return 0;
}
void enqueue(struct queue* q, int value){
if(q->rear == SIZE-1)
printf("\nQueue is Full!!");
else {
if(q->front == -1)
q->front = 0;
q->rear++;
q->items[q->rear] = value;
}
}
int dequeue(struct queue* q){
int item;
if(isEmpty(q)){
printf("Queue is empty");
item = -1;
}
else{
item = q->items[q->front];
q->front++;
if(q->front > q->rear){
printf("Resetting queue");
q->front = q->rear = -1;
}
}
return item;
}
void printQueue(struct queue *q) {
int i = q->front;
if(isEmpty(q)) {
printf("Queue is empty");
} else {
printf("\nQueue contains \n");
for(i = q->front; i < q->rear + 1; i++) {
printf("%d ", q->items[i]);
}
}
}
最佳答案
假设输入有效,作为一个有趣的练习,我尝试提出所需的最小解析器。对于 x86_64,它编译为 less than 40 instructions ,使用一些寄存器:
void edge(int from, int to);
void parse(void)
{
int v = 0;
for (;;) {
const int c = getchar();
if (c == EOF)
return;
// Next 'from' vertex?
if (c == '{') {
++v;
continue;
}
// Ignore vertex count
if (v == 0)
continue;
// Found 'to' vertex?
int w = c - '0';
if (w < 0 || w > 9)
continue;
// Parse 'to' vertex
for (;;) {
const int d = getchar() - '0';
if (d < 0 || d > 9)
break;
w = w * 10 + d;
}
edge(v, w);
}
}
当然,如果您需要验证输入,那么您将需要更多状态来处理逗号、右大括号、不匹配的顶点数、超出范围的顶点数、无效字符等。
关于c - 从文件(C 语言)中读取整数,其中包括有向图的数据,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50541761/
127.0.0.1:8000/api/仅包含来自第二个应用程序的 url,但我将两个 url 模块链接到相同的模式。甚至有可能做到这一点吗? 第一个应用程序: from django.urls imp
我目前正在学习 ColdFusion。我有 PHP 背景,对此我有点困惑。 我有一个选择菜单,我希望将选项保存在不同的文件中。 (例如 options.cfm)当我调用文件时,我想在选择菜单中包含选项
字符串: "75,000", "is", "95%", "or", "95/100" "of", "monthly", "income" o/p: "is","%, "or", "/", "of",
我有 4 个 javascript 文件(每个文件对应一个 HTML 文件),所有 4 个文件中的 3 个函数都是相同的。我想找到一个顺利的解决方案,我可以以某种方式分别包含这 3 个函数...是否可
我在 PHP 中有这种情况,其中 include在一台服务器上被遗漏,但在另一台服务器上没有(我没有设置服务器,所以我不能告诉你更多;我不是真正的 devops 人,所以这就是我在这里问的原因)。两台
这是一个模式文件,midi.xsd定义类型,note ,用于存储 MIDI 音符值: 这是另一个模式文件,octaves.xsd使用
我想备份以下文件夹 /home /etc /usr/local /root /var /boot 并排除 /var/tmp /var/run /var/lock /home/*/.thumbnails
如何重新编码具有许多值(包括缺失值)的数值变量,以获得数字 0:n-1哪里n是唯一值的数量,包括 NA ,整齐? 例子: df 1 1000 0 2 1000 0 3 N
选择元素的 html(包括在内)的最佳方法是什么?例如: This is just a test. 而$('#testDiv').html()返回"This is just a test."
我正在尝试设置Varnish来处理本地环境中的ESI包含。 我在虚拟机中运行 Varnish ,内容在主机上运行。 我有两个文件“index.html”和“test.html”。它们都存储在apach
我有以下内容,并且想要检索“ FromEmail”不为空的数据 Simple email@gma
欧海,我正在编写一个小型 PHP 应用程序,使用一个单独的 config.php 文件和一个functions.php,其中包含我将在应用程序中使用的所有自定义函数。现在,我真的必须在每个函数中包含
我知道可以将 JavaScript 放在一个特定的 .js 文件中,然后通过执行以下操作将其包含在任何页面中...... 我注意到,对于包含的这些 .js 文件: 它们实际上不必以 .js 结尾 其
我使用 gwt UIBinder 添加了一些项目到我的 ComboBox。 --select one-- Dispute Referral Form Dispute Settlement Clause
我可以将一个 first.c 文件包含到另一个 second.c 中吗? (我正在做一些套接字编程,以将服务器收到的消息存储在链接列表中,因此在第一个程序中,我尝试保留链接列表和第二个程序套接字编程文
我有一个简单的 Spring MVC 数据项目设置,我试图选择 Admin 中尚不存在的用户列表。 table 。这是我的存储库方法 SELECT u FROM User u WHERE u.id N
在 bash 脚本中,使用什么实用程序以及如何删除两个字符串之间的文本,包括字符串。 原文: (ABC blah1)blah 2(def blah 5)blah 7)(DEF blah 8)blah
我有这个 BST 问题,我试图用 Java 解决,但我不知道为什么它不起作用。问题是: 二叉搜索树 (BST) 是一种二叉树,其中每个值节点大于或等于该节点的所有节点中的值左子树并且小于该树中所有节点
我有一个字符串,其中包含“Dollars”和“Cents”符号。我想删除它们。我试过了 string.replaceAll("[\"\\u00A2\" $]", "") 但它不起作用。正确的做法是什么
我在 stories 和 tags 之间有一个多对多的关系,为保存关系而创建的表是 taxonomies。我想搜索所有具有所有给定标签的故事。 到目前为止我使用的查询是这个,当然它对我不起作用,它返回
我是一名优秀的程序员,十分优秀!