Part1:回顾

1.图(Graph)

首先来看一下图的定义。

再来看下图的抽象数据类型定义。

看了上述介绍之后，自然有个很基础的问题，如何在程序中表示一个图，一般有以下两种方法。
1.邻接矩阵法。

显然，无项图的邻接矩阵为对称矩阵，浪费了很多空间，所以此时可以使用一维数组来表示，如下所示。

那么邻接矩阵的优缺点分别是什么呢？

2.邻接表表示法。
邻接表表示法的意思是记录每个点以及和它直接相连的点，具体的意思是首先记录根节点，根节点指向与其链接的节点，每个节点分为两个部分，值和指针，指针指向与根节点相连的其他节点，所以共占$N+2E$空间(每条边占用两个空间)。

再来看下邻接表的优缺点。

最后来比较一下邻接矩阵法和邻接表法占用的空间,设$N$个点和$E$条边。
那么邻接矩阵法占用的空间为$N^2$,邻接表法占用的空间为$N+2E$。
注意对于图来说不计重边，如果是无向图，那么$E\le C_N^2$。
因为任意两点之间最多一条边，因此:

$N^2-N-2E\ge N^2-N-2C_N^2=0$

所以在无向图的情形下，邻接表法所占用的空间一定不大于邻接矩阵法。

2.图的遍历

图的遍历有两种，广度优先(BFS)以及深度优先(DFS)
深度优先简单来说就是一条路先走到死，如果走不通，再往回退。因为只要访问每条边和每个节点，所以邻接矩阵法和邻接表法的时间复杂度如下所示。

广度优先的意思是从根节点出发，先走遍与其直接相连的节点，访问完之后，再对第一个访问的相邻节点重复此操作，直至所有的边和节点完全访问。时间复杂度同深度优先。注意BFS最先访问的相邻节点需要最先重复调用，所以需要使用队列来操作。

最后再来看下图的联通性问题。
首先来看下一些基本定义。

其实解决图不连通的情形很简单，只要对未访问的节点调用DFS,以及BFS即可。

Part2:作业

作业1

06-图1 列出连通集（25 分）
给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入格式:
输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。
输出格式:
按照$v_1v_2…v_k$的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。
输入样例:
8 6
0 7
0 1
2 0
4 1
2 4
3 5
输出样例:
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }

这题应该说是非常基础的，只考察了DFS以及BFS的实现。

# -*- coding: utf-8 -*-
"""
Created on Mon Apr 16 12:18:53 2018

@author: 715073608
"""

#读取节点个数N，和边的个数E
N,E=map(int,raw_input().strip().split(' '))

#利用邻接表表示图
m=[[] for i in range(N)]
    
for i in range(E):
    x,y=map(int,raw_input().strip().split(' '))
    m[x].append(y)
    m[y].append(x)
for i in m:
    i.sort()

'''
m=[[1, 2, 7], [0, 4], [0, 4], [5], [1, 2], [3], [], [0]]
N=8
'''
#定义DFS
#m为图，x为开始节点,y为访问数组，记录是否访问过,s用来返回结果
def DFS(m,x,y,s):
    s.append(x)
    y[x]=1
    for i in m[x]:
        if y[i]==0:
            DFS(m,i,y,s)
    return s 

#对全部元素做DFS
def DFSall(m,N):
    #记录结果
    ans=[]
    #记录是否访问过，如果访问过，则不对该节点做BFS
    visited=[0 for i in range(N)]
    for i in range(N):
        if visited[i]==0:
            s=[]
            ans.append(DFS(m,i,visited,s))
    return ans

#产生结果
t=DFSall(m,N)

#定义输出函数
def output(x):
    for i in x:
        print "{ "+' '.join(map(str,i))+' }'

#输出结果
output(t)

#定义BFS
#m为图，x为开始节点,y为访问数组，记录是否访问过,s用来返回结果,q为程序中需要的队列
def BFS(m,x,y,s,q):
    y[x]=1
    s.append(x)
    q.append(x)
    while(len(q)>0):
        v=q.pop(0)
        for i in m[v]:
            if y[i]==0:
                y[i]=1
                q.append(i)
                s.append(i)
    return s

#对全部元素做BFS
def BFSall(m,N):
    visited=[0 for i in range(N)]
    ans=[]
    for i in range(N):
        if visited[i]==0:
            s=[]
            q=[]
            ans.append(BFS(m,i,visited,s,q))
    return ans

#产生结果
t=BFSall(m,N)

#输出结果
output(t)

作业2

06-图2 Saving James Bond - Easy Version（25 分）
This time let us consider the situation in the movie “Live and Let Die” in which James Bond, the world’s most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape — he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head… Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).
Assume that the lake is a 100 by 100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him whether or not he can escape.

Input Specification:
Each input file contains one test case. Each case starts with a line containing two positive integers N (≤100), the number of crocodiles, and D, the maximum distance that James could jump. Then N lines follow, each containing the (x,y) location of a crocodile. Note that no two crocodiles are staying at the same position.

Output Specification:
For each test case, print in a line “Yes” if James can escape, or “No” if not.
Sample Input 1:
14 20
25 -15
-25 28
8 49
29 15
-35 -2
5 28
27 -29
-8 -28
-20 -35
-25 -20
-13 29
-30 15
-35 40
12 12
Sample Output 1:
Yes
Sample Input 2:
4 13
-12 12
12 12
-12 -12
12 -12
Sample Output 2:
No

题目的意思是邦德站在原点处，他的跳跃有一定范围，鳄鱼在不同节点处，以此判断是否能落岸，注意小岛也有一定半径,来看个示意图。

这里采用了DFS,代码中的注释解释了思路。

# -*- coding: utf-8 -*-
"""
Created on Mon Apr 16 20:01:34 2018

@author: Administrator
"""

#读入鳄鱼个数n,以及跳跃距离d
n,d=map(int,raw_input().strip().split(' '))

#初始化图，注意增加原点
m=[[] for i in range(n)]
for i in range(n):
    temp=map(int,raw_input().strip().split(' '))
    #最后一个元素记录是否访问过
    temp.append(0)
    m[i]=temp

#定义点的距离
def dis1(x,y):
    return ((x[0]-y[0])**2+(x[1]-y[1])**2)**0.5

#定义离岸的距离
def dis2(x):
    return min(abs(x[0]-50),abs(x[0]+50),abs(x[1]-50),abs(x[1]+50))

#定义DFS
#m为图，x为开始节点
def DFS(m,x,s):
    ans=s
    m[x][-1]=1
    #如果距离岸的最短距离小于等于d，返回Yes
    if dis2(m[x])<=d:
        ans='Yes'
    #否则进行DFS
    else:
        for i in range(n):
            if m[i][-1]==0 and dis1(m[x],m[i])<=d:
                ans=DFS(m,i,s)
                if ans=='Yes':
                    break
    return ans

#遍历所有的点
t=''
for i in range(n):
    if m[i][-1]==0 and dis1([0,0],m[i])<=7.5+d:
        t=DFS(m,i,'')
        if t=='Yes':
            break
if t=='Yes':
    print 'Yes'
else:
    print 'No'

作业3

06-图3 六度空间（30 分）
“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”如图1所示。
图1 六度空间示意图
“六度空间”理论虽然得到广泛的认同，并且正在得到越来越多的应用。但是数十年来，试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因，这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具，能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。
假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。
输入格式:
输入第1行给出两个正整数，分别表示社交网络图的结点数N（表示人数）、边数M（表示社交关系数）。随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个结点的编号（节点从1到N编号）。
输出格式:
对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比，精确到小数点后2位。每个结节点输出一行，格式为“结点编号:（空格）百分比%”。
输入样例:
10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
输出样例:
1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00%

这题显然是使用BFS，主要难点是记录层数,主要使用了last和tail，注释中有写，这里不详叙。

# -*- coding: utf-8 -*-
"""
Created on Mon Apr 16 23:37:28 2018

@author: Administrator
"""

n,m=map(int,raw_input().strip().split(' '))

x=[[] for i in range(n+1)]
y=[0 for i in range(n+1)]

for i in range(m):
    a,b=map(int,raw_input().strip().split(' '))
    x[a].append(b)
    x[b].append(a)

#定义BFS
#m为图，x为开始节点,y为访问数组，记录是否访问过
def BFS(m,x,y):
    q=[]
	#记录层数
    count=1
    level=0
	#last记录这层的最后一个节点，如果queue中抛出的元素等于last，表示这层遍历完毕，此时层数加一,last=tail
    last=x
	#tail表示下一层的最后一个节点
    tail=0
    y[x]=1
    q.append(x)
    while(len(q)>0):
        v=q.pop(0)
        for i in m[v]:
            if y[i]==0:
                y[i]=1
                q.append(i)
                count+=1
                tail=i
        if v==last:
            level+=1
            last=tail
        if level==6:
            break
    return count

for i in range(1,n+1):
    y1=y[:]
    print '{}: {:2.2f}%'.format(i,BFS(x,i,y1)*100.0/n)

— 作业4

Forwards on Weibo (30)
Weibo is known as the Chinese version of Twitter. One user on Weibo may have many followers, and may follow many other users as well. Hence a social network is formed with followers relations. When a user makes a post on Weibo, all his/her followers can view and forward his/her post, which can then be forwarded again by their followers. Now given a social network, you are supposed to calculate the maximum potential amount of forwards for any specific user, assuming that only L levels of indirect followers are counted.
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers: N (<=1000), the number of users; and L (<=6), the number of levels of indirect followers that are counted. Hence it is assumed that all the users are numbered from 1 to N. Then N lines follow, each in the format:
M[i] user_list[i]
where M[i] (<=100) is the total number of people that user[i] follows; and user_list[i] is a list of the M[i] users that are followed by user[i]. It is guaranteed that no one can follow oneself. All the numbers are separated by a space.
Then finally a positive K is given, followed by K UserID’s for query.
Output Specification:
For each UserID, you are supposed to print in one line the maximum potential amount of forwards this user can triger, assuming that everyone who can view the initial post will forward it once, and that only L levels of indirect followers are counted.
Sample Input:
7 3
3 2 3 4
0
2 5 6
2 3 1
2 3 4
1 4
1 5
2 2 6
Sample Output:
4
5

这题其实就是六度空间的翻版，如果理解了六度空间那题，应该就不难，不过我的代码有点问题，就是会超时，尴尬。


# -*- coding: utf-8 -*-
"""
Created on Tue Apr 17 12:24:23 2018

@author: 715073608
"""
#先根据追随哪些人反取出每人的追随者
n,l=map(int,raw_input().strip().split())

u=[[] for i in range(n+1)]
for i in range(1,n+1):
    temp=map(int,raw_input().strip().split())
    if temp[0]>0:
        for j in temp[1:]:
            u[j].append(i)
v=map(int,raw_input().strip().split())
y=[0 for i in range(n+1)]

#定义BFS
#m为图，x为开始节点,y为访问数组，记录是否访问过
def BFS(m,x,y):
	#记录层数，起点不算第一层
    count=0
    level=0
    q=[]
    last=x
    tail=0
    y[x]=1
    q.append(x)
    while(len(q)>0):
        v=q.pop(0)
        for i in m[v]:
            if y[i]==0:
                q.append(i)
                y[i]=1
                tail=i
                count+=1
        if v==last:
            level+=1
            last=tail
        if level==l:
            break
    return count
for i in v[1:]:
    print BFS(u,i,y[:])