数据结构与算法_c语言描述|程序员面试金典-0401-节点间通路算法|数据结构|广度搜索|leet

程序员面试金典-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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

【数据结构与算法_c语言描述|程序员面试金典-0401-节点间通路】解法：//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; inext=first; while(head->next!=NULL){struct list_node * temp = head->next; int t = temp->val; if(flag[t]==0){for(i=0; inext=temp->next; free(temp); } free_list(head); return false; }