程序员面试金典-0401-节点间通路

- 日理万妓 2022-09-14 08:52 154阅读 0赞

## 程序员面试金典-0401-节点间通路 ##

类似于树的层次遍历算法，需要借助队列将节点插入进去，依次遍历。对应更基本的算法即：广度优先遍历

节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
    
    示例1:
    
     输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
     输出：true
    示例2:
    
     输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4
     输出 true
    提示：
    
    节点数量n在[0, 1e5]范围内。
    节点编号大于等于 0 小于 n。
    图中可能存在自环和平行边。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/route-between-nodes-lcci
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：//f 标注的为简单优化的行，去掉仍然可以pass

struct list_node{
        
        int val;
        struct list_node * next;
    };
    
    struct list_node * node_init(int data){
        
        struct list_node * temp = malloc(sizeof(struct list_node));
        temp->val = data;
        temp->next = NULL;
        return temp;
    }
    
    void list_insert(struct list_node* h,int data){
        
        struct list_node * t = h;
        while(t->next!=NULL)
            t=t->next;
        struct list_node * temp = node_init(data);
        t->next=temp;
    }
    
    void free_list(struct list_node * h){
        
        while(h->next!=NULL){
        
            struct list_node * temp = h->next;
            h->next = temp->next;
            free(temp);
        }
        free(h);
    }
    bool findWhetherExistsPath(int n, int** graph, int graphSize, int* graphColSize, int start, int target){
        
        int row = graphSize;
        int col = (*graphColSize);
        int i=0,j=0;
        int flag[n];
        int row_flag[row]; //f
        for(i=0;i<n;i++)
            flag[i]=0;
        for(i=0;i<row;i++)  //f
            row_flag[i]=0;   //f
        struct list_node * head = node_init(-1);
        struct list_node * first = node_init(target);
        head->next=first;
        while(head->next!=NULL){
        
            struct list_node * temp = head->next;
            int t = temp->val;
            if(flag[t]==0){
        
            for(i=0;i<row;i++){
        
                if(row_flag[i]==1) //f
                    continue;
                    if(graph[i][1]==t){
        
                        if(graph[i][0]==start){
        
                            free_list(head);
                            return true;
                        }
                        list_insert(head,graph[i][0]);
                        row_flag[i]=1;  //f
                    }
            }
            flag[t]=1;
            }
            else{
        
                flag[t]=1;
            }
            head->next=temp->next;
            free(temp);
        }
        free_list(head);
        return false;
    }