时间戳

首页 > 解决方案 > 我想使具有相邻矩阵的 DFS 具有在具有相邻列表的 DFS 上的能力

c - 我想使具有相邻矩阵的 DFS 具有在具有相邻列表的 DFS 上的能力

问题描述

请让我知道如何通过插入任何代码将性能从 O(n^2) 更改为 O(n+e) .. 无需修改

typedef struct GraphType 
{ 
    int n; //the number of vertex GraphNode
    int adj_mat[50][50]; 
} GraphType;

void dfs_mat(GraphType* g,int v)
{
   int w;
   visited[v] = TRUE; // Show Visits at Vertex v
   print("visit %d ->", v); print visited vertex
   for(w = 0; w<g->n; w++) // search adjacent vertex
      if(g->adj_mat[v][w] && !visited[w])
         dfs_mat(g,w); // restart from vertex w
}

void graph_init(GraphType *g)
{
   int r,c;
   g->n=0;
   for(r=0;r<50;r++)
      for(c=0;c<50;c++)
         g->adj_mat[r][c]=0;
}

void insert_vertex(GraphType *g,int v)
{
   if(((g->n)+1)>50){
      printf("error");
      return;
   }
g->n++;
}

void insert_edge(GraphType *g, int start, int end)
{
   if(start >= g->n || end >= g->n){
      printf("error");
      return;
   }
   g->adj_mat[start][end] = 1;
   g->adj_mat[end][start] = 1;
}

int main(void){
   int i;
   GraphType g;

   graph_init(&g);
   for(i=0;i<4;i++)
      insert_vertex(&g,i);
   insert_edge(&g,0,1);
   insert_edge(&g,1,0);
   insert_edge(&g,0,3);
   insert_edge(&g,3,0);
   insert_edge(&g,1,2);
   insert_edge(&g,2,1);
   insert_edge(&g,1,3);
   insert_edge(&g,3,1);
   insert_edge(&g,2,3);
   insert_edge(&g,3,2);
   dfs_mat(&g,0);
}

首先，递归发生的次数与顶点数一样多，因为我们需要检查边。

问题是程序何时访问了所有顶点。即使所有顶点都已经被访问过，其余的迭代操作也会被执行。我想我必须在迭代语句的操作中包含条件。但我不知道。

请救救我。

标签： cgraphdepth-first-searchbreadth-first-search

解决方案

您可以初始化一个变量，例如visited_count并将其设置为节点数。在每次访问操作时减少此变量。每次检查是否visited_count等于零，如果是，则跳出循环。检查////////////////// CHANGE评论中写的行。

#include <stdio.h>
#include <stdbool.h>


typedef struct GraphType 
{ 
    int n; //the number of vertex GraphNode
    int adj_mat[50][50]; 
} GraphType;

static bool visited[50] = {false};
static int visited_count;            ////////////////// CHANGE

void dfs_mat(GraphType* g,int v)
{
   int w;
   visited[v] = true; // Show Visits at Vertex v
   visited_count--;         ////////////////// CHANGE
   printf("=== visit %d ===\n", v); // print visited vertex
   for(w = 0; w<g->n && visited_count; w++) // search adjacent vertex        ////////////////// CHANGE
   {
       if (v != w)         ////////////////// CHANGE
       {
          printf("Processing node: %d, neighbor = %d\n", v, w);      ////////////////// CHANGE - added for debugging
          if(g->adj_mat[v][w] && !visited[w])
             dfs_mat(g,w); // restart from vertex w
       }
   }
}

void graph_init(GraphType *g)
{
   int r,c;
   g->n=0;
   for(r=0;r<50;r++)
      for(c=0;c<50;c++)
         g->adj_mat[r][c]=0;
}

void insert_vertex(GraphType *g,int v)
{
   if(((g->n)+1)>50){
      printf("error");
      return;
   }
g->n++;
}

void insert_edge(GraphType *g, int start, int end)
{
   if(start >= g->n || end >= g->n){
      printf("error");
      return;
   }
   g->adj_mat[start][end] = 1;
   g->adj_mat[end][start] = 1;
}

int main(void){
   int i;
   GraphType g;

   graph_init(&g);
   visited_count = 4;        ////////////////// CHANGE
   for(i=0;i<4;i++)
      insert_vertex(&g,i);
   insert_edge(&g,0,1);
   insert_edge(&g,1,0);
   insert_edge(&g,0,3);
   insert_edge(&g,3,0);
   insert_edge(&g,1,2);
   insert_edge(&g,2,1);
   insert_edge(&g,1,3);
   insert_edge(&g,3,1);
   insert_edge(&g,2,3);
   insert_edge(&g,3,2);
   dfs_mat(&g,0);
}

推荐阅读