Skip to content
Navigation Menu
Sign in
Appearance settings
Platform
AI CODE CREATION
GitHub Copilot
Write better code with AI
GitHub Copilot app
Direct agents from issue to merge
MCP Registry
Integrate external tools
DEVELOPER WORKFLOWS
Actions
Automate any workflow
Codespaces
Instant dev environments
Issues
Plan and track work
Code Review
Manage code changes
Code Quality
Enforce quality at merge
APPLICATION SECURITY
GitHub Advanced Security
Find and fix vulnerabilities
Code security
Secure your code as you build
Secret protection
Stop leaks before they start
EXPLORE
Why GitHub
Documentation
Blog
Changelog
Marketplace
View all features
Solutions
BY COMPANY SIZE
Enterprises
Small and medium teams
Startups
Nonprofits
BY USE CASE
App Modernization
DevSecOps
DevOps
CI/CD
View all use cases
BY INDUSTRY
Healthcare
Financial services
Manufacturing
Government
View all industries
View all solutions
Resources
EXPLORE BY TOPIC
AI
Software Development
DevOps
Security
View all topics
EXPLORE BY TYPE
Customer stories
Events & webinars
Ebooks & reports
Business insights
GitHub Skills
SUPPORT & SERVICES
Documentation
Customer support
Community forum
Trust center
Partners
View all resources
Open Source
COMMUNITY
GitHub Sponsors
Fund open source developers
PROGRAMS
Security Lab
Maintainer Community
GitHub Stars
Archive Program
REPOSITORIES
Topics
Trending
Collections
Enterprise
ENTERPRISE SOLUTIONS
Enterprise platform
AI-powered developer platform
AVAILABLE ADD-ONS
GitHub Advanced Security
Enterprise-grade security features
Copilot for Business
Enterprise-grade AI features
Premium Support
Enterprise-grade 24/7 support
Pricing
Search
/
Sign in
Sign up
Appearance settings
You signed in with another tab or window.
Reload
to refresh your session.
You signed out in another tab or window.
Reload
to refresh your session.
You switched accounts on another tab or window.
Reload
to refresh your session.
Dismiss alert
{{ message }}
mnmlyn
/
Graph
Public
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Issues
0
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Security and quality
Insights
Files
Expand file tree
master
Breadcrumbs
Graph
/
README
Copy path
Blame
More file actions
Blame
More file actions
Latest commit
History
History
History
19 lines (15 loc) · 1.37 KB
master
Breadcrumbs
Graph
/
README
Copy path
Top
File metadata and controls
Code
Blame
19 lines (15 loc) · 1.37 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
将会对图相关的基本算法进行实现,参考《算法导论》。
首先,第22章-基本的图算法。
采用邻接链表来表示图,节点用正的整形数来标识,每个节点有属性color表示图搜索的状态,有属性d和属性
pi等。因此,邻接链表的结构为,首先每个节点为一个结构体VNode,存储各种节点属性,且有一个指针指向当前节
点指向的邻接节点的链表。链表节点又是另外一种结构体LNode。
广度优先搜索。
借助一个队列,来对图进行广度优先搜索。参考22.2节。
BFS之后,pi属性记录了节点的前驱,得到一棵广度优先树。BFS之后每个节点v记录的属性d,为从s到v的最短
路径。借助pi属性,输出节点s到节点v的最短路径上的每个节点。
深度优先搜索。
使用递归方式来进行DFS。辅助递归函数,首先访问当前节点u,然后选择一个相邻的未被访问(白色)节点v进
行递归,递归调用结束后,再选择u其余的白色节点,直到所有节点都不为白色。将当前节点u涂为黑色,结束辅助递
归函数。DFS对所有仍为白色的节点,调用辅助递归函数。
DFS算法中,加入time,来表示访问的先后顺序,每个节点的属性d表示第一次访问时间,属性f表示完成所有相
邻节点访问的时间。
You can’t perform that action at this time.