Hydrologic connectivity is critical to the structure, function, and dynamic process of river ecosystems. Dams, road crossings, and water diversions impact connectivity by altering flow regimes, behavioral cues, local geomorphology, and nutrient cycling. This longitudinal fragmentation of river ecosystems also increases genetic and reproductive isolation of aquatic biota such as migratory fishes. The cumulative effects on fish passage of many structures along a river are often substantial, even when individual barriers have negligible impact. Habitat connectivity can be improved through dam removal or other means of fish passage improvement (e.g., ladders, bypasses, culvert improvement). Environmental managers require techniques for comparing alternative fish passage restoration actions at alternative or multiple locations. Herein, we examined a graph-theoretic algorithm for assessing upstream habitat connectivity to investigate both basic and applied fish passage connectivity problems. First, we used hypothetical watershed configurations to assess general alterations to upstream fish passage connectivity with changes in watershed network topology (e.g., linear vs. highly dendritic) and the quantity, location, and passability of each barrier. Our hypothetical network modeling indicates that locations of dams with limited passage efficiency near the watershed outlet create a strong fragmentation signal but are not individually sufficient to disconnect the system. Furthermore, there exists a threshold in the number of dams beyond which connectivity declines precipitously, regardless of watershed topology and dam configuration. Watersheds with highly branched configurations are shown to be less susceptible to disconnection as measured by this metric. Second, we applied the model to prioritize barrier improvement in the mainstem of the Truckee River, Nevada, USA. The Truckee River application demonstrates the ability of the algorithm to address conditions common in fish passage projects including incomplete data, parameter uncertainty, and rapid application. This study demonstrates the utility of a graph-theoretic approach for assessing fish passage connectivity in dendritic river networks assuming full basin utilization for a given species, guild, or community of concern.